이 글에서는 C++ STL의 multiset 컨테이너에서 제공하는 lower_bound() 함수가 어떻게 동작하는지 예제 코드를 통해 자세히 살펴보겠습니다.
lower_bound() 함수란?
lower_bound()는 multiset 내부에서 전달된 키(key) 값과 같은 첫 번째 원소를 가리키는 반복자(iterator)를 반환합니다. 만약 해당 값과 일치하는 원소가 존재하지 않는다면, 그 값보다 큰 첫 번째 원소를 가리킵니다.
즉, 항상 정렬된 상태를 유지하는 multiset에서 "특정 값 이상인 원소 중 가장 앞쪽에 있는 위치"를 찾을 때 유용하게 활용할 수 있습니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
int main(){
multiset<int> s;
s.insert(1);
s.insert(2);
s.insert(2);
s.insert(1);
s.insert(4);
cout << "The multiset elements are: ";
for (auto it = s.begin(); it != s.end(); it++)
cout << *it << " ";
auto it = s.lower_bound(2);
cout << "\nThe lower bound of key 2 is ";
cout << (*it) << endl;
it = s.lower_bound(3);
cout << "The lower bound of key 3 is ";
cout << (*it) << endl;
it = s.lower_bound(7);
cout << "The lower bound of key 7 is ";
cout << (*it) << endl;
return 0;
}
실행 결과
The multiset elements are: 1 1 2 2 4 The lower bound of key 2 is 2 The lower bound of key 3 is 4 The lower bound of key 7 is 5
결과 분석
- 키 2 → 결과 2: multiset에 값 2가 이미 존재하므로, 해당 값을 가리키는 반복자를 그대로 반환합니다.
- 키 3 → 결과 4: 값 3은 컨테이너에 없기 때문에, 3보다 큰 첫 번째 원소인 4를 반환합니다.
- 키 7 → 결과 5: 7 이상의 원소가 컨테이너에 존재하지 않으므로
s.end()반복자가 반환됩니다. 이를 역참조(*it)하면 정의되지 않은 동작(undefined behavior)이 발생하며, 출력된 '5'는 실제 의미 없는 쓰레기 값입니다.
주의 사항
lower_bound()의 결과가 s.end()와 같은지 반드시 먼저 확인한 후 역참조해야 안전합니다. 또한, 같은 값보다 큰 원소의 위치가 필요하다면 upper_bound() 함수를 함께 활용하면 좋습니다. 두 함수 모두 내부적으로 이진 탐색 기반으로 동작하기 때문에 O(log n)의 시간 복잡도를 가집니다.