[STL] Unordered_Map

STL 에서 기존에 사용하던 Map이라는 container가 있다.

array, vector, list의 경우 연속 컨테이너 (Sequential Container) 였다면, map 과 set의 경우에는 연관 컨테이너(Associative Container)이다. 

여기서 연관 컨테이너라 함은 Key Value가 서로 관련이 있다는 뜻이다.  

map의 경우에는 pair<key,value> 형태로 데이터를 저장하게 되는데, key가 기준이 되어 데이터를 정렬하게 된다. 

Set의 경우에는 map과 비슷하지만 value가 따로 설정되어 있지 않다. 

여튼, 연관 컨테이너 set, map을 사용하는 목적은 찾고자하는 원소를 보다 빨리 찾기 위해서이다. 

set map 의 경우 원소를 찾는데 걸리는 시간 복잡도의 경우 n*logn이다. 

 

그런데 정렬이 필요없는 경우엔 어떨까? 예를 들어 key와 value를 넣지만 어디있는지 박아두고 찾고싶긴한데, 굳이 정렬되어있을 필요가 없는 경우가 그것이다. 

그런 경우를 위해 삽입할때 정렬하는 과정을 없애서 성능 저하를 최대한 막기 위한 것이 unordered_set, unordered_map이다. 

 

사용처

key value형태를 가지고 있고, 메모리를 필요한만큼만 자동으로 할당해주고, 최악의 경우 O(n)의 시간이 걸리긴 하지만 대부분의 경우 O(1)의 시간이 걸리는 탐색시간 덕분에 Hash Table대신에 주로 사용하게 된다.

Hash map으로 사용하게 되면 특정 string 값에 대한 value를 지정해둘 수 있기때 문에 편리하게 사용이 가능하다.

 

사용법

사용법의 경우에는 map과 거의 동일하다. key는 중복이 불가능하고 정렬되어 있지 않은 상태이다.