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

void sort();	(1)	(since C++11)
template< class Compare > void sort( Compare comp );	(2)	(since C++11)

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

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

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

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

Параметры

comp

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

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

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

Хотя подпись не обязательно должна иметь const&, функция не должна изменять передаваемые ей объекты и должна быть способна принимать все значения типа (возможно, константного) Type1 и Type2 независимо от категории значения (следовательно, Type1& не допускается, а также Type1 за исключением случаев, когда для Type1 перемещение эквивалентно копированию(since 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/w/cpp/container/forward_list/sort