Скотт Мейерс - Эффективное использование STL

Когда речь заходит об упорядочении объектов, многим программистам приходит в голову всего один алгоритм: sort(некоторые вспоминают о qsort, но после прочтения совета 46 они раскаиваются и возвращаются к мыслям о sort).

Действительно, 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[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 по-прежнему будет предшествовать WidgetB. Нестабильный алгоритм такой гарантии не дает.