std::equal_range

헤더 `<algorithm>`
template< class ForwardIt, class T > std::pair<ForwardIt, ForwardIt> equal_range( ForwardIt first, ForwardIt last, const T& value );	에 정의됨 (1)	(C++26까지) (C++20부터 constexpr)
template< class ForwardIt, class T = typename std::iterator_traits <ForwardIt>::value_type > constexpr std::pair<ForwardIt, ForwardIt> equal_range( ForwardIt first, ForwardIt last, const T& value );	에 정의됨 (1)		(C++26부터)
template< class ForwardIt, class T, class Compare > std::pair<ForwardIt, ForwardIt> equal_range( ForwardIt first, ForwardIt last, const T& value, Compare comp );	(2)	(C++26까지) (C++20부터 constexpr)
template< class ForwardIt, class T = typename std::iterator_traits <ForwardIt>::value_type, class Compare > constexpr std::pair<ForwardIt, ForwardIt> equal_range( ForwardIt first, ForwardIt last, const T& value, Compare comp );	(2)		(C++26부터)

분할된 범위 value에서 [first, last)와(과) 동등한 모든 요소를 포함하는 범위를 반환합니다.

1) 동등성은 operator<을(를) 사용하여 확인됩니다.

std::lower_bound(first, last, value) 및 std::upper_bound(first, last, value)의 결과를 반환합니다.

다음 조건 중 하나라도 만족하면 동작은 정의되지 않습니다.

elem가 [first, last)의 요소인 경우, bool(elem < value)이(가) !bool(value < elem)을(를) 의미하지 않습니다.
elem이(가) [first, last)의 요소인 경우, 분할되지 않았습니다. 표현식 bool(elem < value) 및 !bool(value < elem)에 대해.

(C++20까지)

std::equal_range(first, last, value, std::less{})와(과) 동일합니다.

(C++20부터)

2) 동등성은 comp을(를) 사용하여 확인됩니다.

std::lower_bound(first, last, value, comp) 및 std::upper_bound(first, last, value, comp)의 결과를 반환합니다.

다음 조건 중 하나라도 만족하면 동작은 정의되지 않습니다.

elem가 [first, last)의 요소인 경우, bool(comp(elem, value))이(가) !bool(comp(value, elem))을(를) 의미하지 않습니다.
elem이(가) [first, last)의 요소인 경우, 분할되지 않았습니다. 표현식 bool(comp(elem, value)) 및 !bool(comp(value, elem))에 대해.

매개변수

first, last	-	검사할 분할된 범위의 요소를 정의하는 반복자 쌍
value	-	요소와 비교할 값
comp	-	첫 번째 인수가 두 번째 인수보다 앞서 정렬되면 `true`을(를) 반환하는 이항 술어. 술어 함수의 시그니처는 다음과 동등해야 합니다. `bool pred(const Type1 &a, const Type2 &b);` 시그니처에 `const &`이(가) 필요하지는 않지만, 함수는 전달된 객체를 수정해서는 안 되며 모든 (const일 수 있는) `Type1` 및 `Type2` 유형의 값을 값 범주에 관계없이 받아들일 수 있어야 합니다(따라서 `Type1 &`는 허용되지 않으며, `Type1`도 `Type1`의 경우 이동이 복사와 동일하지 않은 한 허용되지 않습니다(C++11부터)). 유형 `Type1` 및 `Type2`은(는) `T` 유형의 객체가 `Type1` 및 `Type2` 모두로 암시적으로 변환될 수 있고, `ForwardIt` 유형의 객체를 역참조한 후 `Type1` 및 `Type2` 모두로 암시적으로 변환될 수 있어야 합니다.
유형 요구 사항
- `ForwardIt`은(는) LegacyForwardIterator의 요구 사항을 충족해야 합니다.
- `Compare`은(는) BinaryPredicate의 요구 사항을 충족해야 합니다. Compare를 충족할 필요는 없습니다.

반환값

반복자 쌍을 포함하는 std::pair이며, 여기서

first은(는) [first, last) 범위에서 value보다 앞서 정렬되지 않은 첫 번째 요소를 가리키는 반복자입니다(그러한 요소가 없으면 last). 그리고
second은(는) [first, last) 범위에서 value보다 뒤에 정렬된 첫 번째 요소를 가리키는 반복자입니다(그러한 요소가 없으면 last).

