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

Мейерс Скотт

Алгоритмы

partial_sort

и

nth_element

упорядочивают эквивалентные элементы по своему усмотрению, и сделать с этим ничего нельзя (понятие эквивалентности рассматривается в совете 19). Когда в приведенном примере возникает задача заполнения объектами

Widget

с рангом 2 восьми последних позиций в «верхней двадцатке», алгоритм выберет такие объекты, какие сочтет нужным. Впрочем, такое поведение вполне разумно. Если вы запрашиваете 20 «лучших» объектов

Widget

, а некоторых объекты равны, то в результате возвращенные объекты будут по

крайней мере «не хуже» тех, которые возвращены не были.

Полноценная сортировка обладает несколько большими возможностями. Некоторые алгоритмы сортировки стабильны. При стабильной сортировке два эквивалентных элемента в интервале сохраняют свои относительные позиции после сортировки. Таким образом, если

Widget

 A предшествует

Widget

 B в несортированном векторе

widgets

и при этом ранги двух объектов совпадают, стабильный алгоритм сортировки гарантирует, что после сортировки

Widget

 A по-прежнему будет предшествовать

Widget

B. Нестабильный алгоритм такой гарантии не дает.

Алгоритм

partial_sort

, как и алгоритм

nth_element

, стабильным не является. Алгоритм

sort

также не обладает свойством стабильности, но существует специальный алгоритм

stable_sort

, который, как следует из его названия, является стабильным. При необходимости выполнить стабильную сортировку, вероятно, следует воспользоваться

stable_sort

. В STL не входят стабильные версии

partial_sort

и

nth_element

.

Следует заметить, что алгоритм nth_element чрезвычайно универсален. Помимо выделения

n

верхних элементов в интервале, он также может использоваться для вычисления медианы по интервалу и поиска значения конкретного процентиля [3] :

3

Термин употребляется в статистике. — Примеч. ред.

vector<Widget>::iterator begin(widgets.begin); // Вспомогательные переменные

vector<Widget>::iterator end(widgets.end); // для начального и конечного

// итераторов widgets

vector<Widget>::iterator goalPosition; // Итератор, указывающий на

// интересующий нас объект Widget

// Следующий фрагмент находит Widget с рангом median

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

.