void sort(Rnd first, Rnd last);
void sort(Rnd first, Rnd last, BinPred comp);
Как и в большинстве других алгоритмов, если operator< не удовлетворяет вашим требованиям, можно указать собственный оператор сравнения. В среднем случае сложность имеет зависимость n log n. В худшем случае она может быть квадратичной.
Если требуется, чтобы одинаковые элементы сохранили свой первоначальный порядок, используйте stable_sort. Он имеет такую же сигнатуру, но гарантирует, что порядок эквивалентных элементов изменен не будет. Его сложность при наличии достаточного объема памяти в худшем случае составляет n log n. Если памяти недостаточно, то сложность может оказаться равной n(log n)².
Однако sort работает не для всех контейнеров. Он требует итераторов произвольного доступа, так что при использовании контейнера, не предоставляющего таких итераторов, он неприменим. Итераторы произвольного доступа предоставляют стандартные последовательные контейнеры deque, vector и string/wstring (которые не являются контейнерами, но удовлетворяют большинству требований к ним), list — это единственный, который такого итератора не предоставляет. Если требуется отсортировать список, используйте list::sort. Например, в примере 7.6 вы, вероятно, заметили, что list::sort не принимает никаких аргументов.
lst.sort();
Это отличает его от std::sort, с помощью которого можно отсортировать только часть последовательности. Если требуется отсортировать часть последовательности, то не следует использовать list.
Концепция сортировки очень проста, но есть несколько вариаций на тему ее реализации в стандартной библиотеке. Следующий перечень описывает эти вариации.
partial_sort
Принимает три итератора произвольного доступа — first, middle и last — и (необязательно) функтор сравнения. Он имеет два постусловия: элементы диапазона (first, middle) будут меньше, чем элементы диапазона (middle, last), и диапазон (first, middle) будет отсортирован с помощью operator< или указанного функтора сравнения. Другими словами, он сортирует только первые n элементов.
partial_sort_сору
Делает то же, что и partial_sort, но помещает результаты в выходной диапазон. Он берет первые n элементов из исходного диапазона и в соответствующем порядке копирует их в результирующий диапазон. Если результирующий диапазон (n) короче, чем исходный диапазон (m), то в результирующий диапазон копируется только n элементов.
nth_element
Принимает три итератора произвольного доступа — first, nth и last — и необязательный функтор сравнения. Он помешает элемент, на который ссылается nth, в то место, где он находился бы, если бы весь диапазон был отсортирован. Следовательно, все элементы диапазона (first, nth) будут меньше, чем элемент в позиции nth (те, что находятся в диапазоне (nth, last) не сортируются, но больше, чем те, что предшествуют nth). Этот алгоритм следует использовать тогда, когда требуется отсортировать только один или несколько элементов диапазона и избежать затрат на сортировку всего диапазона.
Также можно разделить элементы диапазона в соответствии с каким-либо критерием (функтором), и это является предметом обсуждения рецепта 7.7.
Рецепт 7.7.
7.7. Разделение диапазона
Имеется диапазон элементов, которые требуется каким-либо образом разделить на группы. Например, необходимо переместить в начало диапазона все элементы, которые меньше определенного значения.
Для перемещения элементов используйте стандартный алгоритм partition с предикатом-функтором. См. пример 7.7.
Пример 7.7. Разделение диапазона
#include <iostream>
#include <istream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <iterator>
#include "utils.h" // Для printContainer(): см. рецепт 7.10
using namespace std;
int main() {
cout << "Введите набор строк: ";
istream_iterator<string> start(cin);
istream_iterator<string> end; // Здесь создается "маркер"
vector<string> v(start, end);
// Реорганизуем элементы в v так, чтобы те, которые меньше,
// чем "foo", оказались перед остальными.
vector<string>::iterator p =
partition(v.begin(), v.end(),
bind2nd(less<string>(), "foo"));
printContainer(v);
cout << "*p = " << *p << endl;
}
Вывод примера 7.7 выглядит примерно так.
Введите набор строк: a d f j k l
^Z
-----
a d f j k l
*p = j
После работы partition итератор p указывает на первый элемент, для которого less(*p, "foo") не равно true.
partition принимает начало и конец диапазона и предикат и перемешает все элементы, для которых предикат равен true, в начало диапазона. Он возвращает итератор, указывающий на первый элемент, для которого предикат не равен true, или на конец диапазона, если все элементы удовлетворяют предикату. Он объявлен вот так.
Bi partition(Bi first, Bi last, Pred pred);
pred — это функтор, который принимает один аргумент и возвращает true или false. Предиката по умолчанию не существует — вы должны указать такой предикат, который удовлетворяет требованию разделения диапазона. При этом можно написать свой предикат, а можно использовать один из предикатов стандартной библиотеки. Например, в примере 7.7 можно видеть, что я для создания функтора использовал less и bind2nd.
vector<string>::iterator p =
partition(v.begin(), v.end(),
bind2nd(less<string>(), "foo"));
Здесь все элементы, которые меньше "foo", перемещаются в начало последовательности. bind2nd здесь необязателен, но он удобен для автоматического создания функтора, который принимает один аргумент и возвращает результат вычисления less<string>(*i, "foo") для каждого i-го элемента последовательности. Если требуется, чтобы одинаковые элементы сохранили свой первоначальный порядок, то следует использовать stable_partition.
partitionset, multiset, map и multimap. Причиной этого является то, что ассоциативные контейнеры хранят свои элементы в упорядоченном виде и перемещать и удалять элементы разрешается только самим контейнерам. Использовать partition можно с любым диапазоном, для которого можно получить, по крайней мере, двунаправленный итератор, и это выполняется для всех стандартных последовательных контейнеров, включая deque, vector и list.