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

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

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

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

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

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

Параметры

comp

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

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

boolcmp(constType1&a,constType2&b);

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

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

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

Сложность

Пусть \(\scriptsize N\)N — size():

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/cpp/container/list/sort