[STL] 10. unordered_map

unordered_map

개념

• 해시 테이블을 기반으로 한 키-값 쌍을 저장하는 컨테이너이다.

• 빠른 검색 속도로, 일반적인 경우 삽입, 삭제, 탐색에 O(1)의 시간복잡도를 가진다.

• 내부적으로 해싱 함수인 std::hash를 사용한다.

• 해시 테이블을 사용해 데이터를 저장하므로 데이터의 순서는 보장되지 않는다.

• 충돌 방지 기법으로 체이닝 방식을 사용한다.

생성

unordered_map<string, int> umap;

멤버 함수

std::unordered_map - cppreference.com

    class Key,     class T,     class Hash = std::hash<Key>,     class KeyEqual = std::equal_to<Key>,     class Allocator = std::allocator<std::pair<const Key, T>>

https://en.cppreference.com/w/cpp/container/unordered_map

삽입

// 위치에 요소를 삽입
auto result = umap.insert({ "name", 5 });

// 요소를 생성 후 삽입, 요소 복사나 이동과정 줄어들음
auto result = umap.emplace( "name", 5 );

// 삽입 결과 리턴
result.first // 첫 번째는 삽입된 요소 또는 이미 존재하는 요소에 대한 이터레이터.
result.second // 두 번째는 삽입이 성공했는지 여부를 나타내는 bool 값

삭제

unordered_map<string, int> umap = {{ "apple", 1 }, { "banana", 2 }, { "orange", 3 }};

// 키를 이용해 삭제
umap.erase("apple"); // apple만 삭제

// 이터레이터를 이용해 삭제
umap.erase(it1, it2, ...);

// 전부 삭제, 컨테이너는 유효함
umap.clear(); 

탐색

// 연산자 []를 사용하여 접근, 키가 없을 경우 요소 삽입
umap.insert({"apple", 1});
cout << operator["apple"]; // 1

// at()함수를 사용하여 접근, 키가 없을 경우 예외를 발생
umap.insert({"apple", 1});
try {
    cout << umap.at("banana");
}
catch (out_of_range& e) {
    cerr << e.what();
}

// 특정 키를 가진 원소를 찾아 이터레이터를 반환, 없으면 end()반환
auto it = umap.find("apple");

unordered_map vs map