[C++] map VS. unordered_map

C++에서 map과 unordered_map의 주요 차이점은 elements를 저장하고 액세스하는 방식에 있으며, 이는 성능과 사용 시나리오의 차이로 이어진다. 순서에 신경을 쓴다면 map을 사용하고, 빈번한 key 기반 조회에 대한 성능 우선순위를 정하고 순서를 신경 쓰지 않는다면 일반적으로 unordered_map이 더 좋다.

 

1. 기본 데이터 구조
   1. map
      : balanced binary search tree (일반적으로 Red-Black Tree)로 구현된다. elemets는 key를 기준으로 정렬된 순서로 저장된다.
   2. unordered_map
      : hash table을 사용해 구현된다. elements는 key에 따라 정렬되지 않고 hash values에 따라 임의의 순서로 저장된다.
2. 시간 복잡도
   1. map
      1. 삽입, 삭제, 조회 작업의 시간 복잡도는 tree 구조로 인해 O (log n) 이다.
      2. key를 기준으로 elements의 엄격한 순서를 유지한다.
   2. unordered_map
      1. 삽입, 삭제, 조회 작업은 평균적으로 O (1) 이지만, hash collision이 발생하는 최악의 경우엔 O (n) 이다(좋은 hash function에서는 드물다).
      2. elements 간에 순서가 유지되지 않는다.
3. elements 순서
   1. map
      : key는 항상 정렬된 순서로 저장된다 (기본으로 < 연산자지만 사용자가 제공한 comparator를 따른다).
   2. unordered_map
      : elements는 특정 순서가 없다. 순서는 내부적으로 사용되는 hash function에 의해 결정된다.
4. 메모리 오버헤드
   1. map
      : tree 구조를 유지해야 하므로 일반적으로 elements당 더 많은 메모리가 필요하다.
   2. unordered_map
      : 잠재적인 collision을 관리하기 위해 hash table에 더 많은 메모리를 사용할 수 있지만 일반적으로 map에 비해 elements 당 오버헤드가 적다.
5. 사용 사례
   1. map
      1. elements의 정렬된 순서가 필요할 경우 유용하다.
      2. elements에 대한 빈번한 정렬된 탐색 또는 연산이 필요한 경우 사용하는 것이 좋다.
   2. unordered_map
      1. 빠른 액세스 (삽입, 삭제, 조회)만 중요하고 elements가 특정 순서로 필요하지 않을 때 선호된다.
      2. 일반적으로 key가 정렬되지 않고 빠른 액세스가 주요 목표인 경우 더 효율적이다.

 

map과 unordered_map 중 어느 쪽이 더 유리할까?

1. 일반적으로 key를 정렬할 필요 없이 빠른 조회, 삽입, 삭제가 필요한 경우에는 unordered_map 더 유리하다. 대부분의 경우 평균적으로 더 나은 성능인 O (1) 의 시간 복잡도를 가지기 때문이다.
2. elements가 정렬된 순서로 필요하거나 로그 시간 복잡도가 허용 가능한 수준이고 key의 결정론적 순서가 필요한 경우 map이 더 유리하다.