이 글에서는 C++ STL에서 multimap::upper_bound() 함수의 동작 방식, 문법, 그리고 실제 사용 예제에 대해 자세히 알아보겠습니다.
C++ STL에서 Multimap(멀티맵)이란?
멀티맵(Multimap)은 맵(map) 컨테이너와 유사한 연관 컨테이너입니다. 키(key)와 매핑된 값(mapped value)의 조합으로 이루어진 요소들을 특정 순서대로 저장할 수 있습니다. 일반적인 맵과 달리, 멀티맵에서는 동일한 키에 여러 개의 요소를 연결할 수 있다는 점이 특징입니다. 또한 데이터는 내부적으로 항상 키를 기준으로 정렬되어 관리됩니다.
multimap::upper_bound()란?
multimap::upper_bound() 함수는 C++ STL에 내장된 함수로, <map> 헤더 파일에 정의되어 있습니다. 이 함수는 멀티맵 컨테이너에서 상한(upper bound)에 해당하는 위치를 가리키는 반복자(iterator)를 반환합니다. 쉽게 말해, 전달된 키 k보다 크다고 판단되는 첫 번째 요소를 가리키는 반복자를 반환합니다.
문법(Syntax)
Map_name.upper_bound(key& k);
매개변수(Parameter)
이 함수는 단 하나의 매개변수만 받습니다.
k − 검색하고자 하는 키입니다.
반환값(Return Value)
이 함수는 키 'k'보다 뒤에 온다고 간주되는 요소, 즉 키 k 다음에 위치하는 요소를 가리키는 반복자를 반환합니다.
입력 예시
map<char, int> newmap;
newmap(make_pair('a', 1));
newmap(make_pair('b', 2));
newmap(make_pair('c', 3));
newmap.upper_bound(b);출력 결과
c:3
실전 예제
#include <bits/stdc++.h>
using namespace std;
int main(){
// 멀티맵 생성
multimap<int, int> mul;
mul.insert({ 2, 10 });
mul.insert({ 1, 20 });
mul.insert({ 1, 30 });
mul.insert({ 3, 40 });
mul.insert({ 3, 50 });
mul.insert({ 4, 60 });
// 키 1의 상한(upper bound)
auto i = mul.upper_bound(1);
cout << "Upper bound of key 1 is: ";
cout << (*i).first << " "<<(*i).second << endl;
// 키 2의 상한(upper bound)
i = mul.upper_bound(2);
cout << "Upper bound of key 2 is: ";
cout << (*i).first << " " <<(*i).second << endl;
// 키 3의 상한(upper bound)
i = mul.upper_bound(3);
cout << "Upper bound of key 3 is: ";
cout << (*i).first << " " << (*i).second << endl;
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Upper bound of key 1 is: 2 10 Upper bound of key 2 is: 3 40 Upper bound of key 3 is: 4 60
결과 해설
결과를 살펴보면 그 동작 원리를 더 명확하게 이해할 수 있습니다.
키 1의 경우: 키가 1인 요소는 (1,20)과 (1,30) 두 개입니다. upper_bound(1)은 키 1인 모든 요소들 바로 다음에 위치한 (2,10)을 반환합니다.
키 2의 경우: 키가 2인 요소는 (2,10) 하나뿐이므로, 그다음에 오는 (3,40)이 반환됩니다.
키 3의 경우: 키가 3인 요소는 (3,40)과 (3,50) 두 개이며, 이들 다음에 위치한 (4,60)이 반환됩니다.
이처럼 upper_bound()는 중복 키가 존재하는 멀티맵에서 해당 키 범위의 끝을 찾거나, 특정 키보다 큰 첫 번째 요소에 접근할 때 매우 유용하게 활용됩니다.