자료구조 SearchTime - map,set,unordered_map

map, set, multimap, multiset 은 일반적으로 binary tree로 구현되어 있다.

(VS 컴파일러의 경우, Red Black Tree로 구현되어 있음)

https://ko.wikipedia.org/wiki/%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99_%ED%8A%B8%EB%A6%AC

오른쪽, 왼쪽을 비교해가면서 'Key'를 찾아가는 구조이다.

이와 같은 구조는 O(log n) 의 시간이 소요된다.

반면, unordered_map 이나 unordered_set의 경우 (c++11 이상에서 사용가능), 해쉬테이블로 구현되어 있다.

bucket이라는 일종의 슬롯형태에 데이터를 해쉬알고리즘에 나누어서 집어넣는 구조인데,

해쉬함수가 constant time이라고 가정할때, SearchTime의 평균시간은  O(1) 이다.

가장 최악의 경우는 모든 데이터가 하나의 bucket에 들어간 경우인데,

이럴경우, 모든 데이터를 iterate 해야하는데 이때는 데이터의 갯수에 비례하는 O(n) 이 소요된다.

따라서 해쉬함수가 적절하고 데이터가 적절하게 분류된다면, constant time을 기대할 수 있다.

bucket_count() 를 이용하면 전체 bucket 카운트를 구할 수 있다.

<Source>

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

int main ()
{
  std::unordered_multimap<std::string,std::string> myumm = {
       {"bed","bedroom"},
       {"oven","kitchen"},
       {"towel","bathroom"},
       {"towel","beach"},
       {"plant","garden"}
  };

  unsigned n = myumm.bucket_count();

  std::cout << "myumm has " << n << " buckets.\n";

  for (unsigned i=0; i<n; ++i) {
    std::cout << "bucket #" << i << " contains: ";
    for (auto it = myumm.begin(i); it!=myumm.end(i); ++it)
      std::cout << "[" << it->first << ":" << it->second << "] ";
    std::cout << "\n";
  }

  return 0;
}

<OutPut>

myumm has 5 buckets.
bucket #0 contains: [towel:bathroom] [towel:beach]
bucket #1 contains: [plant:garden]
bucket #2 contains: 
bucket #3 contains: 
bucket #4 contains: [oven:kitchen] [bed:bedroom]

각각의 bucket에 어떤 데이터가 들어있는지 확인할 수 있다.