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

bool qualityCompare(const Widgets lhs, const Widgets rhs) {
 // Вернуть признак сравнения атрибутов quality
 // объектов lhs и rhs
}
…
partial_sort(widgets.begin, // Разместить 20 элементов
 widgets.begin+20, // с максимальным рангом
 widgets.end, // в начале вектора widgets
 qualityCompare);
… // Использование widgets

После вызова partial_sort первые 20 элементов widgets находятся в начале контейнера и располагаются по порядку, то есть widgets[0] содержит Widget с наибольшим рангом, затем следует widgets[1] и т. д.

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

Алгоритм nth_element сортирует интервал таким образом, что в заданной вами позиции n оказывается именно тот элемент, который оказался бы в ней при полной сортировке контейнера. Кроме того, при выходе из nth_element ни один из элементов в позициях до n не находится в порядке сортировки после элемента, находящегося в позиции n, а ни один из элементов в позициях после n не предшествует элементу, находящемуся в позиции n. Если такая формулировка кажется слишком сложной, это объясняется лишь тем, что мне приходилось тщательно подбирать слова. Вскоре я объясню причины, но сначала мы рассмотрим пример использования nth_element для перемещения 20 «лучших» объектов Widget в начало контейнера widgets:

nth_element(widgets.begin, // Переместить 20 «лучших» элементов
 widgets.begin+20, // в начало widgets
 widgets.end, // в произвольном порядке
 qualityCompare);

Как видите, вызов nth_element практически не отличается от вызова partial_sort. Единственное различие заключается в том, что partial_sort сортирует элементы в позициях 1-20, a nth_element этого не делает. Впрочем, оба алгоритма перемещают 20 объектов Widget с максимальными значениями ранга в начало вектора.

Возникает важный вопрос — что делают эти алгоритмы для элементов с одинаковыми значениями атрибута? Предположим, вектор содержит 12 элементов с рангом 1 и 15 элементов с рангом 2. В этом случае выборка 20 «лучших» объектов Widget будет состоять из 12 объектов с рангом 1 и 8 из 15 объектов с рангом 2. Но как алгоритмы partial_sort и nth_element определяют, какие из 15 объектов следует отобрать в «верхнюю двадцатку»? И как алгоритм sort выбирает относительный порядок размещения элементов при совпадении рангов?

Алгоритмы 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 процентилей