이 글에서는 C++ STL의 set::upper_bound() 함수에 대해 자세히 알아보겠습니다. 기본 개념부터 문법, 동작 방식, 반환 값, 그리고 실전 예제까지 차근차근 살펴봅니다.
C++ STL에서 set이란?
C++ STL의 set은 고유한(unique) 요소만을 저장하는 연관 컨테이너입니다. 각 요소의 값이 곧 식별자 역할을 하기 때문에 중복된 값을 가질 수 없습니다. 한 번 set에 추가된 값은 직접 수정할 수 없지만, 값을 제거하거나 새로운 값을 추가하는 것은 언제든 가능합니다. 내부적으로 set은 이진 탐색 트리(binary search tree) 형태로 구현되어 있어 빠른 검색과 삽입 성능을 제공합니다.
set::upper_bound()란?
upper_bound()는 C++ STL에 내장된 함수로, <set> 헤더 파일에 선언되어 있습니다. 이 함수는 인자로 전달된 값보다 큰 첫 번째 원소를 가리키는 반복자(iterator)를 반환합니다. 즉, 특정 값의 상한(upper bound) 바로 다음에 위치한 원소를 가리키는 반복자를 얻을 수 있습니다.
문법
name_of_set.upper_bound(const type_t& value);
매개변수
이 함수는 매개변수를 하나 받습니다. 상한(upper bound)을 찾고자 하는 값이 그 대상입니다.
반환 값
전달된 값보다 큰 첫 번째 원소를 가리키는 반복자를 반환합니다. 만약 해당하는 원소가 존재하지 않으면 end() 반복자를 반환합니다.
예제 1: 기본 동작
Input: set<int> myset = {1, 2, 3, 4, 5};
Myset.upper_bound(3);
Output: Upper bound = 4위 예제에서 3보다 큰 첫 번째 원소는 4이므로, upper_bound(3)은 4를 가리키는 반복자를 반환합니다.
예제 2: 실제 코드로 확인하기
#include <bits/stdc++.h>
using namespace std;
int main(){
set<int> Set;
Set.insert(9);
Set.insert(7);
Set.insert(5);
Set.insert(3);
Set.insert(1);
cout<<"Elements are : ";
for (auto i = Set.begin(); i!= Set.end(); i++)
cout << *i << " ";
auto i = Set.upper_bound(5);
cout <<"\nupper bound of 5 in the set is: ";
cout << (*i) << endl;
i = Set.upper_bound(1);
cout<<"upper bound of 1 in the set is: ";
cout << (*i) << endl;
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
upper bound of 5 in the set is: 7
upper bound of 1 in the set is: 3
set에는 {1, 3, 5, 7, 9}가 저장되어 있습니다. 5보다 큰 첫 번째 원소는 7이고, 1보다 큰 첫 번째 원소는 3이므로 위와 같은 결과가 출력됩니다.
예제 3: lower_bound()와 함께 범위 삭제하기
upper_bound()는 lower_bound()와 함께 사용하면 특정 범위의 원소를 효율적으로 처리할 수 있습니다. 아래 예제는 두 함수를 조합해 범위 내 원소를 삭제하는 방법을 보여줍니다.
#include <iostream>
#include <set>
int main (){
std::set<int> Set;
std::set<int>::iterator one, end;
for (int i=1; i<10; i++)
Set.insert(i*10);
one = Set.lower_bound (20);
end = Set.upper_bound (40);
Set.erase(one , end); // 10 20 70 80 90
std::cout<<"Elements are: ";
for (std::set<int>::iterator i = Set.begin(); i!=Set.end(); ++i)
std::cout << ' ' << *i;
std::cout << '\n';
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Elements are : 10 50 60 70 80 90
lower_bound(20)은 20을 가리키고, upper_bound(40)은 40보다 큰 첫 번째 원소인 50을 가리킵니다. 따라서 erase(one, end) 구문은 [20, 40] 범위의 원소들을 모두 삭제하게 됩니다.
마무리
set::upper_bound()는 정렬된 set 컨테이너에서 특정 값보다 큰 첫 번째 원소를 빠르게 찾을 수 있는 유용한 함수입니다. 시간 복잡도는 O(log n)으로, lower_bound()와 함께 활용하면 범위 검색, 삭제 등 다양한 작업을 효율적으로 수행할 수 있습니다.