Unordered map

정의

키(key)-값(value) 쌍을 저장하는 STL(Standard Template Library) 컨테이너

• 해시 테이블(Hash Table) 기반의 연관 컨테이너
• 키의 순서가 없어 저장한 순서대로 순회할 수 없음
• 같은 키를 여러번 삽입하면 마지막 삽입 값으로 덮어 씀

시간복잡도

• 삽입(insert), 삭제(erase), 탐색(find)의 시간 복잡도는 O(1)

템플릿 정의

template <
    class Key,                        // 키 타입
    class T,                          // 값 타입
    class Hash = std::hash<Key>,      // 해시 함수
    class KeyEqual = std::equal_to<Key>, // 키 비교 함수
    class Allocator = std::allocator<std::pair<const Key, T>>  // 할당자
> class unordered_map;

• Key: Key 타입 (int, std::string 등)
• T: Value 타입 (int, std::string 등등)
• Hash: Key를 hash로 변환하는 hash 함수 (기본 값: std::hash<Key>)
• KeyEqual: operator==을 사용하여 키를 비교 (기본 값: std::equal_to<Key>)
• Allocator: 메모리 할당 정책 (기본 값: std::allocator<std::pair<const Key, T>>)

사용 방법

예시 코드

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> umap;

    // 요소 삽입
    umap["apple"] = 3;
    umap["banana"] = 5;
    umap["cherry"] = 2;

    std::string find_key = "apple";
    std::cout << "Apple value: " << umap[find_key] << std::endl;

    find_key = "banana";
    if (umap.find(find_key) != umap.end()) {
        std::cout << find_key << " is found!" << std::endl;
    }

    for (const auto& [key, value] : umap) {
        std::cout << key << ": " << value << std::endl;
    }

    return 0;
}

결과

Apple value: 3
Banana is found!
banana: 5
cherry: 2
apple: 3