std::sort

template< class RandomIt >
void sort( RandomIt first, RandomIt last );

template< class RandomIt >
constexpr void sort( RandomIt first, RandomIt last );

template< class ExecutionPolicy, class RandomIt >
void sort( ExecutionPolicy&& policy,
           RandomIt first, RandomIt last );

template< class RandomIt, class Compare >
void sort( RandomIt first, RandomIt last, Compare comp );

template< class RandomIt, class Compare >
constexpr void sort( RandomIt first, RandomIt last, Compare comp );

template< class ExecutionPolicy, class RandomIt, class Compare >
void sort( ExecutionPolicy&& policy,
           RandomIt first, RandomIt last, Compare comp );

Сортирует элементы в диапазоне [first, last) в порядке невозрастания. Порядок равных элементов не гарантируется.

Последовательность сортируется относительно компаратора comp если для любого итератора it , указывающего на последовательность, и любого неотрицательного целого числа n такого, что it + n — это допустимый итератор, указывающий на элемент последовательности, comp(*(it + n), *it) (или *(it + n) < *it) оценивается как false.

Параметры

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

(ничего)

Сложность

O(N·log(N)) сравнений, где N есть std::distance(first, last).

Исключения

Перегрузки с параметром шаблона, названным ExecutionPolicy сообщают об ошибках следующим образом:

• Если выполнение функции, вызванной как часть алгоритма, вызывает исключение, и ExecutionPolicy — одна из стандартных политик, то std::terminate вызывается. Для любой другой ExecutionPolicy, поведение является определенным реализацией.
• Если алгоритм не может выделить память, выбрасывается std::bad_alloc.

Примечания

До LWG713 требование сложности позволяло sort() реализовываться только с использованием быстрой сортировки, что может потребовать O(N²) сравнений в худшем случае.

Introsort может обрабатывать все случаи с O(N·log(N)) сравнениями (без дополнительных накладных расходов в среднем случае), и поэтому обычно используется для реализации sort().

libc++ не реализовала исправленное требование по временной сложности до LLVM 14.

Возможная реализация

См. также реализации в libstdc++ и libc++.

Пример

#include <algorithm>
#include <array>
#include <functional>
#include <iostream>
#include <string_view>
 
int main()
{
    std::array<int, 10> s {5, 7, 4, 2, 8, 6, 1, 9, 0, 3};
 
    auto print = [&s](std::string_view const rem)
    {
        for (auto a : s)
            std::cout << a << ' ';
        std::cout << ": " << rem << '\n';
    };
 
    std::sort(s.begin(), s.end());
    print("sorted with the default operator<");
 
    std::sort(s.begin(), s.end(), std::greater<int>());
    print("sorted with the standard library compare function object");
 
    struct
    {
        bool operator()(int a, int b) const { return a < b; }
    }
    customLess;
 
    std::sort(s.begin(), s.end(), customLess);
    print("sorted with a custom function object");
 
    std::sort(s.begin(), s.end(), [](int a, int b)
                                  {
                                      return a > b;
                                  });
    print("sorted with a lambda expression");
}

0 1 2 3 4 5 6 7 8 9 : sorted with the default operator<
9 8 7 6 5 4 3 2 1 0 : sorted with the standard library compare function object
0 1 2 3 4 5 6 7 8 9 : sorted with a custom function object
9 8 7 6 5 4 3 2 1 0 : sorted with a lambda expression

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

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

См. также