📄 map
- Key-Value 쌍(Pair)으로 이루어진 트리(Tree) 구조
- Key의 중복을 허용하지 않음
- 자료를 저장할 때 내부에서 자동으로 Key를 오름차순 정렬 (0, 1, 2, ⋯)
📄 unordered_map
- map보다 더 빠른 탐색을 위해 Hash table로 구현한 자료구조
- Key의 중복을 허용하지 않음
- 자료를 저장할 때 정렬하지 않음
- 저장된 자료가 많으면 map에 비해 좋은 성능을 보이나, 저장된 자료가 적을 때는 메모리 낭비와 검색 시 오버헤드가 발생
- map의 시간복잡도는 Binary search tree로 탐색 시 O(log n)
- unordered_map의 시간복잡도는 O(1)
- vector나 list가 unordered_map 보다는 빠름
이미지 출처
노력하는 게임 개발자