Associate Container (연관 컨테이너)의 종류
- map
- unordered_map
- multimap
- set
- multiset
- unordered_set
기본적으로 map은 key, value의 쌍의 값을 가진다. key값을 기준으로 정렬하고 unordered_map, multimap과의 차이점은 unordered_map의 경우는 정렬을 hash함수를 사용해서 하며, multimap은 map과 동일하지만 중복값을 허용할 때 사용한다.
연관 컨테이너를 사용하는 이유?
기본적으로 vector가 list보다 탐색이 빠르다고 하지만 데이터 양이 많아지면 vector의 경우도 절대 빠르다고 할 수 없다. 사실 대부분 삽입, 삭제 보다는 탐색이 더 중요하기 때문에 이러한 컨테이너들이 만들어졌다.
1. 생성
#include <map>
map<int, int> m;2. 삽입
map의 경우 pair를 인자로 받는 것을 알 수 있고, 아래와 같은 다양한 방법으로 데이터를 추가할 수 있다.
m.insert(pair<int, int>(1, 100));
m.insert({1, 100});
m.insert(make_pair(1, 100));
m[1] = 100;insert함수를 통해 데이터를 삽입할 경우 pair<map<int, int>::iterator, bool>로 반환되는데 아래와 같이 insert가 두 번 실행될 경우 삽입된 위치의 iterator와 성공여부를 반환한다.
m.insert(pair<int, int>(1, 100)); // {iterator, true} -> 삽입된 위치의 iterator반환
m.insert({1, 100}); // {iterator, false} -> 삽입하려고 했던 위치의 iterator반환3. 삭제
key값을 인자로 넣으면 int를 반환하는데 이것은 지워진 데이터의 개수이다. 기본적인 map은 중복을 허용하지 않으므로 지워졌다면 1을 반환할 것이고, 데이터가 없다면 count가 0으로 반환될 것이다.
int count = m.erase(1);
// iterator를 통해 erase
map<int,int>::iterator it = m.find(1); // 만약 찾지 못했다면 iterator == m.end()이다.
if (it != m.end())
map<int,int>::iterator eraseIt = m.erase(it);4. 탐색
map<int, int> m;
// 1000개의 데이터 삽입
for (int i = 0; i < 1000; i++)
m.insert({ i + 1, i * 100 });
// find함수를 통해 탐색
map<int, int>::iterator findIt = m.find(200);
if (findIt != m.end())
cout << findIt->second << endl;
// iterator 순회를 통한 탐색
for (map<int, int>::iterator it = m.begin(); it != m.end(); it++)
{
if (it->first == 200)
cout << it->second << endl;
}
// 임의 접근 연산자를 통한 탐색
cout << m[200] << endl;5. 임의 접근 연산자의 주의점
임의 접근 연산자의 경우 삽입과 탐색 두 가지에서 사용가능한데 정확히는 다음의 단계를 거친다.
- 있다면 데이터를 반환(변경)하고
- 없다면 데이터를 추가
만약 위 코드에서 1000개의 데이터가 삽입된 사실을 모르고 key가 1200인 데이터를 찾기 위해 임의 접근 연산자를 사용하기 위해 m[1200]에 접근할 경우 0이 출력되는 것을 확인할 수 있다. 따라서 값을 변경하거나 삽입하기 위해서는 유용하지만 탐색의 용도로는 적절하지 않다는 것을 알 수 있다.
set의 경우는 그냥 key, value값이 같은 map이라고 생각하면 된다. unoredered_시리즈를 제외하고는 내부적으로 AVL트리, 자가 균형 이진 트리를 사용하여 정렬한다.