Эффективное использование 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<class ForwardIterator, class T>

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

Как и все алгоритмы,

remove

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

remove

не знает, в каком контейнере находятся искомые элементы. Более того,

remove

не может самостоятельно определить этот контейнер, поскольку не существует способа перехода от итератора к контейнеру, соответствующему ему.

Попробуем разобраться, как происходит удаление элементов из контейнера. Существует только один способ — вызов соответствующей функции контейнера, почти всегда некоторой разновидности

erase

(контейнер

list

содержит пару функций удаления элементов, имена которых не содержат

erase

). Поскольку удаление элемента из контейнера может производиться только вызовом функции данного контейнера, а алгоритм

remove

не может определить, с каким контейнером он работает, значит, алгоритм

remove

не может удалять элементы из контейнера. Этим объясняется тот удивительный факт, что вызов

remove

не изменяет количества элементов в контейнере:

vector<int> v; // Создать vector<int> и заполнить его

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