[C++] map, multimap container 정리

map과 multimap container은 연관 컨테이너(associative container) 중 하나이다.

 

1. map, multimap container의 특징

 

• 노드 기반으로 이뤄진 균형 이진 트리 구조이다.
• 각 노드들은 <key, value>로 이뤄진 pair 객체를 가진다. (이때 map에서는 각 노드는 고유한 key 값을 가지지만, multimap은 중복된 key 값을 허용한다)
• 노드가 삽입이 되면서 key 값을 기준으로 자동으로 정렬이 이뤄진다. (default는 오름차순!)
• 저장공간의 필요에 따라서 allocator 객체를 사용한다.

2. 생성자, 연산자, 멤버함수

map과 multimap은 멤버함수가 동일하다..

 

0) 생성자

 

• map<int, int> m; - int형 key와 int형 value로 이뤄진 pair 객체를 가지는 map 생성!
• map<int, int, greater<int>> m; - int형 key와 int형 value로 pair 객체를 가지는 map을 value를 정렬 기준으로 내림차순 정렬한다. (default는 less(오름차순))
• map<int, int> m1(m2); - m2의 원소들을 복사한 m1 생성

1) 연산자

 

• m[5] = 1; - 5라는 key 값을 가지는 pair 객체의 value를 1로 변경한다! (operator [])

2)  멤버함수

 

m.begin();	m.end();	m.rbegin();	m.rend();	m.clear();
m.count(k);	m.empty();	m.insert(k); //k는 pair 객체	m.insert(iter, k);	m.erase(start, end);
m.find(k);	m2.swap(m1);	m.upper_bound(k); // k가 끝나는 구간	m.lower_bound(k); // k가 시작하는 구간	m.equal_range(k);
m.value_comp();	m.key_comp();	m.size();	m.max_size();

 

---

+ map과 multimap의 정렬에 있어서

 

기본적으로 map과 multimap의 정렬은 key 값을 기준으로 이뤄진다.

따라서 sorting by value를 위해서는 일련의 과정이 따로 필요하다.

 

std::map<int, int> m;
std::vector<std::pair<int, int>> v;

copy(m.begin(), m.end(), std::back_inserter(v));

std::sort(v.begin(), v.end());

 

위와 같이 map(multimap)의 sorting by value를 위해서는 우선 map(multimap)에 들어있는 모든 원소들을 vector로 옮기는 과정이 필요하다. (그렇지 않고선 구현하기가 까다롭다)

 

이때 단순히 copy를 사용하면 '=' 대입 연산을 사용해서 저장되기 때문에 push_back처럼 자동으로 크기를 늘려주지 않는다. 그래서 저장할 공간이 충분치 않다면 런타임에러가 발생한다.

 

따라서 반복자 어댑터 back_inserter를 통해 공간을 확보할 수 있도록 한다.

(벡터 v의 마지막 요소 다음 위치부터 순차적으로 복사하면 확장한다)