algorithm_equal_range
algorithm_equal_range (동등 범위 찾기)
std::equal_range는 파티셔닝된 정렬 범위에서 value와 동등한 모든 요소를 포함하는 하위 범위를 찾아 (시작, 끝) 반복자 쌍으로 돌려줘요. 정렬된 범위에서 이진 탐색을 수행해요.
출처: cppreference
본문
std::equal_range는 파티셔닝된 소스 범위 [first, last)에서 value와 동등한 요소를 모두 포함하는 범위를 찾아요. 어떤 요소는 value보다 앞서지도 않고 뒤서지도 않을 때 value와 동등하다고 간주돼요. <algorithm> 헤더에 정의되어 있어요.
template< class ForwardIt, class T >
std::pair<ForwardIt, ForwardIt>
equal_range( ForwardIt first, ForwardIt last, const T& value );
template< class ForwardIt, class T, class Compare >
std::pair<ForwardIt, ForwardIt>
equal_range( ForwardIt first, ForwardIt last,
const T& value, Compare comp );
- 1번 오버로드 — 순서는
operator<(즉std::less{})로 결정돼요. - 2번 오버로드 — 순서는 비교 함수
comp로 결정돼요.
두 경우 모두 요소들이 두 비교 표현식에 대해 동시에 파티셔닝되어 있어야 해요.
반환값 (Return value)
std::pair 객체를 돌려줘요:
first—value보다 앞서지 않는 첫 번째 요소를 가리키는 반복자 (없으면last)second—value보다 뒤서는 첫 번째 요소를 가리키는 반복자 (없으면last)
복잡도 (Complexity)
N을 std::distance(first, last)라고 하면 2·log₂(N) + 𝓞(1)번 이하의 비교가 필요해요.
참고 (Notes)
std::equal_range는 std::lower_bound와 std::upper_bound를 합친 결과를 돌려줘요. operator<(또는 comp)가 비대칭이어야 해서 a < b와 b < a가 항상 다른 결과를 내야 해요.
ForwardIt이 RandomAccessIterator가 아니면 반복자 증가 횟수가 선형이 돼요. 특히 std::set·std::multiset 반복자는 랜덤 접근이 아니므로, 멤버 함수 std::set::equal_range(또는 std::multiset::equal_range)를 쓰는 게 좋아요.
예제 (Example)
#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';
}
출력:
Compare using S::operator<(): B C D
Using heterogeneous comparison: B C D