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

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

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

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

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

bool hasAcceptableQualty(const Widgets w) {

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

}

Затем эта функция передается при вызове partition:

vector::iterator goodEnd = // Переместить все объекты Widget.

partton(widgets.begin(),// удовлетворяющие условию

widgets.end() ,// hasAcceptableQuality. в начало

hasAcceptableQuality); // widgets и вернуть итератор

// для первого объекта.

// не удовлетворяющего условию

После вызова интервал от widgets.begin() до goodEnd содержит все объекты Widget с рангом 1 и 2, а интервал от goodEnd до widgets.end() содержит все объекты Widget с большими значениями ранга. Если бы в процессе деления потребовалось сохранить относительные позиции объектов Widget с эквивалентными рангами, вместо алгоритма partition следовало бы использовать stable_partition.