(STL) map vs unordered_map

• std::map은 key와 value를 갖는 데이터 구조
• std::map은 key 값에 따라서 정렬되지만, std::unordered_map은 hash_map과 동일하게 내부적으로 key 값에 의해 정렬되지 않는다.
• std::unordered_map의 장점은 빠른 탐색속도
• n개의 데이터 쌍을 갖는 std::map의 경우 O(logN)의 탐색 속도를 갖는 반면, std::unordered_map은 O(1)의 탐색 속도

map

• map은 기본적으로 red-black tree 기반
• 따라서 모든 데이터는 key 값을 기준으로 정렬
• map의 경우 입력되는 key 값의 분포가 고르지 못할 경우 balancing에 대한 비용이 계속 들어가기 때문에 성능 저하
• 탐색 속도 O(logN)은 보장

unordered_map

• hash_table 기반의 hash_container
• node들을 정렬할 필요가 없기 때문에 탐색에서 O(1)의 성능보장