C++ map

Map 종류

• map
• multimap
• unordered_map

map

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;

key value, mapped value로 이루어진 자료구조다.
key 중복이 불가능하다. (unique)
내부 비교 객체(기본은 less)에 의해서 정렬되어 삽입된다. (따라서 항상 정렬되어 있음)
iterator를 사용해 순차적 접근이 가능하지만, key로 개별 접근할 경우에는 unordered_map보다 느리다.

multimap

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

템플릿 형태는 map과 동일하다
key 중복이 가능하다. key가 같은 여러개의 원소가 삽입될 수 있다.
iterator를 사용한 순차적 접근이 가능하지만, 개별 접근은 불가(at() 불가능, find() 사용은 가능)

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과 동일하나, hasher가 들어가는 등 약간의 차이가 있다.
map과 달리 이름처럼 순서나 기준을 가지고 삽입되는 것이 아니므로
순차적 접근이 불가하며, 정렬되어 있지 않다.
참고
(iterator를 통해서 접근 자체는 가능, bucket에 접근하기 때문에 빈곳에 접근하게 될 수도 있다.)
(이렇게 쓰면 이걸 사용하는 의미가 사라지긴 한다. ㅋㅋㅋ)

map에서 기준을 가지고 순차적으로 삽입하는 것과 달리, key를 해싱하여 저장한다.
(빠른 개별 접근을 위해서 내부적으로는 hash에 의해 정리되어 있음)

Internally, the elements in the unordered_map are not sorted in any particular order with respect to either their key or mapped values, but organized into buckets depending on their hash values to allow for fast access to individual elements directly by their key values (with a constant average time complexity on average).

개별 접근 시 상수 시간 복잡도를 가지며 map보다 빠른 접근을 보여준다. (사용하는 이유다)
개인적인 생각으로는 순서 관계없이 일정한 성능을 보여준다고도 할 수 있겠다고 판단했다.
물론 해시 충돌과, 재해싱을 위한 시간은 제외했을 때의 이야기다.

틀린 점은 지적바랍니다.