C++ STL multiset upper_bound() 함수란?
이 튜토리얼에서는 C++ STL의 multiset(멀티셋) 컨테이너에서 제공하는 upper_bound() 함수의 동작 방식과 사용법을 실제 예제와 함께 자세히 살펴보겠습니다.
upper_bound() 함수는 매개변수로 전달된 키(key) 값보다 큰 첫 번째 요소를 가리키는 반복자(iterator)를 반환합니다. 만약 그보다 큰 요소가 컨테이너에 존재하지 않는다면, 컨테이너의 마지막 요소를 가리키는 반복자를 반환합니다.
multiset은 중복 값을 허용하는 정렬된 연관 컨테이너입니다. 따라서 동일한 값이 여러 개 저장되어 있어도 upper_bound()는 해당 키보다 큰 값 중 가장 앞에 있는 요소를 정확히 찾아내며, 시간 복잡도는 O(log n)으로 매우 효율적입니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
int main(){
multiset<int> s;
s.insert(1);
s.insert(3);
s.insert(3);
s.insert(5);
s.insert(4);
cout << "multiset의 요소들: ";
for (auto it = s.begin(); it != s.end(); it++)
cout << *it << " ";
auto it = s.upper_bound(3);
cout << "\n키 3의 upper bound: ";
cout << (*it) << endl;
it = s.upper_bound(2);
cout << "키 2의 upper bound: ";
cout << (*it) << endl;
it = s.upper_bound(10);
cout << "키 10의 upper bound: ";
cout << (*it) << endl;
return 0;
}
실행 결과
multiset의 요소들: 1 3 3 4 5 키 3의 upper bound: 4 키 2의 upper bound: 3 키 10의 upper bound: 5
결과 분석
- upper_bound(3) → 3보다 큰 첫 번째 요소인 4를 반환합니다. multiset에는 3이 두 개 저장되어 있지만, 이 함수는 키와 같은 값은 건너뛰고 더 큰 값만 찾습니다.
- upper_bound(2) → 2보다 큰 첫 번째 요소인 3을 반환합니다.
- upper_bound(10) → 10보다 큰 요소가 존재하지 않으므로, 컨테이너의 마지막 요소인 5를 반환합니다.
이처럼 upper_bound()는 특정 값을 기준으로 데이터 범위를 다룰 때 매우 유용하며, lower_bound()와 함께 사용하면 구간 검색(range query)도 손쉽게 구현할 수 있습니다.