equal_range
equal_range (같은 값의 구간 찾기)
정렬된 범위에서 주어진 값과 같은 원소들이 차지하는 구간을 std::pair로 반환하는 알고리즘이에요. <algorithm> 헤더에 있어요.
출처: cppreference
본문
equal_range는 정렬된 범위 [first, last)에서 value와 같은 원소들의 하한과 상한을 한 번에 구해요.
template< class ForwardIt, class T >
std::pair<ForwardIt, ForwardIt>
equal_range( ForwardIt first, ForwardIt last, const T& value ); // (1)
비교기 comp를 받는 버전도 있어요.
template< class ForwardIt, class T, class Compare >
std::pair<ForwardIt, ForwardIt>
equal_range( ForwardIt first, ForwardIt last, const T& value, Compare comp );
반환 값은 {lower_bound, upper_bound} 쌍이에요. 즉 [lower_bound, upper_bound) 구간이 value와 "같은" 원소 전체를 나타내요. value가 없으면 두 반복자는 같아지고(빈 구간) 삽입 위치를 가리켜요.
복잡도는 로그적이에요. [first, last) 크기 N에 대해 최악의 경우 2·log₂N + O(1)번의 비교를 해요.
lower_bound와 upper_bound를 각각 호출하는 것과 같은 결과를 한 번의 호출로 얻어요. binary_search가 존재 여부만 알려주는 반면, equal_range는 같은 값의 전체 구간을 알려줘서 더 풍부해요.
std::vector<int> v{1, 2, 2, 2, 3, 4};
auto [lo, hi] = std::equal_range(v.begin(), v.end(), 2);
// lo는 첫 2, hi는 마지막 2 다음을 가리킴
중복 원소의 전체 위치 파악이 필요할 때 유용해요.