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

void sort();	(1)	(начиная с C++11)
template< class Compare > void sort( Compare comp );	(2)	(начиная с C++11)

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

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

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

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

Параметры

comp

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

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

boolcmp(constType1&a,constType2&b);

Хотя сигнатура не обязана содержать const&, функция не должна изменять переданные ей объекты и должна принимать все значения типа (возможно, константного) Type1 и Type2 независимо от категории значения (таким образом, Type1& не допускается; также не допускается Type1, за исключением случая, когда для Type1 перемещение эквивалентно копированию(начиная с C++11)).
Типы Type1 и Type2 должны быть такими, чтобы объект типа forward_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 требует итераторов произвольного доступа, поэтому не может использоваться с forward_list. Эта функция также отличается от std::sort тем, что не требует, чтобы тип элементов forward_list поддерживал обмен значениями, сохраняет значения всех итераторов и выполняет стабильную сортировку.

Пример

#include <functional>
#include <iostream>
#include <forward_list>

std::ostream& operator<<(std::ostream& ostr, const std::forward_list<int>& list)
{
    for (const int i : list)
        ostr << ' ' << i;
    return ostr;
}

int main()
{
    std::forward_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

См. также

reverse

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

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