std::ranges:: lexicographical_compare

From cppreference.net

헤더 파일에 정의됨 `<algorithm>`
함수 시그니처
template < std:: input_iterator I1, std:: sentinel_for < I1 > S1, std:: input_iterator I2, std:: sentinel_for < I2 > S2, class Proj1 = std:: identity , class Proj2 = std:: identity , std:: indirect_strict_weak_order < std :: projected < I1, Proj1 > , std :: projected < I2, Proj2 >> Comp = ranges:: less > constexpr bool lexicographical_compare ( I1 first1, S1 last1, I2 first2, S2 last2, Comp comp = { } , Proj1 proj1 = { } , Proj2 proj2 = { } ) ;	(1)	(C++20 이후)
template < ranges:: input_range R1, ranges:: input_range R2, class Proj1 = std:: identity , class Proj2 = std:: identity , std:: indirect_strict_weak_order < std :: projected < ranges:: iterator_t < R1 > , Proj1 > , std :: projected < ranges:: iterator_t < R2 > , Proj2 >> Comp = ranges:: less > constexpr bool lexicographical_compare ( R1 && r1, R2 && r2, Comp comp = { } , Proj1 proj1 = { } , Proj2 proj2 = { } ) ;	(2)	(C++20 이후)

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

1) 요소들은 주어진 이항 비교 함수 comp 를 사용하여 비교됩니다.

2) (1) 과 동일하지만, r 을 소스 범위로 사용하며, 마치 ranges:: begin ( r ) 을 first 로, ranges:: end ( r ) 를 last 로 사용하는 것과 같습니다.

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

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

이 페이지에서 설명하는 함수형 개체들은 algorithm function objects (일반적으로 niebloids 로 알려진)입니다. 즉:

명시적 템플릿 인수 목록은 이들 중 어느 것을 호출할 때도 지정할 수 없습니다.
이들 중 어느 것도 인수 의존적 탐색 에 보이지 않습니다.
이들 중 어느 것이 함수 호출 연산자의 왼쪽 이름으로 일반 비한정 탐색 에 의해 발견될 때, 인수 의존적 탐색 이 억제됩니다.

first1, last1	-	검사할 첫 번째 범위 를 정의하는 반복자-감시자 쌍
r1	-	검사할 첫 번째 요소 범위
first2, last2	-	검사할 두 번째 범위 를 정의하는 반복자-감시자 쌍
r2	-	검사할 두 번째 요소 범위
comp	-	투영된 요소에 적용할 비교 함수
proj1	-	첫 번째 요소 범위에 적용할 투영
proj2	-	두 번째 요소 범위에 적용할 투영

반환값

true 첫 번째 범위가 두 번째 범위보다 사전순으로 작은 경우.

복잡도

최대 $2\cdotmin(N1, N2)$ 번의 비교 연산과 해당 프로젝션 연산이 수행되며, 여기서 N1 = ranges:: distance ( first1, last1 ) 이고 N2 = ranges:: distance ( first2, last2 ) 입니다.

가능한 구현

struct lexicographical_compare_fn
{
    template<std::input_iterator I1, std::sentinel_for<I1> S1,
             std::input_iterator I2, std::sentinel_for<I2> S2,
             class Proj1 = std::identity, class Proj2 = std::identity,
             std::indirect_strict_weak_order<
                 std::projected<I1, Proj1>,
                 std::projected<I2, Proj2>> Comp = ranges::less>
    constexpr bool operator()(I1 first1, S1 last1, I2 first2, S2 last2,
                              Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}) const
    {
        for (; (first1 != last1) && (first2 != last2); ++first1, (void) ++first2)
        {
            if (std::invoke(comp, std::invoke(proj1, *first1), std::invoke(proj2, *first2)))
                return true;
            if (std::invoke(comp, std::invoke(proj2, *first2), std::invoke(proj1, *first1)))
                return false;
        }
        return (first1 == last1) && (first2 != last2);
    }
    template<ranges::input_range R1, ranges::input_range R2,
             class Proj1 = std::identity, class Proj2 = std::identity,
             std::indirect_strict_weak_order<
                 std::projected<ranges::iterator_t<R1>, Proj1>,
                 std::projected<ranges::iterator_t<R2>, Proj2>> Comp = ranges::less>
    constexpr bool operator()(R1&& r1, R2&& r2, Comp comp = {},
                              Proj1 proj1 = {}, Proj2 proj2 = {}) const
    {
        return (*this)(ranges::begin(r1), ranges::end(r1),
                       ranges::begin(r2), ranges::end(r2),
                       std::ref(comp), std::ref(proj1), std::ref(proj2));
    }
};
inline constexpr lexicographical_compare_fn lexicographical_compare;

예제

이 코드 실행

#include <algorithm>
#include <iostream>
#include <iterator>
#include <random>
#include <vector>
int main()
{
    std::vector<char> v1 {'a', 'b', 'c', 'd'};
    std::vector<char> v2 {'a', 'b', 'c', 'd'};
    namespace ranges = std::ranges;
    auto os = std::ostream_iterator<char>(std::cout, " ");
    std::mt19937 g {std::random_device {}()};
    while (not ranges::lexicographical_compare(v1, v2))
    {
        ranges::copy(v1, os);
        std::cout << ">= ";
        ranges::copy(v2, os);
        std::cout << '\n';
        ranges::shuffle(v1, g);
        ranges::shuffle(v2, g);
    }
    ranges::copy(v1, os);
    std::cout << "<  ";
    ranges::copy(v2, os);
    std::cout << '\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

참고 항목

ranges::equal (C++20)	두 원소 집합이 동일한지 판별 (알고리즘 함수 객체)
lexicographical_compare	한 범위가 다른 범위보다 사전순으로 작으면 true 반환 (함수 템플릿)

Compiler support
Freestanding and hosted
Language
Standard library
Standard library headers
Named requirements
Feature test macros (C++20)
Language support library
Concepts library (C++20)
Diagnostics library
Memory management library
Metaprogramming library (C++11)
General utilities library
Containers library
Iterators library
Ranges library (C++20)
Algorithms library
Strings library
Text processing library
Numerics library
Date and time library
Input/output library
Filesystem library (C++17)
Concurrency support library (C++11)
Execution control library (C++26)
Technical specifications
Symbols index
External libraries

cppreference.net

Namespaces

Variants

std::ranges:: lexicographical_compare

목차

매개변수

반환값

복잡도

가능한 구현

예제

참고 항목