STL 컨테이너 - unordered_map

unordered_map

**STL(Standard Template Library)**에서 제공하는 연관 컨테이너로, 키-값 쌍(Key-Value Pair)을 저장하며, 내부적으로 **해시 테이블(Hash Table)**을 사용해 빠른 검색, 삽입, 삭제를 제공합니다. 이 컨테이너는 특히 순서가 중요하지 않고, 중복 없는 키를 통해 데이터를 빠르게 관리해야 할 때 유용합니다.

0. std::map과 std::unordered_map의 차이점

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

특징	std::map	std::unoredered_map
내부 자료 구조	Red-Black Tree (균형 이진 탐색 트리)	해시 테이블 (Hash Table)
키의 순서	자동 정렬 (키가 오름차순으로 정렬됨)	정렬되지 않음 (순서는 임의로 유지됨)
탐색 성능	O(log n) (이진 탐색 트리)	O(1) (평균적으로, 해시 테이블에서 직접 접근)
요소 삽입 성능	O(log n)	O(1) (평균적으로)
기본 비교 연산자	operator<	사용자 정의 해시 함수 사용
중복 키 처리	키는 중복될 수 없음 (키는 고유해야 함)	키는 중복될 수 없음 (키는 고유해야 함)
메모리 사용	상대적으로 더 많은 메모리 사용 (트리 구조)	상대적으로 적은 메모리 사용 (해시 테이블)
순차 탐색	정렬된 순서로 순차 탐색	임의 순서로 순차 탐색
사용 가능한 연산자	find, insert, erase, at, size 등	find, insert, erase, at, size 등

1. std::unordered_map의 특징

unordered_map은 키-값 쌍을 저장하는 연관 컨테이너로, 다음과 같은 특징이 있습니다:

• 해시 테이블 기반: 데이터를 해시 테이블을 사용해 저장하므로 **검색, 삽입, 삭제 연산의 평균 시간 복잡도는 O(1)**입니다. (단, 해시 충돌이 많아지면 최악의 경우 O(n)까지 늘어날 수 있음.)
• 무작위 순서: 요소가 삽입된 순서와 무관하게 정렬되지 않고, 해시 함수의 결과에 따라 저장됩니다.
• 고유 키: 모든 키는 고유해야 하며, 동일한 키를 두 번 추가할 수 없습니다.
• 중복되지 않은 키를 사용해야 할 때 적합: 순서가 중요하지 않고 빠른 검색이 필요한 경우 유용합니다.

2. 헤더 파일

std::unordered_map을 사용하려면 <unordered_map> 헤더파일을 포함해야 합니다.

3. 선언 및 초기화

• 기본 선언

• 선언 및 초기화 예제

4. 주요 멤버 함수

insert	키-값 쌍을 삽입. 이미 존재하는 키면 삽입되지 않음.	map.insert({"key", value});
emplace	삽입 시 키와 값을 생성자 호출로 직접 생성.	map.emplace("key", value);
operator[]	키를 통해 값에 접근. 키가 없으면 기본값으로 추가.	map["key"] = value;
erase	특정 키나 이터레이터를 통해 요소 삭제.	map.erase("key");
clear	모든 요소 삭제.	map.clear();
find	키를 찾아 이터레이터 반환. 키가 없으면 end() 반환.	auto it = map.find("key");
count	특정 키가 존재하는지 확인. (0 또는 1 반환)	if (map.count("key")) { ... }
size	현재 요소 개수 반환.	map.size();
empty	비어 있는지 확인.	if (map.empty()) { ... }
at	키를 통해 값을 반환. 키가 없으면 예외 발생.	map.at("key");
operator[]	키를 통해 값에 접근 또는 추가.	map["key"] = value;
bucket_count	해시 테이블의 현재 버킷 개수 반환.	map.bucket_count();
load_factor	해시 테이블의 현재 적재율 반환.	map.load_factor();
rehash	버킷 개수를 수동으로 조정.	map.rehash(50);