📌 map

연관 컨테이너 (associative container) 중 하나로, 레드 - 블랙 트리 를 기반으로 구현되어 있다.
map의 각 노드들은 key와 value 쌍으로 이루어져 있으며, key의 중복을 허용하지 않는다.
원소 삽입 시 자동으로 정렬되며, 기본적으로 key 값을 기준으로 오름차순 정렬을 지원한다.
검색이나 순회 시, key 값을 이용하여 값을 얻어낸다.

💿 선언 방법

1. 비어 있는 map을 생성하는 경우 : map <데이터 타입> 이름;
2. 기존 map의 모든 요소들을 복사하여 생성하는 경우 : `map <데이터 타입> 이름 (복사할 map의 이름);
3. 기존 map의 특정 범위 요소를 복사하여 생성하는 경우 : map <데이터 타입> 이름 (복사할 맵의 시작 반복자, 복사할 맵의 끝 반복자);

💿 시간 복잡도

1. 임의의 원소에 접근하는 경우 : O(logN)
2. 특정 원소를 검색하는 경우 : O(logN)
3. 원소를 삽입 / 삭제하는 경우 : O(logN)

💿 장 / 단점

• 장점

1. 데이터 검색, 삽입, 삭제가 빠르다.
2. 데이터의 중복을 방지할 수 있다.
3. key 값을 통한 랜덤 액세스와 iterator를 통한 접근 모두 가능하다.

• 단점

1. 데이터를 삽입, 삭제할 때 정렬을 유지하기 위한 추가적인 작업이 필요하다.

📌 unordered_map

자동으로 정렬을 지원하지 않는 map이다.
해쉬 테이블을 기반으로 구현되어 있다.

💿 시간 복잡도

1. 임의의 원소에 접근하는 경우 : O(1)
2. 특정 원소를 검색하는 경우 : O(1)
3. 원소를 삽입 / 삭제하는 경우 : O(1)

💿 장 / 단점

• 장점

1. 데이터가 많은 경우, map보다 월등히 좋은 성능을 가진다.

• 단점

1. 데이터가 적은 경우, 메모리 낭비와 검색 시 오버헤드가 발생하게 된다.

이러한 장단점 때문에 unordered_map은 대용량의 데이터를 관리할 경우 사용하기 적합하다.

📌 multimap

key 값의 중복을 허용하는 map이다.
map과 다르게 operator [] 를 사용해서 원소 (pair <key, value>)의 추가 또는 수정이 불가능하다.

---

이미지 출처

map 이미지 출처
unordered_map 이미지 출처
multimap 이미지 출처