Шрифт:
goalPosition = begin + widgets.size/2; // Нужный объект находится
// в середине отсортированного вектора
nth_element(begin, goalPosition, end, // Найти ранг median в widgets
qualityCompare);
… // goalPositon теперь указывает
// на Widget с рангом median
// Следующий фрагмент находит Widget с уровнем 75 процентилей
vector<Widget>::size_type goalOffset = // Вычислить удаление нужного
0.25*widgets.size; // объекта Widget от начала
nth_element(begin, egin+goalOffset, nd, // Найти ранг в
ualityCompare); // begin+goalOffset теперь
… // указывает на Widget
// с уровнем 75 процентилей
Алгоритмы
sort
, stable_sort
и partial_sort
хорошо подходят для упорядочивания результатов сортировки, а алгоритм nth_element
решает задачу идентификации верхних n
элементов или элемента, находящегося в заданной позиции. Иногда возникает задача, близкая к алгоритму nth_element
, но несколько отличающаяся от него. Предположим, вместо 20 объектов Widget
с максимальным рангом потребовалось выделить все объекты Widget
с рангом 1 или 2. Конечно, можно отсортировать вектор по рангу и затем найти первый элемент с рангом, большим 2. Найденный элемент определяет начало интервала с объектами Widget
, ранг которых превышает 2. Полная сортировка потребует большого объема работы, совершенно ненужной для поставленной цели. Более разумное решение основано на использовании алгоритма
partition
, упорядочивающего элементы интервала так, что все элементы, удовлетворяющие заданному критерию, оказываются в начале интервала. Например, для перемещения всех объектов
Widget
с рангом 2 и более в начало вектора widgets
определяется функция идентификации: bool hasAcceptableQualty(const Widgets w) {
// Вернуть результат проверки того, имеет ли объект w ранг больше 2
}
Затем эта функция передается при вызове
partition
: vector<Widget>::iterator goodEnd = // Переместить все объекты Widget,
partition(widgets.begin, // удовлетворяющие условию
widgets.end, // hasAcceptableQuality, в начало
hasAcceptableQuality); // widgets и вернуть итератор
// для первого объекта,
// не удовлетворяющего условию
После вызова интервал от
widgets.begin
до goodEnd
содержит все объекты Widget
с рангом 1 и 2, а интервал от goodEnd
до widgets.end
содержит все объекты Widget
с большими значениями ранга. Если бы в процессе деления потребовалось сохранить относительные позиции объектов Widget
с эквивалентными рангами, вместо алгоритма partition следовало бы использовать stable_partition
. Алгоритмы
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
.