std::sort
Объявление
<tbody> </tbody>| Определено в заголовочном файле <algorithm>
|
||
template< class RandomIt > void sort( RandomIt first, RandomIt last ); |
(1) | (constexpr начиная с C++20) |
template< class ExecutionPolicy, class RandomIt > void sort( ExecutionPolicy&& policy, RandomIt first, RandomIt last ); |
(2) | (начиная с C++17) |
template< class RandomIt, class Compare > void sort( RandomIt first, RandomIt last, Compare comp ); |
(3) | (constexpr начиная с C++20) |
template< class ExecutionPolicy, class RandomIt, class Compare > void sort( ExecutionPolicy&& policy, RandomIt first, RandomIt last, Compare comp ); |
(4) | (начиная с C++17) |
Описание
Сортировка элементов в диапазоне [first, last) в порядке "возрастания". Сохранность порядка элементов, имеющих одинаковое значение, не гарантируется.
comp.policy.|
|
(до C++20) |
|
|
(начиная с C++20) |
Параметры
[first, last)
|
— | два итератора задающих диапазон элементов для сортировки |
| comp | — | объект функции сравнения (т.е. объект, удовлетворяющий требованиям Compare), который возвращает true, если первый аргумент "меньше", чем второй.Определение сравнения должно быть эквивалентно:
Использование |
| Требования к типам | ||
-RandomIt должен соответствовать требованиям ValueSwappable и RandomAccessIterator.
| ||
-The type of dereferenced RandomIt must meet the requirements of MoveAssignable and MoveConstructible.
| ||
Возвращаемое значение
(Нет)
Предусловия
| Этот раздел не завершён |
Постусловия
[[assume(std::is_sorted(first,last))]][[assume(std::is_sorted(first,last,comp))]]Исключения
Перегрузки с параметром шаблона по имени ExecutionPolicy сообщают об ошибках следующим образом:
- Если выполнение функции, вызванной как часть алгоритма, вызывает исключение и
ExecutionPolicyявляется одной из стандартных политик, вызывается std::terminate. Для любой другойExecutionPolicyповедение определяется реализацией. - Если алгоритму не удаётся выделить память, генерируется std::bad_alloc.
Сложность
O(N·log(N)), где N = std::distance(first, last) применения cmp.
Заметки
До LWG713, сложность std::sort() зависела от реализации Quicksort, гарантировалось лишь O(N2
) сравнений в худшем случае.
Introsort имеет сложность O(N·log(N)) сравнений (without incurring additional overhead in the average case), и, теперь обычно используется для реализации sort().
в libc++
Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда.
Пример
См. также реализацию в libstdc++ и libc++.
#include <algorithm>
#include <functional>
#include <array>
#include <iostream>
#include <iterator>
int main()
{
std::array<int, 10> s{5, 7, 4, 2, 8, 6, 1, 9, 0, 3};
std::sort(s.begin(), s.end());
std::copy(s.begin(), s.end(), std::ostream_iterator<int>(std::cout," "));
std::cout << std::endl;
std::sort(s.begin(), s.end(), std::greater<int>());
std::copy(s.begin(), s.end(), std::ostream_iterator<int>(std::cout," "));
std::cout << std::endl;
}
Вывод:
0 1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1 0
См. также
| сортирует первые N элементов диапазона (шаблон функции) | |
| сортирует диапазон элементов, сохраняя порядок между равными элементами (шаблон функции) | |
(C++20) |
сортирует диапазон в порядке возрастания (ниблоид) |