Скотт Мейерс - Эффективное использование 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*widgets.size(); // объекта Widget от начала

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

ualityCompare); // begin+goalOffset теперь

… // указывает на Widget

// с уровнем 75 процентилей

Алгоритмы sort, stable_sortи partial_sortхорошо подходят для упорядочивания результатов сортировки, а алгоритм nth_elementрешает задачу идентификации верхних nэлементов или элемента, находящегося в заданной позиции. Иногда возникает задача, близкая к алгоритму 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,

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

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

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

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

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

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

Алгоритмы sort, stable_sort, partial_sortи nth_elementработают с итераторами произвольного доступа, поэтому они применимы только к контейнерам vector, string, dequeи array. Сортировка элементов в стандартных ассоциативных контейнерах бессмысленна, поскольку эти контейнеры автоматически хранятся в отсортированном состоянии благодаря собственным функциям сравнения. Единственным контейнером, к которому хотелось бы применить алгоритмы sort, stable_sort, partial_sortи nth_element, является контейнер list— к сожалению, это невозможно, но контейнер listотчасти компенсирует этот недостаток функцией sort(интересная подробность: list::sortвыполняет стабильную сортировку). Таким образом, полноценная сортировка listвозможна, но алгоритмы partial_sortи nth_elementприходится имитировать. В одном из таких обходных решений элементы копируются в контейнер с итераторами произвольного доступа, после чего нужный алгоритм применяется к этому контейнеру. Другое обходное решение заключается в создании контейнера, содержащего list::iterator, применении алгоритма к этому контейнеру и последующему обращению к элементам списка через итераторы. Третье решение основано на использовании информации упорядоченного контейнера итераторов для итеративной врезки ( splice) элементов listв нужной позиции. Как видите, выбор достаточно широк.