[C++] STL std::map의 사용과 속도

map은 stl 컨테이너로 키와 value를 저장하는 class이다. 

template < class Key,                                     // map::key_type
           class T,                                       // map::mapped_type
           class Compare = less<Key>,                     // map::key_compare
           class Alloc = allocator<pair<const Key,T> >    // map::allocator_type
           > class map;

간단한 선언예시는 다음과 같고

std::map<string, int> account;

account라는 map에 string,int의 pair를 삽입한다.

 

insert,erase으로 삽입,삭제를 진행하고 find를 통해 원하는 key에 대한 value를 찾을 수 있다.

 

C++에서 map은 이진탐색트리를 기본으로 한 트리로 구현되었는데 여기서 문제(?)가 발생한다.

이는 탐색의 속도 문제로 map은 정렬을 진행하다 보니 find에 log(N)의 시간이 소요된다.

 

이러한 단점을 해결하기 위해 나온 map이 unordered_map 이다.

unordered_map은 hashmap 기반으로 탐색에 일반적으로 log(1)의 시간이 소요되기 때문에 정렬이 필요하지 않는 대부분의 사용처에 있어서 unordered_map의 속도나 활용도가 높을 것으로 보인다.

template < class Key,                                    // unordered_map::key_type
           class T,                                      // unordered_map::mapped_type
           class Hash = hash<Key>,                       // unordered_map::hasher
           class Pred = equal_to<Key>,                   // unordered_map::key_equal
           class Alloc = allocator< pair<const Key,T> >  // unordered_map::allocator_type
           > class unordered_map;

 

왜 처음 map을 implement할 때 bst기반으로 알고리즘을 작성했을까 생각해 보면 확실치는 않지만 iteration을 universal하게 제공하고 싶었던것으로 보인다. 이는 stl의 주요 목적중 하나로 map에서도 iteration을 의미있게 활용하려면 sorting이 필요하고 log(N)정도면 충분하다고 생각했을지도 모른다. 또 hash map에 비해 메모리를 적게쓰므로 이러한 곳에서 이점이 있다고 판단했을지도 모르겠다.

 

하지만 결과적으로 map이 unoredered_map보다 탐색에 시간이 더 걸리게 되고 sorting에도 시간이 걸리므로 정렬이 필요한 경우엔 map을 그렇지 않으면 undordered_map을 사용하는것이 유리할 것이다.