STL 컨테이너 - unordered_set

unordered_set

C++ STL에서 제공하는 컨테이너 중 하나로, 해시 기반으로 요소를 저장하는 집합입니다. std::set과 달리 요소를 정렬된 상태로 유지하지 않으며, 요소의 저장 순서가 일정하지 않습니다. 그러나 중복 요소를 허용하지 않는 집합의 성질은 std::set과 동일합니다.

0. std::set과 std::unordered_set의 차이점

std::set과 std::unordered_set의 차이점을 표로 정리하면 다음과 같습니다. 두 컨테이너는 모두 키-값 쌍을 저장하는 연관 컨테이너지만, 그 내부 동작 방식에 큰 차이가 있습니다.

특성	std::set	std::unordered_set
정렬	원소가 자동으로 오름차순으로 정렬됨	원소의 순서가 정해져 있지 않음 (해시 값에 따라 순서가 결정됨)
구현 방식	이진 검색 트리 (보통 Red-Black Tree) 사용	해시 테이블 사용
검색 성능	평균적으로 O(log N)	평균적으로 O(1)
삽입 성능	평균적으로 O(log N)	평균적으로 O(1)
메모리 사용	추가적인 트리 구조를 위한 메모리 소모가 있음	해시 테이블에 의한 추가 메모리 사용
중복 허용 여부	중복된 원소를 허용하지 않음	중복된 원소를 허용하지 않음
사용 예시	원소를 정렬된 상태로 관리해야 할 때	원소의 빠른 검색이 중요하고, 순서가 중요하지 않을 때

 

1. std::unordered_set 특징

• 해시 테이블 기반: 요소를 해시 테이블에 저장하며, 삽입/삭제/탐색의 평균 시간 복잡도는 **O(1)**입니다.
• 중복 허용하지 않음: 집합처럼 동작하며, 동일한 값의 요소는 하나만 저장됩니다.
• 정렬되지 않음: 저장된 데이터의 순서는 삽입 순서와 다르며, 요소 간의 정렬이 보장되지 않습니다.
• 빠른 탐색: 해시 테이블 덕분에 대량의 데이터에서 특정 요소를 효율적으로 검색할 수 있습니다.
• 해시 함수와 비교 함수: 사용자 정의 해시 함수나 비교 함수를 지정할 수 있습니다.

2. 헤더 파일

std::unordered_set를 사용하려면 <unordered_set> 헤더를 포함해야 합니다.

 

3. 선언 및 초기화

• 기본 선언

• 초기화

4. 주요 멤버 함수

함수명	설명
insert(value)	요소를 추가합니다.
emplace(value)	요소를 직접 생성하여 추가합니다(복사 생략).
erase(value)	특정 요소를 삭제합니다.
clear()	모든 요소를 제거합니다.
find(value)	특정 요소를 검색하고, 이터레이터를 반환합니다(없으면 end() 반환).
count(value)	특정 요소의 존재 여부를 확인합니다(결과는 0 또는 1).
size()	컨테이너에 저장된 요소의 개수를 반환합니다.
empty()	컨테이너가 비어 있는지 확인합니다.
bucket_count()	현재 사용 중인 버킷의 개수를 반환합니다.
load_factor()	해시 테이블의 요소 대비 버킷 비율을 반환합니다.
rehash(n)	최소 버킷 수를 재설정하여 리해싱을 강제합니다.
reserve(n)	n개의 요소를 저장할 수 있도록 용량을 예약합니다.