[C++] Unordered Map (작성 중)

참조 자료 : https://en.cppreference.com/w/cpp/container/unordered_map

std::unordered_map - cppreference.com

 

헤더파일

•  #include <unordered_map>

Unordered map 은 unique key를 가진 key-value pair를 저장하는 컨테이너 이다. 요소 탐색, 삽입, 제거가 O(n) 복잡도를 가진다. 내부적으로 요소들은 sorting되어 있지 않지만 bucket으로 구성되어 있다. bucket은 key + hash 에 따라 구성되는데, 동일한 key에 동일한 hash code이면 same bucket으로 연결된다. 

 

unordered_map class의 template

// since C++11
template<
    class Key,
    class T,
    class Hash = std::hash<Key>,
    class KeyEqual = std::equal_to<Key>,
    class Allocator = std::allocator< std::pair<const Key, T> >
> class unordered_map;

// since C++17
namespace pmr {
template <
    class Key,
    class T,
    class Hash = std::hash<Key>,
    class KeyEqual = std::equal_to<Key>
> using unordered_map = std::unordered_map<Key, T, Hash, KeyEqual,
                            std::pmr::polymorphic_allocator<std::pair<const Key,T>>>;
}

 

Class Member type

Member type	Definition
key_type	Key
mapped_type	T
value_type	std::pair<const Key, T>
size_type	unsigned integer type
difference_type	signed integer type
hasher	Hash
key_equal	KeyEqual
.. Member type 더 많지만 생략

 

Class Member function