std::unordered_set
std::unordered_set (해시 기반 집합 컨테이너)
고유한 키들을 저장하는 해시 기반 연관 컨테이너예요. 해시 함수로 버킷에 배치돼 평균 상수 시간 탐색이 가능해요. C++11부터 있어요.
출처: cppreference
본문
<unordered_set> 헤더에 정의돼 있고, 해시 기반 연관 컨테이너예요.
template<
class Key,
class Hash = std::hash<Key>,
class KeyEqual = std::equal_to<Key>,
class Allocator = std::allocator<Key>
> class unordered_set;
C++17부터 pmr 별칭도 있어요: std::pmr::unordered_set<Key, Hash, KeyEqual>.
std::unordered_set은 고유한 키들을 저장하는 연관 컨테이너예요. 탐색·삽입·제거의 평균 상수 시간 복잡도를 가져요. 내부적으로 원소들이 버킷들의 배열에 저장되고, 키가 해시 함수로 버킷 인덱스에 매핑돼요. (평균 상수 시간이지만 최악의 경우 선형이 될 수 있어요.)
반복자로 역참조하면 const Key&를 얻으며, 키는 const여서 수정할 수 없어요(제거 후 재삽입해야 함). std::set과 달리 원소의 순서가 정렬돼 있지 않아요.
unordered_set은 Container, AllocatorAwareContainer, UnorderedAssociativeContainer 요구사항을 만족해요.
멤버 타입
key_type, value_type = Key, 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. - 반복자:
begin/cbegin,end/cend. - 용량:
empty,size,max_size. - 수정자:
clear,insert,emplace,emplace_hint,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==,!=: 두 unordered_set 비교.std::swap(std::unordered_set):std::swap특수화.erase_if(C++20): 특정 기준을 만족하는 원소 모두 제거.
빠른 멤버십 확인(어떤 값이 집합에 있는지)이 필요할 때 유용해요. std::set과 달리 정렬 순서가 필요 없고 해시 기반이라 평균 O(1) 탐색을 제공해요. 키 타입은 std::hash 지원 또는 사용자 정의 해시가 필요해요.