C++ STL에서 upper_bound() 함수는 정렬된 컨테이너에서 특정 값보다 큰 첫 번째 원소를 찾는 데 사용되는 핵심 알고리즘입니다. 이 글에서는 upper_bound()의 동작 원리, 문법, 그리고 실제 활용 예제까지 자세히 살펴보겠습니다.
upper_bound()란 무엇인가?
upper_bound() 함수는 컨테이너 내에서 전달된 값(val)보다 크다고 판단되는 첫 번째 원소를 가리키는 반복자(iterator)를 반환합니다. 만약 해당하는 원소가 존재하지 않으면, 컨테이너의 끝(end)을 가리키는 반복자를 반환합니다.
이 함수는 주로 set, map, multiset, multimap과 같은 연관 컨테이너나 정렬된 배열, vector 등에서 효율적인 탐색을 위해 활용됩니다. 내부적으로 이진 탐색(binary search) 방식을 사용하기 때문에 시간 복잡도는 O(log n)으로 매우 빠릅니다.
함수 문법
iterator upper_bound (const value_type& val); const_iterator upper_bound (const value_type& val) const;
첫 번째 형태는 일반 반복자(iterator)를 반환하고, 두 번째 형태(const 버전)는 상수 객체에서 호출될 때 읽기 전용인 상수 반복자(const_iterator)를 반환합니다.
반환값
반환값은 컨테이너 내에서 val보다 크다고 간주되는 첫 번째 원소를 가리키는 반복자입니다. 예를 들어, {10, 20, 30, 40}이 저장된 set에서 upper_bound(25)를 호출하면 30을 가리키는 반복자가 반환됩니다.
활용 예제
다음 예제는 set 컨테이너에서 upper_bound()를 사용하여 특정 값을 기준으로 원소를 삭제하는 방법을 보여줍니다.
#include <iostream>
#include <set>
using namespace std;
int main () {
set<int> myset;
set<int>::iterator itup;
// 10부터 90까지 10 단위로 원소 삽입
for (int i = 1; i < 10; i++) myset.insert(i*10);
// 60보다 큰 첫 번째 원소(70)를 가리키는 반복자 반환
itup = myset.upper_bound(60);
// 해당 원소 삭제
myset.erase(itup);
cout << "myset contains:";
for (set<int>::iterator it = myset.begin(); it != myset.end(); ++it)
cout << ' ' << *it;
}실행 결과
myset contains: 10 20 30 40 50 60 80 90
코드 설명
위 예제에서 set에는 10, 20, 30, ..., 90까지 총 9개의 원소가 저장되어 있습니다. myset.upper_bound(60)을 호출하면 60보다 큰 첫 번째 원소인 70을 가리키는 반복자가 반환됩니다. 이후 erase() 함수를 통해 70이 삭제되었으므로, 최종 출력 결과에서 70만 빠진 것을 확인할 수 있습니다.
lower_bound()와의 차이점
upper_bound()와 자주 비교되는 함수로 lower_bound()가 있습니다. 두 함수의 차이는 다음과 같습니다.
- lower_bound(val): val보다 크거나 같은(≥) 첫 번째 원소를 가리킴
- upper_bound(val): val보다 큰(>) 첫 번째 원소를 가리킴
즉, val과 동일한 값이 컨테이너에 존재할 경우 lower_bound()는 그 값을 가리키지만, upper_bound()는 그 다음 원소를 가리킨다는 점이 핵심 차이입니다. 이 두 함수를 함께 사용하면 특정 값의 범위(range)를 효율적으로 구할 수 있어 코딩 테스트나 실무에서 매우 유용하게 활용됩니다.