[자료구조 및 알고리즘] map과 unordered_map의 차이

map과 unordered_map의 차이

	map	unordered_map
순서	오름차순 정렬	정렬 없음
구현	트리 구조	해시 테이블
탐색 시간	log(N)	O(1)
삽입 시간	log(N)	O(1)

 

요약

• map은 정렬 순서를 보장하고 unordered_map은 보장하지 않는다.
• unordered_map은 hash 기반으로 map보다 속도가 빠르다.
• map은 BST(Binary Search Tree) 기반으로 해시 충돌에서 안전하다.
• set과 unordered_set도 동일하게 각각 트리, 해시 기반이다.
• multimap과 multiset은 BST 기반이다.

참조

https://zshchun.github.io/posts/map%EA%B3%BC-unordered-map%EC%9D%98-%EC%B0%A8%EC%9D%B4/