Чтобы данные постоянно находились в отсортированном состоянии, сохраните их в стандартном ассоциативном контейнере. Стоит также рассмотреть возможность использования стандартного контейнера priority_queue, данные которого тоже хранятся в отсортированном виде (контейнер priority_queue традиционно считается частью STL, но, как упоминалось в предисловии, в моем определении «контейнер STL» должен поддерживать итераторы, тогда как контейнер priority_queue их не поддерживает).
«А что можно сказать о быстродействии?» — спросите вы. Хороший вопрос. В общем случае время работы алгоритма зависит от объема выполняемой работы, а алгоритмам стабильной сортировки приходится выполнять больше работы, чем алгоритмам, игнорирующим фактор стабильности. В следующем списке алгоритмы, описанные в данном совете, упорядочены по возрастанию затрачиваемых ресурсов (времени и памяти):
1. partition;
2. stable_partition;
3. nth_element;
4. partial_sort;
5. sort;
6. stable_sort.
При выборе алгоритма сортировки я рекомендую руководствоваться целью, а не соображениями быстродействия. Если выбранный алгоритм ограничивается строго необходимыми функциями и не выполняет лишней работы (например, partition вместо полной сортировки алгоритмом sort), то программа будет не только четко выражать свое предназначение, но и наиболее эффективно решать поставленную задачу средствами STL.
Начнем с краткого обзора remove, поскольку этот алгоритм вызывает больше всего недоразумений в STL. Прежде всего необходимо рассеять все сомнения относительно того, remove, а также
Объявление remove выглядит следующим образом:
template
ForwardIterator remove(ForwardIterator first, ForwardIterator last, const T& value);
Как и все алгоритмы, remove получает пару итераторов, определяющих интервал элементов, с которыми выполняется операция. Контейнер при вызове не передается, потому remove не знает, в каком контейнере находятся искомые элементы. Более того, remove не может самостоятельно определить этот контейнер, поскольку не существует способа перехода от итератора к контейнеру, соответствующему ему.
Попробуем разобраться, как происходит удаление элементов из контейнера. Существует только один способ — вызов соответствующей функции контейнера, почти всегда некоторой разновидности erase (контейнер list содержит пару функций удаления элементов, имена которых не содержат erase). Поскольку удаление элемента из контейнера может производиться только вызовом функции данного контейнера, а алгоритм remove не может определить, с каким контейнером он работает, значит, remove remove не изменяет количества элементов в контейнере:
vector
v.reserve(10); // числами 1-10 (вызов reserve описан
for (int i=1; i<=10; ++i){ // в совете 14)
v.push_back(i);
};
cout << v.size; // Выводится число 10
v[3]=v[5]=v[9]=99; // Присвоить 3 элементам значение 99
remove(v.begin, v.end, 99); // Удалить все элементы со значением 99
cout << v.size; // Все равно выводится 10!
Чтобы понять смысл происходящего, необходимо запомнить следующее:
Алгоритм remove не знает, из какого контейнера он должен удалять элементы, а без этого он не может вызвать функцию «настоящего» удаления.
Итак, теперь вы знаете, чего алгоритм remove сделать не может и по каким причинам. Остается понять, что же он все-таки делает.
В общих чертах remove перемещает элементы в заданном интервале до тех пор, пока все «оставшиеся» элементы не окажутся в начале интервала (с сохранением их относительного порядка). Алгоритм возвращает итератор, указывающий на позицию за последним «оставшимся» элементом. Таким образом, возвращаемое значение можно интерпретировать как новый «логический конец» интервала.
