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

Действительно, sort — превосходный алгоритм, однако полноценная сортировка требуется далеко не всегда. Например, если у вас имеется вектор объектов Widget и вы хотите отобрать 20 «лучших» объектов с максимальным рангом, можно ограничиться сортировкой, позволяющей выявить 20 нужных объектов и оставить остальные объекты несортированными. Задача называется частичной сортировкой, и для ее решения существует специальный алгоритм partial_sort:

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[l] и т. д.

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

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

nth_element(widgets.begin().//Переместить 20 «лучших» элементов

widgets.beginC)+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 А предшествует Widget В в несортированном векторе widgets и при этом ранги двух объектов совпадают, стабильный алгоритм сортировки гарантирует, что после сортировки Widget А по-прежнему будет предшествовать Widget В. Нестабильный алгоритм такой гарантии не дает.