5. 맵(map)

map의 자료구조

---

map의 자료구조는 '트리(tree)'다(정확하게 말하면 트리 자료구조 중의 하나인 '레드-블랙 트리이다).

오른쪽의 트리 자료구조에서 제일 최상 위의 '5'는 루트노드(root node) 라고하며, 노드'5'와 노드'7'의 관계에서 노드'5'는 부모노드, 노드'7'은 자식노드라고 한다. 또한 노드 '12'와 노드'20'의 관계에서는 부모노드는 '12'이다. 자식이 없는 노드는 리프노드(leaf node)라고 한다.

 

 

 

트리 자료구조의 특징

---

트리는 노드를 균형이 있게 가지는 것이 성능에 유리하기 때문에 기본 트리에서 변형된 B-트리, R-트리, 레드 블랙 트리, AVL 트리등 다양한 종류의 트리 자료구조가 있다.

 

균형을 이룬 트리는 자료를 정해진 방식에 따라서 분류하여 저장하기 때문에 시퀸스(일렬로)하게 자료를 저장하는 연결 리스트에 비해서 검색이 빠르다. 그렇지만 정해진 규칙에 따라서 자료를 삽입, 삭제 해야 되기 때문에 삽입과 삭제가 간단하지 않으며 구현이 복잡하다.

 

 

 

map을 언제 사용해야 될까?

---

map은 많은 자료를 정렬하여 저장하고 있고 빠른 검색을 필요로 할 때 자주 사용한다. hash_map과 다른 부분은 map은 자료를 저장할 때 내부에서 자동으로 정렬을 하고, hash_map은 정렬하지 않는다는 것이다.

 

1. 정렬해야 한다.

2. 많은 자료를 저장하고, 검색이 빨라야 한다.

3. 빈번하게 삽입, 삭제하지 않는다.

 

 

 

map의 사용방법

---

가장 먼저 map의 헤더파일을 포함한다.

#include <map>

 

map의 사용방법.

map< Key 자료형, value 자료형 > 변수이름

map<int, int> map1;

 

value는 저장할 자료이고, key는 value를 가리키는 것이다.

 

앞에서 map은 자료를 저장할 때 정렬을 한다고 말했다. 정렬의 대상은 key를 대상으로 하며 오름차순으로 정렬한다. 그래서 내림차순으로 정렬하고 싶거나 key의 자료형이 기본형이 아닌 유저 정의형(class나, struct로 정의한 것)인 경우는 정렬 방법을 제공해야 한다.

 

내림차순으로 정렬하고 싶다면,

map<key 자료형, value 자료형, 비교 함수 > 변수이름

map<int, int, greater<int>> map1;

 

위에서 사용한 비교 함수 greater는 STL에 이미 정의되어 있는 템플릿이다.

 

대부분 사용법은 hash_map과 같다.

 

 

 

가. 주요 멤버들

---

 

 

 

 

나. 추가

---

 

 

 

 

다. 반복자 사용

---

 

 

 

 

라. 검색

---

 

 

 

 

마. 삭제

---

저장하고 있는 요소를 삭제할 때는 erase와 clear를 사용한다. erase는 특정 요소를 삭제할 때 사용하고, clear는 모든 요소를 삭제할 때 사용한다.

 

 

    

 

 

바. 정렬된 아이템 리스트 출력 예제 코드

---

 

 

출처 : Thinking About C++ STL 프로그래밍 (최홍배 지음)