Programmers <전화번호 목록> 문제를 풀고 다른 사람의 풀이를 보다가, unordered_map을 사용하여 푼 코드를 보고 map과 unordered_map 두 개의 차이점이 무엇인지 궁금해졌다.
map
우선 map이란 연관 컨테이너로 key와 value를 가지고 있는 자료구조이다.
- map은 <key, value>의 pair를 저장
- RB Tree(Red-Black Tree) 기반
- key값을 기준으로 컨테이너 내에서 자동 정렬(오름차순)이 된다.
- 빠른 검색을 위해 사용하며 key값을 기준으로 value의 값을 찾는다.
- 삽입, 삭제가 빈번하게 일어나지 않을 때에 유용하게 사용된다
삽입, 삭제 시 자동 정렬이 발생하기 때문에 많은 시간이 소요된다 - key값의 중복 허용 ❌
unordered_map
- map과 비슷하게 <key, value>의 pair를 저장
- hash table 기반의 hash container
- 따라서 key값에 따른 자동 정렬이 발생하지 않는다.
- 역시나 key값의 중복 허용 ❌
- hash table을 통해 참조 ➡ 정렬이 필요 없다
💡 hash_map과의 차이?
- hash_map와 unordered_map은 비슷하지만 hash_map은 비표준으로 unordered_map에 비해 성능이 좋지 않다.
- unordered_map은 표준으로 C++11부터 포함되어 있다.
unordered_map을 쓰는 것을 권장!
📍
- unordered_map은 정렬 없이 hash table 참조를 통해 값을 찾기 때문에 탐색 속도가 map에 비해 더 빠르다
- 데이터의 수가 많을수록 값을 찾을 때에 unordered_map이 성능면에서 더 좋다
- 키를 정렬하여 탐색하는 것이 아닐 경우 unordered_map을 사용하는 것을 추천!
Backend-Developer