map
map 은 기본적으로 레드블랙 트리(Red-Black Tree 이하 RB Tree) 기반으로 되어있습니다.
때문에 모든 데이터는 정렬되어 저장됩니다.
RB Tree는 검색속도가 빠른 Binary Search Tree(BST)에 Self-Balancing 기능을 추가한 것으로 AVL Tree만큼 엄격하진 않지만
O(logN)을 보장하는 수준으로 Balancing 되어지는 특징을 갖고 있습니다.
이러한 특성 때문에 입력되는 키 값의 분포가 고르지 못할 경우 balancing(node rotation)에 대한 비용이 들기 때문에
Insert / Delete 성능이 저하될 수 있습니다. (물론 최악의 경우에도 O(logN)의 성능은 보장됩니다)
unordered_map
unordered_map은 hash_table 기반의 hash container입니다.
hash_table을 통해 참조를 하기 때문에 각 node들을 정렬할 필요가 없습니다.
따라서 충분한 hash_table의 크기만 주어진다면 데이터 양이 많아지더라도
Search / Insert / Delete 의 O(1) 성능을 꾸준하게 보장할 수 있습니다.
출처: https://gracefulprograming.tistory.com/3 [Peter의 우아한 프로그래밍]
'STL > map' 카테고리의 다른 글
| map 자주 쓰는 멤버함수 정리 (0) | 2019.09.28 |
|---|