Полная сортировка потребует большого объема работы, совершенно ненужной для поставленной цели. Более разумное решение основано на использовании алгоритма partition, упорядочивающего элементы интервала так, что все элементы, удовлетворяющие заданному критерию, оказываются в начале интервала.
Например, для перемещения всех объектов Widget с рангом 2 и более в начало вектора widgets определяется функция идентификации:
bool hasAcceptableQualty(const Widgets w) {
// Вернуть результат проверки того, имеет ли объект w ранг больше 2
}
Затем эта функция передается при вызове partition:
vector
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 в нужной позиции. Как видите, выбор достаточно широк.
Алгоритмы partition и stable_partition отличаются от sort, stable_sort, partial_sort и nth_element тем, что они работают только с двусторонними итераторами. Таким образом, алгоритмы partition и stable_partition могут использоваться с любыми стандартными последовательными контейнерами.
Подведем краткий итог возможностей и средств сортировки.
• Полная сортировка в контейнерах vector, string, deque и array: алгоритмы sort и stable_sort.
• Выделение n начальных элементов в контейнерах vector, string, deque и array: алгоритм partial_sort.
• Идентификация n начальных элементов или элемента, находящегося в позиции n, в контейнерах vector, string, deque и array: алгоритм nth_element.
• Разделение элементов стандартного последовательного контейнера на удовлетворяющие и не удовлетворяющие некоторому критерию: алгоритмы partition и stable_partition.
• Контейнер list: алгоритмы partition и stable_partition; вместо sort и stable_sort может использоваться list::sort. Алгоритмы partial_sort или nth_element приходится имитировать. Существует несколько вариантов их реализации, некоторые из которых были представлены выше.
