자료구조) unordered_map과 map의 차이

최근에 map관련된 알고리즘 문제들을 많이 풀었다.

Map이란?
Map은 Key와 Value가 쌍으로 이루어진 자료구조이다. (이진트리 기반)
위에 문제사진으로 보자면, 우리는 string 이라는 key값을 통해 "int"를 구하고자하는것이 목적이다.
그러기 때문에 해당 key값은 고유한(Unique) 값을 가져야한다.
map은 Binary Search Tree로 O(log n)의 시간복잡도를 가진다.

Unordered_map이란?
우선 unordered_map은 "정렬이 되지 않은" 맵이라는 뜻으로, 말그대로 정렬을 하지 않았기 때문에 시간복잡도가 O(1)로 들어가게 된다.
이해가 안될수도 있겠지만, unordered_map은 Hash 기반으로 만들어진 컨테이너이기 때문에 정렬이 적용되지 않는다.
단, 이전에 언급했던 map과 같이 고유한 key값을 통해 value를 찾는 목적은 동일하다.