복잡도

$\scriptsize N$ $N$ 이(가) std::distance(first, last)인 경우:

1) 최대

2log 2 (N)+O(1)

번의 비교 (value 사용 시)operator<(C++20까지)std::less{}(C++20부터).

2) 최대

2log 2 (N)+O(1)

번의 비교자 comp 적용.

단, ForwardIt이(가) LegacyRandomAccessIterator가 아닌 경우 반복자 증가 횟수는 $\scriptsize N$ $N$ 에 선형입니다. 특히 std::set 및 std::multiset 반복자는 임의 접근이 아니므로, 해당 멤버 함수 std::set::equal_range (또는 std::multiset::equal_range)를 사용하는 것이 좋습니다.

참고

std::equal_range은(는) [first, last)이(가) 분할되어야 한다는 것만 요구하지만, 이 알고리즘은 일반적으로 [first, last)이(가) 정렬된 경우에 사용되므로 모든 value에 대해 이진 탐색이 유효합니다.

std::lower_bound 및 std::upper_bound의 요구 사항 외에도, std::equal_range은(는) operator< 또는 comp이(가) 비대칭적이어야 합니다(즉, a < b와 b < a의 결과가 항상 다릅니다).

따라서 이진 탐색의 중간 결과는 std::lower_bound와 std::upper_bound에서 공유될 수 있습니다. 예를 들어 std::lower_bound 호출의 결과를 first의 인수로 사용하여 std::upper_bound 호출에 사용할 수 있습니다.

기능 테스트 매크로	값	Std	기능
`__cpp_lib_algorithm_default_value_type`	`202403`	(C++26)	알고리즘을 위한 초기화 리스트 (1,2)

가능한 구현

equal_range (1)

template<class ForwardIt,
         class T = typename std::iterator_traits<ForwardIt>::value_type>
constexpr std::pair<ForwardIt, ForwardIt> 
    equal_range(ForwardIt first, ForwardIt last, const T& value)
{
    return std::equal_range(first, last, value, std::less{});
}

equal_range (2)

template<class ForwardIt,
         class T = typename std::iterator_traits<ForwardIt>::value_type,
         class Compare>
constexpr std::pair<ForwardIt, ForwardIt>
    equal_range(ForwardIt first, ForwardIt last, const T& value, Compare comp)
{
    return std::make_pair(std::lower_bound(first, last, value, comp),
                          std::upper_bound(first, last, value, comp));
}

예제

이 코드 실행

#include <algorithm>
#include <complex>
#include <iostream>
#include <vector>

struct S
{
    int number;
    char name;
    // note: name is ignored by this comparison operator
    bool operator<(const S& s) const { return number < s.number; }
};

struct Comp
{
    bool operator()(const S& s, int i) const { return s.number < i; }
    bool operator()(int i, const S& s) const { return i < s.number; }
};

int main()
{
    // note: not ordered, only partitioned w.r.t. S defined below
    const std::vector<S> vec{{1, 'A'}, {2, 'B'}, {2, 'C'},
                             {2, 'D'}, {4, 'G'}, {3, 'F'}};
    const S value{2, '?'};
    
    std::cout << "Compare using S::operator<(): ";
    const auto p = std::equal_range(vec.begin(), vec.end(), value);
    
    for (auto it = p.first; it != p.second; ++it)
        std::cout << it->name << ' ';
    std::cout << '\n';
    
    std::cout << "Using heterogeneous comparison: ";
    const auto p2 = std::equal_range(vec.begin(), vec.end(), 2, Comp{});
    
    for (auto it = p2.first; it != p2.second; ++it)
        std::cout << it->name << ' ';
    std::cout << '\n';

    using CD = std::complex<double>;
    std::vector<CD> nums{{1, 0}, {2, 2}, {2, 1}, {3, 0}, {3, 1}};
    auto cmpz = [](CD x, CD y) { return x.real() < y.real(); };
    #ifdef __cpp_lib_algorithm_default_value_type
        auto p3 = std::equal_range(nums.cbegin(), nums.cend(), {2, 0}, cmpz);
    #else
        auto p3 = std::equal_range(nums.cbegin(), nums.cend(), CD{2, 0}, cmpz);
    #endif

    for (auto it = p3.first; it != p3.second; ++it)
        std::cout << *it << ' ';
    std::cout << '\n';
}

