[C++] STL로 해시 테이블(Hash Table) 만들기 (std::unordered_map, std::unordered_set)

STL로 해시 테이블(Hash Table) 만들기

서론

C++의 STL을 이용하여 해시 테이블(Hash Table)을 구현할 수 있다.
std::unordered_map과 std::unordered_set을 이용한다.
이 방법으로 해시 테이블을 구현할 경우 원소의 순서가 보장되지 않으며, 원소의 순서를 보장하도록 만들기 위해서는 std::unordered_multimap 또는 std::unordered_multiset을 이용하여 구현하면 된다.

 

코드

#include <iostream>
#include <unordered_map>
#include <unordered_set>

void print(const std::unordered_set<int>& container) {
    for (const auto& element : container) {
        std::cout << element << " ";
    }
    std::cout << std::endl;
}

void print(const std::unordered_map<int, int>& container) {
    for (const auto& element : container) {
        std::cout << element.first << " -> " << element.second << ", ";
    }
    std::cout << std::endl;
}

void find(const std::unordered_set<int>& container, const int element) {
    if (container.find(element) == container.end()) {
        std::cout << element << " 검색: 실패" << std::endl;
    }
    else {
        std::cout << element << " 검색: 성공" << std::endl;
    }
}

void find(const std::unordered_map<int, int>& container, const int element) {
    auto it = container.find(element);
    if (it == container.end()) {
        std::cout << element << " 검색: 실패" << std::endl;
    }
    else {
        std::cout << element << " 검색: 성공, 값 = " << it->second << std::endl;
    }
}

int main() {
    std::cout << "*** std::unordered_set 예제 ***" << std::endl;
    std::unordered_set<int> set1 = {1, 2, 3, 4, 5};

    std::cout << "set1 초기값: ";
    print(set1);

    set1.insert(2);
    std::cout << "2 삽입: ";
    print(set1);

    set1.insert(10);
    set1.insert(300);
    std::cout << "10, 300 삽입: ";
    print(set1);

    find(set1, 4);
    find(set1, 100);

    set1.erase(2);
    std::cout << "2 삭제: ";
    print(set1);

    find(set1, 2);

    std::cout << "*** std::unordered_map 예제 ***" << std::endl;
    std::unordered_map<int, int> squareMap;

    squareMap.insert({2, 4});     // 삽입 방법 1
    squareMap[3] = 9;             // 삽입 방법 2
    std::cout << "2, 3의 제곱 삽입: ";
    print(squareMap);

    squareMap[20] = 400;
    squareMap[30] = 900;
    std::cout << "20, 30의 제곱 삽입: ";
    print(squareMap);

    find(squareMap, 10);
    find(squareMap, 20);
    std::cout << "squareMap[3] = " << squareMap[3] << std::endl;
    std::cout << "squareMap[100] = " << squareMap[100] << std::endl;
    print(squareMap);

    return 0;
}

 

결과 확인

*** std::unordered_set 예제 ***
set1 초기값: 5 1 2 3 4
2 삽입: 5 1 2 3 4
10, 300 삽입: 10 5 1 2 300 3 4
4 검색: 성공
100 검색: 실패
2 삭제: 10 5 1 300 3 4
2 검색: 실패
*** std::unordered_map 예제 ***
2, 3의 제곱 삽입: 3 -> 9, 2 -> 4, 
20, 30의 제곱 삽입: 30 -> 900, 20 -> 400, 3 -> 9, 2 -> 4,
10 검색: 실패
20 검색: 성공, 값 = 400
squareMap[3] = 9
squareMap[100] = 0
100 -> 0, 2 -> 4, 3 -> 9, 20 -> 400, 30 -> 900,