Namespaces
Variants

    std::lexicographical_compare

    cppreference.net에서
     
    C++
     
    알고리즘 라이브러리
    제약된 알고리즘 및 범위 기반 알고리즘 (C++20)
    제약된 알고리즘, 예: ranges::copy, ranges::sort, ...
    정렬 및 관련 연산
    분할 연산
    (C++11)    
    (C++11)

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


     
    헤더 <algorithm> 
    template< class InputIt1, class InputIt2 >
bool lexicographical_compare( InputIt1 first1, InputIt1 last1,
                              InputIt2 first2, InputIt2 last2 );
    		에 정의됨 (1) (C++20부터 constexpr) 
    template< class ExecutionPolicy,
          class ForwardIt1, class ForwardIt2 >
bool lexicographical_compare( ExecutionPolicy&& policy,
                              ForwardIt1 first1, ForwardIt1 last1,
                              ForwardIt2 first2, ForwardIt2 last2 );
    		(2) (C++17부터) 
    template< class InputIt1, class InputIt2, class Compare >
bool lexicographical_compare( InputIt1 first1, InputIt1 last1,
                              InputIt2 first2, InputIt2 last2,
                              Compare comp );
    		(3) (C++20부터 constexpr) 
    template< class ExecutionPolicy,
          class ForwardIt1, class ForwardIt2, class Compare >
bool lexicographical_compare( ExecutionPolicy&& policy,
                              ForwardIt1 first1, ForwardIt1 last1,
                              ForwardIt2 first2, ForwardIt2 last2,
                              Compare comp );
    		(4) (C++17부터)

    첫 번째 범위 [first1, last1) 가 두 번째 범위 보다 사전식으로 작은지[first2, last2) 확인합니다.

    1) 요소들은 operator<을(를) 사용하여 비교됩니다.
    3) 요소들은 주어진 이진 비교 함수 comp을(를) 사용하여 비교됩니다.
    2,4) (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부터)

    사전식 비교는 다음과 같은 속성을 가진 연산입니다:

    • 두 범위는 요소별로 비교됩니다.
    • 첫 번째로 일치하지 않는 요소가 어느 범위가 다른 범위보다 사전식으로 작은지 또는 큰지를 정의합니다.
    • 한 범위가 다른 범위의 접두사인 경우, 더 짧은 범위가 다른 범위보다 사전식으로 작습니다.
    • 두 범위가 동등한 요소를 가지며 길이가 같으면, 두 범위는 사전식으로 동등합니다.
    • 빈 범위는 비어 있지 않은 범위보다 사전식으로 작습니다.
    • 두 빈 범위는 사전식으로 동등합니다.

    매개변수

    first1, last1 - 검사할 첫 번째 범위의 요소를 정의하는 반복자 쌍
    first2, last2 - 검사할 두 번째 범위의 요소를 정의하는 반복자 쌍
    policy - 사용할 실행 정책
    comp - 비교 함수 객체 (즉, Compare의 요구 사항을 만족하는 객체)로, 첫 번째 인수가 두 번째 인수보다 true작으면 을(를) 반환합니다.

    비교 함수의 시그니처는 다음과 동등해야 합니다:

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

    시그니처에 const&이(가) 있을 필요는 없지만, 함수는 전달된 객체를 수정해서는 안 되며, Type1 (const 가능) 및 Type2 유형의 모든 값을 값 카테고리에 관계없이 받아들일 수 있어야 합니다 (따라서 Type1&은(는) 허용되지 않으며, Type1 또한 Type1 이동이 복사와 동등한 경우(C++11부터)가 아니면 허용되지 않습니다).
    유형 Type1 및 Type2은(는) InputIt1 및 InputIt2 유형의 객체를 역참조한 후 Type1 및 Type2에 모두 암시적으로 변환될 수 있어야 합니다.

    유형 요구 사항
    -
    InputIt1, InputIt2은(는) LegacyInputIterator의 요구 사항을 충족해야 합니다.
    -
    ForwardIt1, ForwardIt2은(는) LegacyForwardIterator의 요구 사항을 충족해야 합니다.
    -
    Compare은(는) Compare의 요구 사항을 충족해야 합니다.

    반환값

    true첫 번째 범위가 두 번째 범위보다 사전식으로 작으면 false, 그렇지 않으면

    입니다.

    복잡도N1을 std::distance(first1, last1)으로 하고, N2를 std::distance(first2, last2)으로 할 때:

    1,2) 최대 2min(1,N2)번의 operator< 비교를 수행합니다.
    3,4) 최대 2min(N1,N2)번의 비교 함수 comp 적용을 수행합니다.

    예외

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

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

    가능한 구현

    lexicographical_compare (1) 
    template<class InputIt1, class InputIt2>
bool lexicographical_compare(InputIt1 first1, InputIt1 last1,
                             InputIt2 first2, InputIt2 last2)
{
    for (; (first1 != last1) && (first2 != last2); ++first1, (void) ++first2)
    {
        if (*first1 < *first2)
            return true;
        if (*first2 < *first1)
            return false;
    }
    
    return (first1 == last1) && (first2 != last2);
}
    lexicographical_compare (3) 
    template<class InputIt1, class InputIt2, class Compare>
bool lexicographical_compare(InputIt1 first1, InputIt1 last1,
                             InputIt2 first2, InputIt2 last2, Compare comp)
{
    for (; (first1 != last1) && (first2 != last2); ++first1, (void) ++first2)
    {
        if (comp(*first1, *first2))
            return true;
        if (comp(*first2, *first1))
            return false;
    }
    
    return (first1 == last1) && (first2 != last2);
}

    예제

    이 코드 실행
    #include <algorithm>
#include <iostream>
#include <random>
#include <vector>

void print(const std::vector<char>& v, auto suffix)
{
    for (char c : v)
        std::cout << c << ' ';
    std::cout << suffix;
}

int main()
{
    std::vector<char> v1{'a', 'b', 'c', 'd'};
    std::vector<char> v2{'a', 'b', 'c', 'd'};
    
    for (std::mt19937 g{std::random_device{}()};
         !std::lexicographical_compare(v1.begin(), v1.end(),
                                       v2.begin(), v2.end());)
    {
        print(v1, ">= ");
        print(v2, '\n');
        
        std::shuffle(v1.begin(), v1.end(), g);
        std::shuffle(v2.begin(), v2.end(), g);
    }
    
    print(v1, "<  ");
    print(v2, '\n');
}

    가능한 출력: 

    a b c d >= a b c d 
d a b c >= c b d a 
b d a c >= a d c b 
a c d b <  c d a b

    결함 보고서

    다음 동작 변경 결함 보고서는 이전에 발표된 C++ 표준에 소급하여 적용되었습니다.

    DR 적용 대상 발표된 동작 올바른 동작
    LWG 142 C++98 최대 min(N1,N2)번의 비교가 허용되었지만, 이는
    불가능합니다 (동등성은 2번의 비교로 결정됨)     		한계를 두 배로 높임
    LWG 1205 C++98 빈 범위를 포함한 사전식 비교의 결과가 명확하지 않음 명확히 함

    참고 항목

    		 두 요소 집합이 동일한지 결정합니다
    (함수 템플릿 & 알고리즘 함수 객체)
    (C++20)
    (C++20)
    		 삼방향 비교를 사용하여 두 범위를 비교합니다
    (함수 템플릿)
    (C++20)
    		 두 범위를 사전식으로 비교합니다
    (알고리즘 함수 객체)