12. Unordered Container

연관 컨테이너는 set, multiset, map, multimap 외에도 더 존재한다. unordered_set, unordered_multiset, unordered_map, unordered_multimap은 해싱을 이용하여 자료를 저장하는 연관 컨테이너로 C++11 표준이며 그 이전에는 각각 hash_set, hash_multiset, hash_map, hash_multimap이라는 비표준 라이브러리로 존재했다.

 

C++에서 <unordered_set> 헤더파일을 인클루드하면 unordered_set과 unordered_multiset을 사용할 수 있고 <unordered_map> 헤더파일을 인클루드하면 unordered_map과 unordered_multimap을 사용할 수 있다. 각각의 클래스는 <unordered_set>에서 인클루드하는 헤더파일 <bits/unordered_set.h>와 <unordered_map>에서 인클루드하는 헤더파일 <bits/unordered_map.h>에 정의되어 있다.

 

해싱을 사용하여 자료를 저장하기 때문에 이 컨테이너들은 삽입한 원소를 자동으로 정렬할 필요가 없다. 하지만 이것이 이 컨테이너들의 처리 속도가 빠르다는 것을 의미하지는 않는다. 오히려 특정 상황에서는 성능이 심하게 저하될 가능성이 있다. 자세한 내용은 이 글들을 참고하면 좋다.

 

unordered container의 멤버 함수는 앞에서 소개한 연관 컨테이너의 멤버 함수와 많이 겹친다. 다음 함수들은 unordered_set, unordered_multiset, unordered_map, unordered_multimap에 공통으로 내장되어 있으며, 이것들에 대한 설명은 이 글을 참고하면 된다.

unordered_set::insert
unordered_set::size
unordered_set::clear
unordered_set::empty
unordered_set::erase
unordered_set::begin
unordered_set::end
unordered_set::emplace
unordered_set::emplace_hint
unordered_set::count
unordered_set::find
unordered_set::contains
unordered_set::equal_range
unordered_set::max_size
unordered_set::extract
unordered_set::merge
unordered_set::swap
unordered_set::get_allocator

다음 함수들은 unordered_map에만 내장된 함수들이다. 이것들과 [] 연산자에 대한 설명은 이 글을 참고하면 된다.

unordered_map::insert_or_assign
unordered_map::try_emplace
unordered_map::at

이밖에 unordered container에는 각각의 원소를 해시값에 따라 저장할 bucket이라는 개념과 이와 관련된 함수, 그밖에 해싱과 관련된 함수가 추가로 존재하며 다음과 같다(unordered_set, unordered_multiset, unordered_map, unordered_multimap에 공통으로 적용된다):

u.begin(x);	해시값이 x인 버킷의 시작 주소를 가리키는 반복자를 반환한다.
u.end(x);	해시값이 x인 버킷의 끝을 가리키는 반복자를 반환한다.
u.bucket(k);	key k가 속한 버킷을 반환한다.
u.bucket_size(x);	해시값이 x인 버킷에 들어 있는 key의 개수를 반환한다.
u.bucket_count();	u의 버킷의 개수를 반환한다.
u.max_bucket_count();	u가 담을 수 있는 버킷의 최대 개수를 반환한다.
u.load_factor();	u의 버킷에 들어 있는 key의 평균 개수를 반환한다.
u.max_load_factor();	u의 버킷에 들어 있는 key의 평균 개수로 가능한 최댓값을 반환한다.
u.rehash(n);	u의 버킷의 수를 n으로 바꾸고 key들을 다시 해싱한다.
u.reserve(n);	u에 최소 n개의 원소를 담을 수 있는 메모리를 할당한다.
u.hash_function();	u의 해시 함수를 반환한다.
u.key_eq();	u의 key 비교 함수를 반환한다.

rehash, reserve 함수는 해시 테이블을 새로 만든다. reserve 함수의 경우 vector::reserve 함수와 비슷하게 이해할 수 있다.

 

이상의 unordered container들은 때때로 유용하게 사용할 수 있으나 프로그래밍 대회에서는 이것들을 사용한 코드를 저격하는 데이터가 있을 가능성이 높으므로 사용을 신중하게 결정해야 한다. 특히 codeforces처럼 Hack 시스템이 존재하는 대회에서는 사용을 자제할 필요가 있다.

 

→ solved.ac tag: hash_set