Namespaces
Variants

    std::is_sorted_until

    cppreference.net에서
     
    C++
     
    알고리즘 라이브러리
    제약 조건이 있는 알고리즘과 범위에 대한 알고리즘 (C++20)
    제약 알고리즘, 예: ranges::copy, ranges::sort, ...
    정렬 및 관련 연산
    분할 연산
    (C++11)    
    (C++11)

    정렬 연산
    이진 검색 연산
    (정렬된 범위에서)
    집합 연산 (정렬된 범위에 대해)
    병합 연산 (정렬된 범위에 대해)
    힙 연산
    최소/최대 연산
    (C++11)
    (C++17)
    사전식 비교 연산
    (C++20)
    순열 연산


     
    헤더에 정의됨 <algorithm> 
    template< class ForwardIt >
ForwardIt is_sorted_until( ForwardIt first, ForwardIt last );
    		(1) (C++11부터)
    (C++20부터 constexpr)    		 
    template< class ExecutionPolicy, class ForwardIt >
ForwardIt is_sorted_until( ExecutionPolicy&& policy,
                           ForwardIt first, ForwardIt last );
    		(2) (C++17부터) 
    template< class ForwardIt, class Compare >
ForwardIt is_sorted_until( ForwardIt first, ForwardIt last,
                           Compare comp );
    		(3) (C++11부터)
    (C++20부터 constexpr)    		 
    template< class ExecutionPolicy, class ForwardIt, class Compare >
ForwardIt is_sorted_until( ExecutionPolicy&& policy,
                           ForwardIt first, ForwardIt last,
                           Compare comp );
    		(4) (C++17부터)

    범위 [first, last)를 검사하고, first에서 시작하는 가장 큰 범위를 찾습니다. 요소들은 비내림차순으로 정렬되어 있습니다.

    1) 요소들이 sorted 기준에 따라 정렬되어 있는 가장 큰 범위를 찾습니다. 기준: operator<(C++20까지)std::less{}(C++20부터).
    3) 요소들이 기준에 따라 정렬되어 있는 가장 큰 범위를 찾습니다. 기준: comp.
    2,4) (1,3)과 동일하지만, (1,3) policy에 따라 실행됩니다.
    이 오버로드들은 다음 표현식의 값이 true인 경우에만 오버로드 해결에 참여합니다:

    std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>

    		(C++20까지)

    std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>

    		(C++20부터)

    매개변수

    first, last - 검사할 요소들의 범위를 정의하는 반복자 쌍
    policy - 사용할 실행 정책을 위해
    comp - 비교 함수 객체 (즉, Compare 요구 사항을 만족하는 객체)로, 첫 번째 인수가 두 번째 인수보다 true작으면 ​ (즉, 앞에 오도록 정렬됨)을 반환합니다.

    비교 함수의 시그니처는 다음과 같아야 합니다:

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

    시그니처에 const&가 있을 필요는 없지만, 함수는 전달된 객체를 수정하지 않아야 하며, Type1 및 Type2 타입의 모든 값을 (값 종류에 관계없이) 받을 수 있어야 합니다 (따라서 Type1&는 허용되지 않으며, Type1도 Type1 이동이 복사와 동일한 경우가 아니면 허용되지 않습니다(C++11부터)).
    Type1과 Type2 타입은 ForwardIt 타입의 객체를 역참조한 후 암시적으로 두 타입 모두로 변환될 수 있어야 합니다. ​

    타입 요구 사항
    -
    ForwardIt는 LegacyForwardIterator의 요구 사항을 충족해야 합니다.
    -
    Compare는 Compare의 요구 사항을 충족해야 합니다.

    반환값

    first에서 시작하여 오름차순으로 정렬된 가장 큰 범위의 상한입니다. 즉, 범위 it가 정렬된 마지막 반복자 [first, it)입니다.

    빈 범위와 길이가 1인 범위에 대해 last을 반환합니다.

    복잡도

    N을 std::distance(first, last)로 나타낼 때:

    1,2) O(N) 번의 비교 (operator<(C++20까지)std::less{}(C++20부터) 사용).
    3,4) O(N) 번의 비교자 comp 적용.

    예외

    템플릿 매개변수 이름 ExecutionPolicy이 있는 오버로드는 다음과 같이 오류를 보고합니다:

    • 알고리즘의 일부로 호출된 함수에서 예외가 발생하고 ExecutionPolicy이 표준 정책 중 하나인 경우 std::terminate가 호출됩니다. 다른 ExecutionPolicy의 경우 동작은 구현에 따라 정의됩니다.
    • 알고리즘이 메모리 할당에 실패하면 std::bad_alloc이 발생합니다.

    가능한 구현

    libstdc++ 및 libc++의 구현도 참고하십시오.

    is_sorted_until (1) 
    template<class ForwardIt>
constexpr //< since C++20
ForwardIt is_sorted_until(ForwardIt first, ForwardIt last)
{
    return std::is_sorted_until(first, last, std::less<>());
}
    is_sorted_until (2) 
    template<class ForwardIt, class Compare>
constexpr //< since C++20
ForwardIt is_sorted_until(ForwardIt first, ForwardIt last, Compare comp)
{
    if (first != last)
    {
        ForwardIt next = first;
        while (++next != last)
        {
            if (comp(*next, *first))
                return next;
            first = next;
        }
    }
    return last;
}

    예제

    이 코드 실행
    #include <algorithm>
#include <cassert>
#include <iostream>
#include <iterator>
#include <random>
#include <string>

int main()
{
    std::random_device rd;
    std::mt19937 g(rd());
    const int N = 6;
    int nums[N] = {3, 1, 4, 1, 5, 9};
    
    const int min_sorted_size = 4;
    
    for (int sorted_size = 0; sorted_size < min_sorted_size;)
    {
        std::shuffle(nums, nums + N, g);
        int *const sorted_end = std::is_sorted_until(nums, nums + N);
        sorted_size = std::distance(nums, sorted_end);
        assert(sorted_size >= 1);
        
        for (const auto i : nums)
            std::cout << i << ' ';
        std::cout << ": " << sorted_size << " initial sorted elements\n"
                  << std::string(sorted_size * 2 - 1, '^') << '\n';
    }
}

    가능한 출력: 

    4 1 9 5 1 3 : 1 initial sorted elements
^
4 5 9 3 1 1 : 3 initial sorted elements
^^^^^
9 3 1 4 5 1 : 1 initial sorted elements
^
1 3 5 4 1 9 : 3 initial sorted elements
^^^^^
5 9 1 1 3 4 : 2 initial sorted elements
^^^
4 9 1 5 1 3 : 2 initial sorted elements
^^^
1 1 4 9 5 3 : 4 initial sorted elements
^^^^^^^

    참고 항목

    (C++11)
    		 범위가 정렬되었는지 확인
    (함수 템플릿 & 알고리즘 함수 객체)
    (C++20)
    (C++20)
    		 가장 큰 정렬된 하위 범위를 찾음
    (알고리즘 함수 객체)