[C++ STL 프로그래밍] 맵 (Map)

http://dream-cy.tistory.com/10

1. 시퀀스 컨테이너와 연관 컨테이너

 - 시퀀스 컨테이너 : 순서 있게 자료를 보관하는 컨테이너 (vector, list, deque)

 - 연관 컨테이너 : key, value 형태로 짝을 이뤄 자료를 보관하는 컨테이너 (map, set)

2.Map 자료구조와 특징

  map의 자료구조는 레드 블랙 트리(red black tree)를 사용합니다. 트리는 특정 노드의 값을 기준으로 작은 값은 왼쪽 서브트리, 큰 값은 오른쪽 서브트리에 저장되어 특정 값을 찾을때 선형 자료구조보다 빠르게 찾을 수 있습니다. 트리의 노드는 깊이가 작을 수록 성능에 유리하므로 균형있게 저장되는 것이 중요합니다. 따라서 기본 트리에서 변형하여 B-, B+, AVL, 레드블랙과 같은 다양한 트리가 존재합니다.

3. Map를 사용해야 하는 경우

 - 저장된 데이터들을 정렬해야 할 경우

 - 많은 자료들을 저장하고, 특정 자료에 대해 검색을 빠르게 해야 할 경우

4. Map의 사용

- 헤더 파일

#include <map>

using namespace std;

- 형(type)

map< key 자료형, value 자료형 > 변수명

map< key 자료형, value 자료형 >::iterator 변수명

map< key 자료형, value 자료형 >::reverse_iterator 변수명

map< key 자료형, value 자료형 >::size_type 변수명

- 메소드 소개

멤버	설명
begin	첫 번째 원소의 랜덤 접근 반복자를 반환 map<int, string> m; map<int, string>::iterator i; m.insert( map<int, string>::value_type(1, "Hello") ); m.insert( map<int, string>::value_type(2, "World") ); m.insert( map<int, string>::value_type(3, "Diary") ); for(i=m.begin(); i!=m.end(); i++)     cout << i->second << endl;
end	마지막 원소 다음의 반복자를 반환 map<int, string> m; map<int, string>::iterator i; m.insert( map<int, string>::value_type(1, "Hello") ); m.insert( map<int, string>::value_type(2, "World") ); m.insert( map<int, string>::value_type(3, "Diary") ); for(i=m.begin(); i!=m.end(); i++)     cout << i->second << endl;
rbegin	역방향으로 첫 번째 원소의 반복자를 반환 map<int, string> m; map<int, string>::reverse_iterator i; m.insert( map<int, string>::value_type(1, "Hello") ); m.insert( map<int, string>::value_type(2, "World") ); m.insert( map<int, string>::value_type(3, "Diary") ); for(i=m.rbegin(); i!=m.rend(); i++)     cout << i->second << endl;
rend	역방향으로 마지막 원소 다음의 반복자를 반환 map<int, string> m; map<int, string>::reverse_iterator i; m.insert( map<int, string>::value_type(1, "Hello") ); m.insert( map<int, string>::value_type(2, "World") ); m.insert( map<int, string>::value_type(3, "Diary") ); for(i=m.rbegin(); i!=m.rend(); i++)     cout << i->second << endl;
insert	원소 추가 map<int, string> m; m.insert( map<int, string>::value_type(1, "Hello"); m.insert( pair<int, string>(2, "World") );
find	key와 연관된 원소의 반복자 반환 map<int, string> m; m.insert( map<int, string>::value_type(1, "Hello") ); m.insert( map<int, string>::value_type(2, "World") ); m.insert( map<int, string>::value_type(3, "Diary") ); cout << m.find(1)->second; // Hello 출력
lower_bound	지정한 key의 요소를 가지고 있다면 해당 위치의 반복자를 반환 map<int, string> m; m.insert( map<int, string>::value_type(1, "Hello") ); m.insert( map<int, string>::value_type(2, "World") ); m.insert( map<int, string>::value_type(3, "Diary") ); for(i=m.lower_bound(1); i!=m.upper_bound(3); i++)     cout << i->second << endl; // 1~3 key 값의 원소 모두 출력
upper_bound	지정한 key의 요소를 가지고 있다면 해당 위치 다음 위치의 반복자 반환 map<int, string> m; m.insert( map<int, string>::value_type(1, "Hello") ); m.insert( map<int, string>::value_type(2, "World") ); m.insert( map<int, string>::value_type(3, "Diary") ); for(i=m.lower_bound(1); i!=m.upper_bound(3); i++)     cout << i->second << endl; // 1~3 key 값의 원소 모두 출력
clear	저장하고 있는 모든 원소를 삭제 map<int, string> m; m.insert( map<int, string>::value_type(1, "Hello") ); m.insert( map<int, string>::value_type(2, "World") ); m.insert( map<int, string>::value_type(3, "Diary") ); m.clear(); // 모든 원소 삭제
erase	특정 위치의 원소나 지정 범위의 원소들을 삭제 map<int, string> m; m.insert( map<int, string>::value_type(1, "Hello") ); m.insert( map<int, string>::value_type(2, "World") ); m.insert( map<int, string>::value_type(3, "Diary") ); m.erase( m.begin() ); // 1번 원소 삭제 m.erase( m.find(2), m.find(3) ); // 2번 원소만 삭제됨 (2이상 3 미만)
size	원소의 개수를 반환 map<int, string> m; m.insert( map<int, string>::value_type(1, "Hello") ); m.insert( map<int, string>::value_type(2, "World") ); m.insert( map<int, string>::value_type(3, "Diary") ); m.size(); // 3
empty	비어있는지 확인 if(!m.empty())     cout << "map is not empty" << endl;
operator[]	지정한 key값으로 원소 추가 및 접근 map<int, string> m; m[1] = "Hello"; m[2] = "World"; m[3] = "Diary";