출력:

Compare using S::operator<(): B C D 
Using heterogeneous comparison: B C D
(2,2) (2, 1)

결함 보고서

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

DR	적용 대상	게시된 동작	올바른 동작
LWG 270	C++98	`Compare`이(가) Compare`T`를 충족해야 하고 LessThanComparable이어야 합니다 (엄격한 약순서 필요)	분할만 필요; 이기종 비교 허용
LWG 384	C++98	최대 $\scriptsize 2\log_{2}(N)+1$ $2log 2 (N)+1$ 번의 비교 가 허용되었으며, 이는 구현 불가능합니다^[1]	$\scriptsize 2\log_{2}(N)+O(1)$ $2log 2 (N)+O(1)$

로 수정됨↑ equal_range을(를) 단일 요소 범위에 적용하려면 2번의 비교가 필요하지만, 복잡도 요구 사항에 따라 최대 1번의 비교만 허용됩니다.

참고 항목

lower_bound	이진 탐색을 사용하여 주어진 값보다 작지 않은 첫 번째 요소를 찾습니다 (함수 템플릿 & 알고리즘 함수 객체)
ranges::lower_bound (C++20)
upper_bound	이진 탐색을 사용하여 주어진 값보다 큰 첫 번째 요소를 찾습니다 (함수 템플릿 & 알고리즘 함수 객체)
ranges::upper_bound (C++20)	이진 탐색을 사용하여 주어진 값보다 큰 첫 번째 요소를 찾습니다 (함수 템플릿 & 알고리즘 함수 객체)
binary_search	이진 탐색을 사용하여 요소가 범위에 존재하는지 확인합니다 (함수 템플릿 & 알고리즘 함수 객체)
ranges::binary_search (C++20)	이진 탐색을 사용하여 요소가 범위에 존재하는지 확인합니다 (함수 템플릿 & 알고리즘 함수 객체)
partition	요소 범위를 두 그룹으로 나눕니다 (함수 템플릿 & 알고리즘 함수 객체)
ranges::partition (C++20)	요소 범위를 두 그룹으로 나눕니다 (함수 템플릿 & 알고리즘 함수 객체)
equal	두 요소 집합이 동일한지 확인합니다 (함수 템플릿 & 알고리즘 함수 객체)
ranges::equal (C++20)	두 요소 집합이 동일한지 확인합니다 (함수 템플릿 & 알고리즘 함수 객체)
equal_range	특정 키와 일치하는 요소의 범위를 반환합니다 (`std::set<Key,Compare,Allocator>`의 공개 멤버 함수)
equal_range	특정 키와 일치하는 요소의 범위를 반환합니다 (`std::multiset<Key,Compare,Allocator>`의 공개 멤버 함수)
ranges::equal_range (C++20)	이진 탐색을 사용하여 주어진 값과 일치하는 요소의 범위를 찾습니다 (알고리즘 함수 객체)

[1] 로 수정됨↑ equal_range을(를) 단일 요소 범위에 적용하려면 2번의 비교가 필요하지만, 복잡도 요구 사항에 따라 최대 1번의 비교만 허용됩니다.

[1]

컴파일러 지원
프리스탠딩 및 호스티드
언어
표준 라이브러리
표준 라이브러리 헤더
명명된 요구 사항
기능 테스트 매크로 (C++20)
언어 지원 라이브러리
개념 라이브러리 (C++20)
진단 라이브러리
메모리 관리 라이브러리
메타프로그래밍 라이브러리 (C++11)
일반 유틸리티 라이브러리
컨테이너 라이브러리
반복자 라이브러리
Ranges 라이브러리 (C++20)
알고리즘 라이브러리
문자열 라이브러리
텍스트 처리 라이브러리
수치 라이브러리
날짜 및 시간 라이브러리
입출력 라이브러리
파일 시스템 라이브러리 (C++17)
동시성 지원 라이브러리 (C++11)
실행 제어 라이브러리 (C++26)
기술 사양
기호 인덱스
외부 라이브러리

ko.cppreference.net

Namespaces

Variants

std::equal_range

목차

매개변수

반환값

복잡도

참고

가능한 구현

예제

결함 보고서

참고 항목