Скотт Мейерс - Эффективное использование 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[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 В. Нестабильный алгоритм такой гарантии не дает.

Алгоритм partial_sort, как и алгоритм nth_element, стабильным не является. Алгоритм sort также не обладает свойством стабильности, но существует специальный алгоритм stable_sort, который, как следует из его названия, является стабильным. При необходимости выполнить стабильную сортировку, вероятно, следует воспользоваться stable_sort. В STL не входят стабильные версии partial_sort и nth_element.

Следует заметить, что алгоритм nth_element чрезвычайно универсален. Помимо выделения n верхних элементов в интервале, он также может использоваться для вычисления медианы по интервалу и поиска значения конкретного процентиля [3] Термин употребляется в статистике. — Примеч. ред. :

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

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

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

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

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

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

goalPosition = begin + widgets.size()/2; // Нужный объект находится

// в середине отсортированного вектора

nth_element(begin.goalPosition.end. // Найти ранг median в widgets qualityCompare):

// goalPositon теперь указывает // на Widget с рангом median // Следующий фрагмент находит Widget с уровнем 75 процентилей

vector::size_type goalOffset - // Вычислить удаление нужного 0.25*wdgets.size():// объекта Widget от начала

nth_element(begin,begin+goalOffset,end, // Найти ранг в

qualityCompare):// begin+goalOffset теперь

// указывает на Widget // с уровнем 75 процентилей

Алгоритмы so rt, stable_so rt и pa rti al_so rt хорошо подходят для упорядочивания результатов сортировки, а алгоритм nth_elementрешает задачу идентификации верхних п элементов или элемента, находящегося в заданной позиции. Иногда возникает задача, близкая к алгоритму nth_element,но несколько отличающаяся от него. Предположим, вместо 20объектов Widgetс максимальным рангом потребовалось выделить все объекты Widgetс рангом 1 или 2. Конечно, можно отсортировать вектор по рангу и затем найти первый элемент с рангом, большим 2. Найденный элемент определяет начало интервала с объектами Widget,ранг которых превышает 2.

Полная сортировка потребует большого объема работы, совершенно ненужной для поставленной цели. Более разумное решение основано на использовании алгоритма partition,упорядочивающего элементы интервала так, что все элементы, удовлетворяющие заданному критерию, оказываются в начале интервала.

Например, для перемещения всех объектов Widgetс рангом 2 и более в начало вектора widgetsопределяется функция идентификации:

bool hasAcceptableQualty(const Widgets w) {

// Вернуть результат проверки того, имеет ли объект w ранг больше 2