[C++/STL] - multimap

1. multimap 이란

multimap은 C++ STL의 연관 컨테이너 중 하나이다. 이 컨테이너는 map과 유사하지만, key값이 중복될 수 있다는 점이 다르다.

2. 특징

multimap은 균형 이진 트리(중위순회)로 구현되어 있으며, key와 value의 쌍(pair)으로 이루어진 원소들의 집합으로 이루어져 있다. multimap은 기본적으로 key값을 기준으로 오름차순으로 정렬된다.

3. 장단점

장점 :

• key값이 중복될 수 있어서, 같은 key값을 가지는 여러 개의 원소를 저장할 수 있다.
• key값에 따라 자동으로 정렬되어 있어서, 검색과 정렬에 용이하다.
• multimap의 원소를 삽입하거나 삭제하는 과정에서, 다른 원소들의 위치는 변경되지 않는다.

단점 :

• multimap은 map보다 메모리를 더 많이 차지한다.
• multimap의 원소를 검색하는 과정에서, 검색 시간이 더 오래 걸릴 수 있다.

4. 시간복잡도

1. 접근 - O(log n)
2. 검색 - O(log n)
3. 삽입 및 삭제 - O(log n)
   multimap이 균형 이진 트리로 구현되어 있기 때문이다. 따라서 multimap의 원소 접근, 검색, 삽입, 삭제의 시간복잡도는 모두 O(log n)이다.

5. 사용법

1) 초기화

multimap<int, string> myMultimap;
// 기본 생성자: 비어있는 multimap을 생성한다.

myMultimap.insert(make_pair(1, "One"));
myMultimap.insert(make_pair(2, "Two"));
myMultimap.insert(make_pair(3, "Three"));
// pair를 이용한 삽입: make_pair() 함수를 이용하여 key와 value를 가지는 pair를 만들어 multimap에 삽입한다.

multimap<int, string> myMultimap = {{1,"One"}, {2,"Two"}, {3,"Three"}};
// 초기화 리스트를 이용한 삽입: 초기화 리스트를 이용하여 multimap을 초기화할 수 있다.

multimap<int, string> myMultimap1 = {{1,"One"}, {2,"Two"}};
multimap<int, string> myMultimap2(myMultimap1);
// 다른 multimap을 이용한 삽입: 다른 multimap을 이용하여 multimap을 초기화할 수 있다.

2) 멤버 함수

map의 멤버함수를 모두 포함하고 있으며 추가된 멤버함수가 있다.
equal_range(key): multimap에서 key값과 일치하는 원소들의 범위를 pair로 반환한다.