nth element(begin.goalPosition.end. Найти ранг median в widgets qualityCompare):

goalPosition теперь указывает на Widget с рангом median Следующий фрагмент находит Widget с уровнем 75 процентилей

vector<Widget>::size type goalOffset - Вычислить удаление нужного 0.25*widgets.size(): объекта Widget от начала

nth e1ement(begin,begin+goalOffset,end, Найти ранг в

qualityCompare): begin+goalOffset теперь

указывает на Widget с уровнем 75 процентилей

Алгоритмы sort, stable sort и partial sort хорошо подходят для упорядочивания результатов сортировки, а алгоритм nth el ement решает задачу идентификации верхних п элементов или элемента, находящегося в заданной позиции. Иногда возникает задача, близкая к алгоритму nth el ement, но несколько отличающаяся от него. Предположим, вместо 20 объектов Widget с максимальным рангом потребовалось выделить все объекты Wi dget с рангом 1 или 2. Конечно, можно отсортировать вектор по рангу и затем найти первый элемент с рангом, большим 2. Найденный элемент определяет начало интервала с объектами Widget, ранг которых превышает 2.

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

Например, для перемещения всех объектов Widget с рангом 2 и более в начало вектора widgets определяется функция идентификации:

bool hasAcceptableQualityCconst WidgetS w) {

Вернуть результат проверки того, имеет ли объект w ранг больше 2

Затем эта функция передается при вызове partition:

vector<Widget>::iterator goodEnd = Переместить все объекты Widget. partitionCwidgets.beginO, удовлетворяющие условию

widgets.end(), hasAcceptableQuality. в начало

hasAcceptableQuality): widgets и вернуть итератор для первого объекта. не удовлетворяющего условию

После вызова интервал от widgets.begiп() до goodEnd содержит все объекты Widget с рангом 1 и 2, а интервал от goodEnd до widgets.end() содержит все объекты Widget с большими значениями ранга. Если бы в процессе деления потребовалось сохранить относительные позиции объектов Widget с эквивалентными рангами, вместо алгоритма partition следовало бы использовать stable partition.

Алгоритмы sort, stable sort, parti al sort и nth e1 ement работают с итераторами произвольного доступа, поэтому они применимы только к контейнерам vector.

stri ng, deque и array. Сортировка элементов в стандартных ассоциативных контейнерах бессмысленна, поскольку эти контейнеры автоматически хранятся в отсортированном состоянии благодаря собственным функциям сравнения. Единственным контейнером, к которому хотелось бы применить алгоритмы sort, stable sort, partial sort и nth element, является контейнер list - к сожалению, это невозможно, но контейнер 1 i st отчасти компенсирует этот недостаток функцией sort (интересная подробность: list:.-sort выполняет стабильную сортировку). Таким образом, полноценная сортировка 1 i st возможна, но алгоритмы parti al sort и nth el ement приходится имитировать. В одном из таких обходных решений элементы копируются в контейнер с итераторами произвольного доступа, после чего нужный алгоритм применяется к этому контейнеру. Другое обходное решение заключается в создании контейнера, содержащего list::iterator, применении алгоритма к этому контейнеру и последующему обращению к элементам списка через итераторы. Третье решение основано на использовании информации упорядоченного контейнера итераторов для итеративной врезки (spl ice) элементов 1 i st в нужной позиции. Как видите, выбор достаточно широк.

Алгоритмы partition и stable partition отличаются от sort, stable sort, partial sort и nth el ement тем, что они работают только с двусторонними итераторами. Таким образом, алгоритмы partition и stable partition могут использоваться с любыми стандартными последовательными контейнерами.

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

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

Выделение n начальных элементов в контейнерах vector, stri ng, deque и array алгоритм parti al sort.

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

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

Контейнер 1 i st: алгоритмы partition и stablepartition; вместо sort и stable sort может использоваться 1 i st:: sort. Алгоритмы partial sort или nth el ement приходится имитировать. Существует несколько вариантов их реализации, некоторые из которых были представлены выше.

Чтобы данные постоянно находились в отсортированном состоянии, сохраните их в стандартном ассоциативном контейнере. Стоит также рассмотреть возможность использования стандартного контейнера priority queue, данные которого тоже хранятся в отсортированном виде (контейнер priorityqueue традиционно считается частью STL, но, как упоминалось в предисловии, в моем определении контейнер STL должен поддерживать итераторы, тогда как контейнер priority queue их не поддерживает).

А что можно сказать о быстродействии? - спросите вы. Хороший вопрос. В общем случае время работы алгоритма зависит от объема выполняемой работы.

а алгоритмам стабильной сортировки приходится выполнять больше работы, чем алгоритмам, игнорирующим фактор стабильности. В следующем списке алгоритмы, описанные в данном совете, упорядочены по возрастанию затрачиваемых ресурсов (времени и памяти):

1. partition;

2. stable partition;

3. nth el ement;

4. partial sort;

5. sort;

6. stable sort.

При выборе алгоритма сортировки я рекомендую руководствоваться целью, а не соображениями быстродействия. Если выбранный алгоритм ограничивается строго необходимыми функциями и не выполняет лишней работы (например, partition вместо полной сортировки алгоритмом sort), то программа будет не только четко выражать свое предназначение, но и наиболее эффективно решать поставленную задачу средствами STL.

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

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

tempiate<class Forwardlterator.class T>

Forwardlterator removeCForwardlterator first.Forwardlterator last, const T& value):

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

Попробуем разобраться, как происходит удаление элементов из контейнера. Существует только один способ - вызов соответствующей функции контейнера, почти всегда некоторой разновидности erase (контейнер 1 i st содержит пару функций удаления элементов, имена которых не содержат erase). Поскольку удаление элемента из контейнера может производиться только вызовом функции данного контейнера, а алгоритм remove не может определить, с каким контейнером он работает, значит, алгоритм remove не может удалять элементы из контейнера. Этим