std::unordered_map
std::unordered_map (해시 기반 연관 컨테이너)
고유한 키를 갖는 키-값 쌍을 저장하는 연관 컨테이너예요. 키는 해시 함수로 버킷에 배치돼 평균 상수 시간 탐색이 가능해요. C++11부터 있어요.
출처: cppreference
본문
<unordered_map> 헤더에 정의돼 있고, 해시 기반 연관 컨테이너예요.
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;
C++17부터 pmr 별칭도 있어요: std::pmr::unordered_map<Key, T, Hash, KeyEqual>.
std::unordered_map은 고유한 키를 갖는 키-값 쌍을 저장하는 연관 컨테이너예요. 탐색·삽입·제거의 평균 상수 시간 복잡도를 가져요. 내부적으로 원소들이 버킷(bucket)들의 배열에 저장되고, 키가 해시 함수로 버킷 인덱스에 매핑돼요.
(평균 상수 시간이지만) 최악의 경우(충돌이 심할 때) 복잡도는 선형이 될 수 있어요. 반복자로 역참조하면 std::pair<const Key, T>&를 얻으며 키는 const여서 수정할 수 없어요. std::map과 달리 원소의 순서가 정렬돼 있지 않아요.
unordered_map은 Container, AllocatorAwareContainer, UnorderedAssociativeContainer 요구사항을 만족해요.
멤버 타입
key_type, mapped_type, value_type(std::pair<const Key, T>), size_type, difference_type, hasher = Hash, key_equal = KeyEqual, allocator_type, reference, const_reference, pointer, const_pointer, iterator, const_iterator, local_iterator, const_local_iterator, node_type(C++17).
멤버 함수
- 생성자, 소멸자,
operator=,get_allocator. - 원소 접근:
at,operator[]. - 반복자:
begin/cbegin,end/cend. - 용량:
empty,size,max_size. - 수정자:
clear,insert,insert_or_assign(C++17),emplace,emplace_hint,try_emplace(C++17),erase,erase_if(C++20),swap,extract(C++17),merge(C++17). - 탐색:
count,find,contains(C++20),equal_range. - 버킷 인터페이스:
begin(c)/end(c)(해당 버킷의 시작/끝),bucket_count,max_bucket_count,bucket_size,bucket(키가 속한 버킷). - 해시 정책:
load_factor,max_load_factor,rehash,reserve. - 관찰자:
hash_function,key_eq.
비멤버 함수
operator==,!=(C++20부터==계열): 두 unordered_map 비교.std::swap(std::unordered_map):std::swap특수화.erase_if(std::unordered_map)(C++20): 특정 기준을 만족하는 원소 모두 제거.
해시 충돌이 심하지 않다면 평균 O(1)로 키를 찾을 수 있어 빠른 탐색이 필요할 때 std::map의 대안으로 널리 쓰여요. 키 타입은 std::hash가 지원하거나 사용자 정의 해시를 제공해야 해요.