std::sort

template< class RandomIt >
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 ExecutionPolicy, class RandomIt, class Compare >
void sort( ExecutionPolicy&& policy,
           RandomIt first, RandomIt last, Compare comp );

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

Если выполнено любое из следующих условий, поведение не определено:

Параметры

Сложность

Дано \(\scriptsize N\) N как last - first :

Исключения

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

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

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

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

Примечания

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

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

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

Пример

#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++.

См. также