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 이 throw됩니다.

가능한 구현

구현체는 또한 libstdc++ 와 libc++ 에서 확인할 수 있습니다.

참고 사항

LWG713 이전에는, LWG713 복잡도 요구사항이 sort() 구현에 Quicksort 만을 사용하는 것을 허용했으며, 이는 최악의 경우 \(\scriptsize O(N^2)\) O(N 2
) 비교 연산이 필요할 수 있습니다.

인트로소트 는 모든 경우에 대해 \(\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++ 표준에 소급 적용되었습니다.

참고