std::list<T,Allocator>::sort

void sort();	(1)
template< class Compare > void sort( Compare comp );	(2)

Сортирует элементы и сохраняет порядок эквивалентных элементов. Ссылок и итераторов не становится недействительными.

1) Элементы сравниваются с помощью operator<.

2) Элементы сравниваются с помощью comp.

Если происходит исключение, порядок элементов в *this не определен.

Параметры

comp

объект-функция сравнения (т.е. объект, удовлетворяющий требованиям Compare), которая возвращает true если первый аргумент меньше (т.е. расположен раньше) второго.

Подпись функции сравнения должна быть эквивалентна следующей:

bool cmp(const Type1& a, const Type2& b);

Хотя подпись не обязательно должна иметь const&, функция не должна изменять передаваемые ей объекты и должна уметь принимать все значения типа (возможно, const) Type1 и Type2 независимо от категории значения (следовательно, Type1& не допускается, также как и Type1 , если для Type1 перемещение эквивалентно копированию(с C++11)).
Типы Type1 и Type2 должны быть такими, чтобы объект типа list<T,Allocator>::const_iterator можно было распаковать, а затем неявно преобразовать в оба из них.

Требования к типу

-Compare должен удовлетворять требованиям Compare.

Возвращаемое значение

(нет)

Сложность

Дано \(\scriptsize N\)N как std::distance(begin(), end()):

1) Приблизительно \(\scriptsize N \cdot log(N)\)N·log(N) сравнений, использующих operator<.

2) Приблизительно \(\scriptsize N \cdot log(N)\)N·log(N) применений функции сравнения comp.

Примечания

std::sort требует итераторов произвольного доступа и поэтому не может использоваться с list. Эта функция также отличается от std::sort тем, что не требует, чтобы тип элементов list поддерживал перестановку, сохраняет значения всех итераторов и выполняет стабильную сортировку.

Пример

#include <functional>
#include <iostream>
#include <list>
 
std::ostream& operator<<(std::ostream& ostr, const std::list<int>& list)
{
    for (const int i : list)
        ostr << ' ' << i;
    return ostr;
}
 
int main()
{
    std::list<int> list{8, 7, 5, 9, 0, 1, 3, 2, 6, 4};
    std::cout << "initially: " << list << '\n';
 
    list.sort();
    std::cout << "ascending: " << list << '\n';
 
    list.sort(std::greater<int>());
    std::cout << "descending:" << list << '\n';
}

Вывод:

initially:  8 7 5 9 0 1 3 2 6 4
ascending:  0 1 2 3 4 5 6 7 8 9
descending: 9 8 7 6 5 4 3 2 1 0

Отчеты об ошибках

Следующие отчеты об ошибках, изменяющие поведение, были применены ретроактивно к ранее опубликованным стандартам C++.

DR	Применён к	Поведение, как опубликовано	Правильное поведение
LWG 1207	C++98	не было ясно, будут ли итераторы и/или ссылки аннулированы	сохранить действительными

См. также

reverse

инвертирует порядок элементов
(общедоступный член-функция)

© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/w/cpp/container/list/sort