Специализирующие алгоритмы STL, чтобы они автоматически вызывали эффективные функции-члены контейнера при их наличии

Question

STL имеет глобальные алгоритмы, которые могут работать с произвольными контейнерами, если они поддерживают основные требования этого алгоритма.Например, некоторые алгоритмы могут требовать, чтобы у контейнера были итераторы произвольного доступа, такие как вектор, а не список.

Когда у контейнера есть более быстрый способ сделать что-либо, чем у общего алгоритма, он предоставляет функцию-член содно и то же имя для достижения той же цели - например, список, предоставляющий свои собственные remove_if(), поскольку он может удалять элементы, просто выполняя операции с указателями в постоянное время.

Мой вопрос - возможно ли / целесообразно специализироватьуниверсальные алгоритмы, чтобы они автоматически вызывали версию функции-члена для контейнеров, где это более эффективно?Например, есть std::remove_if вызов list::remove_if внутри для списков.Это уже сделано в STL?

Answer 1

Не в случае remove_if, так как семантика различна. std::remove_if на самом деле ничего не удаляет из контейнера, в то время как list::remove_if делает, так что вы определенно не хотите, чтобы первое вызывало второе.

Ни вы, ни реализация не могут буквально специализировать универсальные алгоритмы для контейнеров, поскольку алгоритмы являются шаблонами функций, которые принимают итераторы, а сами контейнеры являются шаблонами классов, тип итератора которых зависит от параметра шаблона. Таким образом, чтобы специализировать std::remove_if в общем случае для list<T>::iterator, вам потребуется частичная специализация remove_if, и нет такой вещи, как частичная специализация шаблона функции.

Я не могу вспомнить, разрешено ли реализациям перегружать алгоритмы для определенных типов итераторов, но даже если не "официальный" алгоритм, может вызывать функцию, которая может быть перегружена, или он может использовать класс, который может быть частично специализированным. К сожалению, ни один из этих методов не поможет вам, если вы написали свой собственный контейнер и нашли способ сделать стандартный алгоритм особенно эффективным для него.

Предположим, например, что у вас есть контейнер с итератором с произвольным доступом, но где у вас есть особенно эффективный метод сортировки, который работает со стандартным порядком: сортировка по сегментам, возможно. Тогда вы можете подумать о том, чтобы поместить свободную функцию template <typename T> void sort(MyContainer<T>::iterator first, MyContainer<T>::iterator last) в то же пространство имен, что и класс, и позволить людям вызывать ее с помощью using std::sort; sort(it1, it2); вместо std::sort(it1, it2);. Проблема заключается в том, что если они делают это в общем коде, они рискуют, чтобы кто-то еще, пишущий какой-либо другой тип контейнера, имел функцию sort, которая даже не сортирует диапазон (английское слово "sort" имеет более одного значения , в конце концов). Таким образом, в общем случае вы не можете в общем случае сортировать диапазон итераторов таким образом, чтобы получать информацию об эффективности для пользовательских контейнеров.

Когда разница в коде зависит только от категории итератора (например, std::distance, который быстр для итераторов с произвольным доступом и медленный в противном случае), это делается с помощью так называемой «отправки тега итератора», и это Наиболее распространенный случай, когда существует явная разница в эффективности между различными контейнерами.

Если есть какие-либо оставшиеся случаи, которые применяются к стандартным контейнерам (исключая случаи, когда результат отличается или если эффективность требует только определенной категории итераторов), давайте их рассмотрим.

Answer 2

Это невозможно - алгоритмы работают с итераторами, а итераторы не знают об объекте контейнера, на который они ссылаются.Даже если бы они это сделали, во время компиляции не было бы никакого способа определить, относится ли данный диапазон итераторов ко всему контейнеру, поэтому это не может быть сделано только одной специализацией;потребуется дополнительная проверка во время выполнения.

Answer 3

Единственный способ сделать это - создать собственные шаблоны-оболочки для каждого из алгоритмов, используя контейнер, а не пару итераторов.Тогда вы можете специализировать свою оболочку для каждого типа контейнера, который можно оптимизировать.К сожалению, это устраняет большую гибкость стандартных алгоритмов и наполняет ваши программы кучей нестандартных вызовов.

Answer 4

То, что вы ищете, это не специализация, а перегрузка .Вы могли бы предоставить альтернативные версии алгоритмов (но не юридически в пространстве имен std), которые принимают в качестве аргументов контейнеры , а не пары итераторов, и либо вызывают подвески STL, вызывая begin() и end() на контейнере или делай что-нибудь еще.Такой подход, конечно, требует кода для вызова ваших функций вместо функций STL.

Это, конечно, было сделано раньше, так что вы могли бы найти набор заголовков, которые избавят вас от работы по написанию всего этого стандартного кода.