STL::map

map 클래스

map 클래스는 이진 검색 트리 기반의 자료 구조이다. 일반적인 이진 검색 트리는 한 방향으로 쏠린 형태로 만들어져 효율성이 떨어질 수 있는데 map은 레드 트리 구조로 되어 있어서 항상 일정한 효율성을 보장한다. 레드 트리 구조는 직접 구현하기 매우 복잡해서 map 클래스를 사용한다. 

(레드 트리 구죠는 자가 균형 이진 탐색 트리)

 

map의 선언

map을 선언할 때는 key에 해당하는 자료형과 value에 해당하는 자료형을 선언한다.

map<char,int> m;
m['A'] = 2;
m.insert(make_pair('A',2));

 

 

upper_bound, lower_bound 메서드 

upper_bound : 컨테이너의 오른쪽 원소 중 기준 원소보다 큰 값중 가장 왼쪽에 있는 원소의 iterator값을 리턴한다.