Почему нет перегрузки find / lower_bound для std :: map и нет перегрузки sort для std :: list?
Я знаю, что вы никогда не должны использовать std::find(some_map.begin(), some_map.end()) или же std::lower_boundпотому что это займет линейное время вместо логарифмического some_map.lower_bound, Подобное происходит с std::list: есть std::list::sort функция для сортировки, но вы не можете позвонить std::sort(some_list.begin(), some_list.end())потому что итераторы не имеют произвольного доступа.
Тем не мение, std::swapнапример, имеет перегрузки для стандартных контейнеров, так что вызов swap(some_map, other_map) принимает O (1), а не O (n). Почему стандарт C ++ не дает нам специализированные версии lower_bound а также find для карт и наборов? Есть ли глубокая причина?
Решение
Я не думаю, что есть глубокая причина, но это более философски, чем все остальное. Свободные функциональные формы стандартных алгоритмов, в том числе упомянутые вами, принимают пары итераторов, указывающие диапазон, через который они будут проходить. Алгоритм не может определить тип базового контейнера по этим итераторам.
Предоставление специализаций или перегрузок будет отходом от этой модели, поскольку вам придется передавать сам контейнер в алгоритм.
swap отличается, потому что он принимает экземпляры типов, участвующих в качестве аргументов, а не только итераторы.
Другие решения
Правило, которому следует STL, заключается в том, что алгоритмы свободных функций работают на итераторах и являются общими, не заботясь о типе диапазона, к которому относятся итераторы (кроме категории итераторов). Если конкретный тип контейнера может реализовать операцию более эффективно, чем использование std::algo(cont.begin(), cont.end()) затем эта операция предоставляется в качестве функции-члена контейнера и называется cont.algo(),
Так что у тебя есть std::map<>::lower_bound() а также std::map<>::find() а также std::list<>::sort(),
Тот простой факт, что такие функции должны работать в терминах пар итераторов, может привести к значительным накладным расходам, даже если они будут специализированы для итераторов отображения / отображения.
Имейте в виду, что:
-
Такие функции можно вызывать с любой парой итераторов, а не только с начала / конца.
-
Итераторы карты / наборов обычно реализуются как указатель на лист узел, а начальный узел члена
find/lower_boundэто корень узел дерева.
Наличие элемента find и lower_bound лучше, потому что указатель на корневой узел напрямую сохраняется как элемент объекта map / set.
Гипотетический не член find пришлось бы пройтись по дереву, чтобы найти наименьшего общего предка между двумя входными узлами, а затем выполнить команду dfs, при этом все же стараясь искать только в [первом, последнем) диапазоне, что значительно дороже.
Да, вы могли бы отслеживать корневой узел внутри итератора, а затем оптимизировать, если функция вызывается с парой начало / конец … просто чтобы избежать функции-члена?
Есть веские причины «философии дизайна» для того, чтобы не обеспечивать эти перегрузки. В частности, все взаимодействие контейнеров и алгоритмов STL предназначено для прохождения различных концепций итераторов, так что эти две части остаются независимыми, так что вы можете определять новые типы контейнеров без необходимости перегрузки для всех алгоритмов и, таким образом, вы можете определить новые алгоритмы без необходимости перегрузки для всех контейнеров.
Помимо этих вариантов проектирования, существует очень хорошая техническая причина, по которой эти алгоритмы (сортировка, нижняя граница и т. Д.) Не могут быть перегружены для специальных контейнеров, таких как list или же map / set, Причина в том, что итераторам не нужно явно подключаться к родительскому контейнеру. Другими словами, вы можете получить итераторы списка (начало / конец) из контейнера списка, но вы не можете получить (ссылку на) контейнер списка из итератора списка. То же самое касается итераторов map / set. Итераторы могут быть реализованы так, чтобы быть «слепыми» к своему родительскому контейнеру. Например, контейнер типа list обычно содержит в качестве членов данных указатели на узлы головы и хвоста и объект-распределитель, но самим итераторам (обычно просто указателям на узел) не нужно знать о заголовке / хвосте или распределителе, они просто имеют для перехода по предыдущим / следующим ссылочным указателям для перемещения вперед / назад в списке. Итак, если вы должны были реализовать перегрузку std::sort для list В контейнере не было бы способа извлечь контейнер списка из итераторов, которые передаются в функцию сортировки. И во всех упомянутых вами случаях версии алгоритмов, которые подходят для этих специальных контейнеров, «централизованы» в том смысле, что их нужно запускать на уровне контейнера, а не на «слепом» уровне итератора. Вот почему они имеют смысл как функции-члены, и поэтому вы не можете получить их от итераторов.
Однако, если вам нужен общий способ вызова этих алгоритмов независимо от имеющегося у вас контейнера, вы можете предоставить перегруженные шаблоны функций на уровне контейнера, если хотите. Это так просто, как это:
template <typename Container>
void sort_container(Container& c) {
std::sort(begin(c), end(c));
};
template <typename T, typename Alloc>
void sort_container(std::list<T, Alloc>& c) {
c.sort();
};
template <typename Key, typename T, typename Compare, typename Alloc>
void sort_container(std::map<Key, T, Compare, Alloc>&) { /* nothing */ };
//... so on..
Дело в том, что если вы уже связаны с контейнерами STL, то вы можете подключиться к алгоритмам STL таким образом, если хотите … но не ожидайте, что стандартная библиотека C ++ заставит вас иметь такой тип взаимозависимость между контейнерами и алгоритмами, потому что не все хотят их (например, многим людям действительно нравятся алгоритмы STL, но они не любят контейнеры STL (у которых есть многочисленные проблемы)).