Скотт Мейерс - Эффективное использование STL

Алгоритмы 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.

Начнем с краткого обзора 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; // Создать vector и заполнить его