정의
- Map은 연관 컨테이너(Associative Container)이다.
- Map은 각 노드가 key와 value 쌍으로 이루어진 트리이다.
기본적인 형태: map<key, value>
시간 복잡도
- 접근, 검색, 삽입, 삭제 시 평균적으로 O(logN)의 시간 복잡도를 가진다. (set와 동일)
특징
Set와의 공통점
-
Red-Black 트리 구조(균형 이진 트리 구조)로 구현되었다.
-
key 값은 중복이 허용되지 않는다.(유일성을 갖는다.)
** 중복 원소를 허용하고 싶다면 Multimap을 사용하면 된다. -
원소가 삽입되면 삽입 순서와는 상관없이 자동으로 정렬되며 기본적으론 오름차순이다. (key를 기준으로 정렬)
** 내림차순 정렬
1) map<int, int, greater>map1;
2) 데이터에 -(마이너스)를 붙여 삽입 -
저장공간의 필요에 따라서 allocator 객체 사용(동적 할당)
Set와의 차이점
- key와 value는 쌍을 이루므로 insert는 pair 객체를 인자로 받아야 한다.
장점
- key를 기준으로 데이터를 정렬하여 데이터 검색이 매우 빠르다. (list나 vector보다 탐색 속도가 빠르다.)
Set와의 공통점
- key-value 쌍으로 데이터를 저장하므로 데이터를 빠르게 삽입, 삭제할 수 있다.
- key 값은 중복될 수 없다. 이를 통해 데이터의 중복을 방지할 수 있다.
단점
- 해쉬맵(hashmap)이 아니므로 O(1)이 아니다.
Set와의 공통점
- 데이터를 삽입할 때마다 이진 탐색 트리를 재조정해야 하므로 삽입, 삭제 연산 속도가 다른 컨테이너에 비해 느리다.
참고 사이트
https://life-with-coding.tistory.com/305
https://devowen.com/386
https://velog.io/@jimojjing/CSTL-map
