Эффективное использование STL

Алгоритмы sort, stable_sort, partial_sort и nth_element работают с итераторами произвольного доступа, поэтому они применимы только к контейнерам vector, string, deque и array. Сортировка элементов в стандартных ассоциативных контейнерах бессмысленна, поскольку эти контейнеры автоматически хранятся в отсортированном состоянии благодаря собственным функциям сравнения. Единственным контейнером, к которому хотелось бы применить алгоритмы sort, stable_sort, partial_sort и nth_element, является контейнер list — к сожалению, это невозможно, но контейнер list отчасти компенсирует этот недостаток функцией sort (интересная подробность: list:.-sort выполняет стабильную сортировку). Таким образом, полноценная сортировка list возможна, но алгоритмы partial_sort и nth_element приходится имитировать. В одном из таких обходных решений элементы копируются в контейнер с итераторами произвольного доступа, после чего нужный алгоритм применяется к этому контейнеру. Другое обходное решение заключается в создании контейнера, содержащего list:: iterator, применении алгоритма к этому контейнеру и последующему обращению к элементам списка через итераторы. Третье решение основано на использовании информации упорядоченного контейнера итераторов для итеративной врезки (splice) элементов list в нужной позиции. Как видите, выбор достаточно широк.

Алгоритмы partition и stable_partition отличаются от sort, stable_sort, partial_ sort и nth_element тем, что они работают только с двусторонними итераторами. Таким образом, алгоритмы partition и stable_partition могут использоваться с любыми стандартными последовательными контейнерами.

Подведем краткий итог возможностей и средств сортировки.

•Полная сортировка в контейнерах vector, string, deque и array: алгоритмы sort и stable_sort.

•Выделение n начальных элементов в контейнерах vector, string, deque и array: алгоритм partial_sort.

•Идентификация n начальных элементов или элемента, находящегося в позиции n, в контейнерах vector, string, deque и array: алгоритм nth_element.

•Разделение элементов стандартного последовательного контейнера на удовлетворяющие и не удовлетворяющие некоторому критерию: алгоритмы partition и stable_partition.

•Контейнер list: алгоритмы partition и stable_partition; вместо sort и stable_sort может использоваться list:: sort. Алгоритмы partial_sort или nth_element приходится имитировать. Существует несколько вариантов их реализации, некоторые из которых были представлены выше.

Чтобы данные постоянно находились в отсортированном состоянии, сохраните их в стандартном ассоциативном контейнере. Стоит также рассмотреть возможность использования стандартного контейнера 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.

Совет 32. Сопровождайте вызовы remove-подобных алгоритмов вызовом erase

Начнем с краткого обзора remove, поскольку этот алгоритм вызывает больше всего недоразумений в STL. Прежде всего необходимо рассеять все сомнения относительно того, что делает алгоритм remove, а также почему и как он это делает. Объявление remove выглядит следующим образом:

template

ForwardIterator remove(ForwardIterator first, ForwardIterator last, const T& value);

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