C++ STL multimap::lower_bound() 함수 완벽 가이드

이 글에서는 C++ STL에서 multimap::lower_bound() 함수의 동작 원리, 문법, 그리고 실제 예제까지 자세히 알아보겠습니다.

C++ STL에서 Multimap이란?

Multimap은 map 컨테이너와 유사한 연관 컨테이너(associative container)입니다. 키(key)와 매핑된 값(mapped value)의 조합으로 이루어진 요소들을 특정 순서대로 저장합니다. 일반적인 map과 달리 multimap에서는 동일한 키를 가진 여러 개의 요소를 저장할 수 있으며, 데이터는 내부적으로 항상 키를 기준으로 정렬된 상태로 유지됩니다.

multimap::lower_bound()란?

multimap::lower_bound()는 C++ STL의 내장 함수로, <map> 헤더 파일에 정의되어 있습니다. 이 함수는 multimap 컨테이너에서 전달된 키 k보다 작지 않은(즉, 크거나 같은) 첫 번째 요소를 가리키는 반복자(iterator)를 반환합니다.

문법(Syntax)

multi.lower_bound(key& k);

매개변수(Parameter)

이 함수는 단 하나의 매개변수만 받습니다.

• k − 검색하려는 대상 키입니다.

반환값(Return Value)

이 함수는 키 k보다 크거나 같은 값을 가진 첫 번째 요소를 가리키는 반복자를 반환합니다. 조건에 맞는 요소가 존재하지 않으면 end() 반복자를 반환합니다.

입력 예시:

multimap<char, int> newmap;
newmap.insert(make_pair('a', 1));
newmap.insert(make_pair('b', 2));
newmap.insert(make_pair('c', 3));
newmap.lower_bound('b');

출력 결과:

b:2

예제 코드

#include <bits/stdc++.h>
using namespace std;

int main(){
    // multimap 생성
    multimap<int, int> mul;
    mul.insert({ 2, 10 });
    mul.insert({ 1, 20 });
    mul.insert({ 1, 30 });
    mul.insert({ 3, 40 });
    mul.insert({ 3, 50 });
    mul.insert({ 4, 60 });

    // 키 1의 lower bound 조회
    auto i = mul.lower_bound(1);
    cout << "키 1의 lower bound: ";
    cout << (*i).first << " " << (*i).second << endl;

    // 키 2의 lower bound 조회
    i = mul.lower_bound(2);
    cout << "키 2의 lower bound: ";
    cout << (*i).first << " " << (*i).second << endl;

    // 키 3의 lower bound 조회
    i = mul.lower_bound(3);
    cout << "키 3의 lower bound: ";
    cout << (*i).first << " " << (*i).second << endl;

    return 0;
}

실행 결과

위 코드를 실행하면 아래와 같은 결과가 출력됩니다.

키 1의 lower bound: 1 20
키 2의 lower bound: 2 10
키 3의 lower bound: 3 40

참고 사항

multimap::lower_bound()의 시간 복잡도는 O(log n)입니다. multimap이 내부적으로 균형 이진 탐색 트리 구조로 구현되어 있기 때문입니다. 또한 upper_bound()와 혼동하지 않도록 주의해야 합니다. upper_bound()는 키 k보다 엄격하게 큰 첫 번째 요소를 가리키는 반복자를 반환한다는 점에서 lower_bound()와 차이가 있습니다.