이 글에서는 C++ STL의 map::lower_bound() 함수의 동작 원리, 문법, 그리고 다양한 예제를 통해 자세히 알아보겠습니다.
C++ STL에서 맵(Map)이란?
맵(map)은 연관 컨테이너(associative container)의 일종으로, 키(key)와 매핑된 값(mapped value)의 조합으로 이루어진 요소들을 특정 순서에 따라 저장할 수 있게 해 줍니다. 맵 컨테이너의 데이터는 내부적으로 항상 연관된 키를 기준으로 정렬되어 유지되며, 저장된 값들은 고유한 키를 통해서만 접근할 수 있습니다.
map::lower_bound()란 무엇인가?
map::lower_bound()는 C++ STL에 내장된 함수로, <map> 헤더 파일에 정의되어 있습니다. 이 함수는 맵 컨테이너에서 전달된 키의 하한(lower bound)에 해당하는 반복자(iterator)를 반환합니다. 즉, 키 k보다 작지 않은(크거나 같은) 키를 가진 첫 번째 요소를 가리키는 반복자를 반환합니다.
문법(Syntax)
Map_name.lower_bound(key& k);
매개변수(Parameter)
이 함수는 단 하나의 매개변수만 받습니다.
- k − 검색하고자 하는 키입니다.
반환 값(Return Value)
이 함수는 키 k보다 작지 않은 첫 번째 요소를 가리키는 반복자를 반환합니다. 만약 k와 정확히 일치하는 키가 없다면, k보다 큰 키 중 가장 작은 키를 가진 요소를 가리킵니다.
예제 1
입력
map<char, int> newmap;
newmap['a'] = 1;
newmap['b'] = 2;
newmap['c'] = 3;
newmap.lower_bound('b');
출력
b:2
키 'b'의 하한을 구하면 'b'보다 작지 않은 첫 번째 키인 'b' 자체가 선택되므로 결과는 b:2가 됩니다.
예제 2
#include <bits/stdc++.h>
using namespace std;
int main() {
map<int, int> TP_Map;
TP_Map.insert({5, 50});
TP_Map.insert({2, 30});
TP_Map.insert({1, 10});
TP_Map.insert({4, 70});
cout<<"\nTP Map is : \n";
cout << "MAP_KEY\tMAP_ELEMENT\n";
for (auto i = TP_Map.rbegin(); i!= TP_Map.rend(); i++) {
cout << i->first << "\t" << i->second << endl;
}
auto i = TP_Map.lower_bound(2);
cout << "The lower bound of key 2 is ";
cout << i->first << ": " << i->second << endl;
auto i_1 = TP_Map.lower_bound(3);
cout << "The lower bound of key 3 is ";
cout << i_1->first << " :" << i_1->second << endl;
return 0;
}
출력
TP Map is: MAP_KEY MAP_ELEMENT 5 50 4 70 2 30 1 10 The lower bound of key 2 is 2 :30 The lower bound of key 3 is 4 :70
예제 해설
위 코드에서 맵에는 키 1, 2, 4, 5가 오름차순으로 정렬되어 저장됩니다. lower_bound(2)는 키 2와 일치하는 첫 번째 요소 2:30을 반환하고, lower_bound(3)은 키 3이 존재하지 않기 때문에 3보다 큰 키 중 가장 작은 4에 해당하는 4:70을 반환합니다.
참고: upper_bound()와의 차이점
upper_bound(k)는 k보다 큰 키를 가진 첫 번째 요소를 반환하는 반면, lower_bound(k)는 k와 같은 키가 존재하면 그 요소 자체를 반환한다는 점이 다릅니다. 두 함수 모두 맵이 레드-블랙 트리(red-black tree) 기반의 정렬된 구조로 구현되어 있어 O(log n)의 시간 복잡도로 빠르게 동작합니다.