Map container 정리

Map이란?

 C++의 STL에서 연관 컨테이너 중 하나인 map은 레드 블랙 트리로 구성되어 있다. 레드 블랙 트리는 자가 균형 이진 탐색 트리로 삽입과 삭제가 일어나는 경우에 자동으로 그 높이를 작게 유지하는 것이 특징이다. 이 이유는 연산 과정에서 트리의 높이가 한쪽으로 치우치는 것을 막아 시간복잡도 상의 이득을 보기 위함이다. n개의 원소가 있을 때 map은 O(log n)의 시간 복잡도로 삽입, 삭제, 검색을 할 수 있다. key값은 중복이 불가능하며 만약 동일한 key가 있는데 insert를 시도할 시 무시된다. 또한 key값은 오름차순 자동정렬되는데 정렬을 하고싶지 않다면 unordered_map(해시)를 선언해 성능을 높일 수 있다. 

선언하는 법

헤더파일에 map을 include 시켜주고, map<key값의 자료형, value값의 자료형> 컨테이너 이름 ; 이런식으로 선언해주면 된다. ex) map<string, int> student_score;

주요 메소드

1. begin(), end() : 각각 첫 번째 원소와 마지막 원소 다음의 반복자를 반환한다.   

2.  clear() : 저장하고 있는 모든 원소를 삭제한다. 

3. insert() : 원소를 추가한다.

4. find() : key와 관련된 원소의 반복자를 반환한다. (찾지 못한 경우 end()반복자 반환).

5. size() : 원소의 개수를 반환.

6. erase() : 해당 원소를 삭제.

 

사용법

1. []연산자를 이용하면 값도 넣을 수 있고 접근도 용이하다. 

 student["Alice"] += 1; //Alice라는 key값을 가진 원소의 value값에 1을 더해서 저장해라!

2. 추후 새로 알게 된 내용이 있으면 추가하기!