unordered_map
unordered_map (std::unordered_map — 해시 맵)
std::unordered_map은 고유한 키를 가진 키-값 쌍을 담는 연관 컨테이너로, 키를 해시 함수로 매핑해 평균 상수 시간에 검색해요.
출처: cppreference
본문
std::unordered_map은 고유한 키를 가진 키-값 쌍을 담는 연관 컨테이너예요. 검색·삽입·제거는 평균적으로 상수 시간(amortized constant) 복잡도를 가져요. 내부적으로는 해시 테이블로 구현되며, 원소는 키의 해시값에 따라 버킷(bucket)에 분산돼요.
주요 특징은 다음과 같아요.
- 키는 정렬되지 않아요(비내림차순 무관). 대신
Hash함수와KeyEqual동등 비교로 관리돼요. - 키는 고유해요. 중복 키는
unordered_multimap이 다뤄요. - 이터레이터는 순방향(forward)이고, 역방향 순회는 지원하지 않아요.
템플릿 매개변수
Key: 키의 타입.T: 매핑된 값의 타입.Hash: 키를 해시하는 함수 객체 타입. 기본값은std::hash<Key>.KeyEqual: 키 동등성을 판정하는 함수 객체 타입. 기본값은std::equal_to<Key>.Allocator: 할당자. 기본값은std::allocator<std::pair<const Key, T>>.
멤버 타입
key_type=Key,mapped_type=T,value_type=std::pair<const Key, T>hasher=Hash,key_equal=KeyEqualsize_type,difference_type,reference,const_reference,pointer,const_pointeriterator,const_iterator,local_iterator,const_local_iteratornode_type,insert_return_type
멤버 함수
- 생성자/파괴자,
operator=,get_allocator - 원소 접근:
at,operator[] - 이터레이터:
begin,end(및begin(n),end(n)버킷 이터레이터) - 용량:
empty,size,max_size - 수정자:
clear,insert,insert_range,insert_or_assign,emplace,emplace_hint,try_emplace,erase,erase_if,swap,extract,merge - 탐색:
count,find,contains,equal_range - 버킷 인터페이스:
begin,end(버킷),bucket_count,max_bucket_count,bucket_size,bucket - 해시 정책:
load_factor,max_load_factor,rehash,reserve - 관찰자:
hash_function,key_eq - 비멤버 함수:
operator==,operator!=(C++20에서 파생),std::erase_if,std::swap