[c++] map과 unordered_set의 차이

공부 계기

---

오늘 알고리즘 문제를 풀다가, map을 사용했을 때는 시간초과가 발생했지만 unordered_set을 사용했을 때는 통과했다

• 입력된 값중에 특정 값이 있는지 없는지를 파악하기 위해서 해시를 사용해서 O(1) 만에 탐색하고자 했다
• 그래서 나는 map이 key, value로 저장하는 것을 떠올려 당연히 해시일 것이라 생각하고 사용했다
• 그런데, map을 사용했을 때는 시간초과가 발생했고 해시가 아닌 것을 깨달았다

 

풀었던 문제

https://www.acmicpc.net/problem/19585

 

map

---

STL에서 제공하는 key, value 자료구조

• map은 key, value가 pair 형태로 저장이 되며, 해시 테이블이 아닌 이진 탐색 트리(BST) 기반으로 탐색 을 한다
  • 따라서 탐색 시간은 O(logN)
• 정확히는 "레드 블랙 트리(RBT)"를 사용 하며, 값을 항상 정렬된 상태로 유지하고 균형을 유지 한다
• 삽입시에 트리의 균형을 유지하기 위한 움직임이 발생하기 때문에 unordered_map에 비해 느리다

 

unordered_map

---

STL에서 제공하는 해시 테이블 기반의 key, value 자료구조

• unordered_map은 map과 달리 해시 테이블을 사용해서 값을 탐색 한다
  • 따라서 해시 충돌이 없다는 가정 하에 탐색 시간은 O(1)

 

map과 unordered_map의 차이

---

그럼 둘은 어떻게 다르고 언제 사용하는 게 좋지?

• map의 경우에는 값을 저장할 때 정렬을 해서 저장을 하기 때문에, 값이 들어갈 자리를 찾기 위한 시간이 발생한다
• 일반적으로 unordered_map이 map보다 성능이 좋다고 하지만, 데이터의 수가 많아지면 map이 더 좋다고 한다
• 레드 블랙 트리는 이론상 균형을 계속 맞추기 때문에 트리의 높이를 컴팩트하게 유지하고, 해시 테이블에서는 해시 충돌이 발생할 수도 있기 때문이다
• 데이터가 적은 경우에는 unordered_map, 많은 경우에는 map을 사용하는 것이 좋다

 

map과 unordered_map의 시간 복잡도

---

각각에 탐색, 삽입, 삭제 연산을 수행했을 때의 시간 복잡도를 알아보자

연산	map	unordered_map
탐색	O(logN)	O(1)
삽입	O(logN)	O(1)
삭제	O(logN)	O(1)

 

unordered_set

---

그럼 내가 풀이에 사용했던 unordered_set은 뭐지?

• unordered_set은 set은 이진 탐색 트리(BST)를 사용하는 반면, 해시 테이블을 사용하는 set 자료구조이다
• set과 map의 차이는 set의 경우는 단지 값을 저장하지만, map은 key, value 형태의 자료구조인 것이 차이다

 

지금까지 map이 해시 테이블 기반인줄 알았는데, BST 기반인 것을 처음 알았다
앞으로 해시 테이블을 이용하려면 unordered_map이나 unordered_set을 사용하자

 

 

Reference

---

STL map / unordered_map 과 map이 사용하는 자료구조

[STL 컨테이너] map & unordered_map & multimap

[C++] set과 unorderd_set