std::map은 balanced tree로 구현되어있고, std::unordered_map은 hash table로 구현되어있다.

기본적으로 hash table이 balanced tree보다 더 빠르게 자료를 탐색할 수 있기 때문에, std::unordered_map이 std::map 보다 더 빠르다. 하지만 std::unordered_map은 hash table 구조이기 때문에, 저장해야하는 데이터의 양이 많아진다면 hash collision이 나타날 수 밖에 없어서 성능이 떨어질 수 밖에 없다 (pigeonhole principle).

그러므로 아래와 같은 방식으로 사용하면 좋다.

• 데이터의 양이 작다면 → std::unordered_map
• 데이터의 양이 많다면 → std::map