C++ STL map의 equal_range() 함수 사용법과 예제

이 글에서는 C++ STL의 map 컨테이너에서 제공하는 equal_range() 함수의 개념과 실제 사용 방법을 자세히 살펴봅니다.

equal_range() 함수는 매개변수로 전달된 키와 동일한 키가 속한 컨테이너의 범위를 감싸는 반복자(iterator) 쌍(pair)을 반환합니다. 반환된 pair에서 first는 하한(lower bound)에 해당하는 요소를, second는 상한(upper bound)에 해당하는 요소를 가리킵니다.

여기서 하한은 해당 키보다 작지 않은 첫 번째 요소를 의미하고, 상한은 해당 키보다 큰 첫 번째 요소를 의미합니다. 만약 찾으려는 키가 맵에 존재하지 않는다면, 두 반복자 모두 그 키가 삽입될 수 있는 위치를 가리키게 됩니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
int main() {
    //컨테이너 초기화
    map<int, int> mp;
    mp.insert({ 4, 30 });
    mp.insert({ 1, 40 });
    mp.insert({ 6, 60 });
    pair<map<int, int>::iterator,
        map<int, int>::iterator>
        it;
    it = mp.equal_range(1);
    cout << "하한(lower bound): " << it.first->first << ":" << it.first->second;
    cout << "\n상한(upper bound): " << it.second->first << ":" << it.second->second;
    return 0;
}

실행 결과

하한(lower bound): 1:40
상한(upper bound): 4:30

코드 설명

위 예제에서는 int형 키와 값을 저장하는 map을 생성한 뒤 세 개의 데이터를 삽입했습니다. 이후 mp.equal_range(1)을 호출하여 키 1에 해당하는 범위를 구합니다.

반환된 pair의 it.first는 키 1을 가리키므로 1:40이 출력되고, it.second는 키 1 바로 다음으로 큰 키인 4를 가리키므로 4:30이 출력됩니다.

마무리

equal_range()는 lower_bound()와 upper_bound()를 한 번에 호출하는 것과 같은 역할을 합니다. 특정 키의 존재 여부를 확인하거나 같은 키를 가진 요소들의 범위를 처리할 때 유용하며, 맵의 크기 n에 대해 로그 시간 O(log n)의 시간 복잡도로 동작합니다.