C++ : unordered_map : 개념, 장점, 예제, 구현

C++ : unordered_map : 개념, 장점, 예제, 구현

 

unordered_map

std::map은 자동으로 정렬되는 컨테이너입니다. 그래서 요서 삽입, 제거가 빈번할 경우에는 성능이 저하됩니다. 그래서 그부분을 해결하기 위해 나온 것이 unordered_map입니다.

 

#include <iostream>
#include <string>
#include <unordered_map>

int main()
{
  std::unordered_map<std::string, int> scores;
  
  scores["nana"] = 60;
  scores["mocha"] = 70;
  scores["coco"] = 100;
  
  for (auto it = scores.begin(); it != scores.end(); ++it)
  {
    std::cout << it->first << " : " << it->second << std::endl;
  }
  
  return 0;
}

 

사용법은 map과 상당히 유사합니다. 키와 값의 쌍들을 저장합니다. 키는 중복이 불가합니다. 자동으로 정렬되지 않는 컨테이너입니다. 요소는 해쉬 함수가 생성하는 색인 기반의 버킷들로 구성됩니다. 해쉬맵이라고도 불립니다. 

가끔 키가 다른데도 같은 해쉬 값이 나옵니다. 이럴 경우, 하나의 버킷에 둘 이상의 데이터가 들어갑니다. 버킷 내용도 확인이 가능합니다. 버킷 사이즈를 충분히 크게 하면, 충돌이 적게 날 수 있습니다. 

 

 

std::map 

자동으로 정렬되는 컨테이너입니다. 키 값 쌍들로 정장되며 이진 탐색 트리 기반입니다. 탐색 시간이 O(log n ) 입니다. 삽입과 제거가 빈번하면 느려집니다.

 

 

std::unordered_map

자동으로 정렬되지 않는 컨테이너입니다. 키 값 쌍들로 저장합니다. 해쉬 테이블 기반이며, 탐색 시간이 O(1)로 충돌이 없을 경우 빠릅니다. 최악의 경우 O(n)으로 늘어날 수 있습니다. 버킷 때문에 메모리 사용량이 증가합니다.