[C++]unorderd_map에서 pair<> 사용 불가능한 이유

1. map<pair<string, string>, int>가 가능한 이유

• std::map은 이진 검색 트리 기반(예: Red-Black Tree)으로 구현되어 있습니다.
• 따라서, std::map은 키를 비교하기 위해 정렬 가능한 순서를 필요로 합니다.
• pair<string, string>은 내부적으로 std::less(기본 정렬 방식)를 사용하여 사전순으로 비교할 수 있습니다.
  • std::pair는 < 연산자가 오버로드되어 있으므로, 자동으로 비교가 가능합니다.
    • 먼저 첫 번째 요소(string)를 비교하고, 같다면 두 번째 요소를 비교합니다.
• 결과적으로, std::map은 pair를 정렬할 수 있으므로 사용이 가능합니다.

---

2. unordered_map<pair<string, string>, int>가 안 되는 이유

• std::unordered_map은 해시 테이블을 기반으로 구현되어 있습니다.
• 해시 테이블에서는 각 키에 대해 고유한 해시 값을 생성해야 하기 때문에, 키에 대해 std::hash가 정의되어 있어야 합니다.
• std::pair<string, string>에 대해 표준 라이브러리에서 기본 제공하는 해시 함수가 없습니다.
  • 따라서, unordered_map은 std::pair를 키로 사용할 수 없다고 컴파일러가 판단합니다.

---

3. 해결 방법: unordered_map<pair<string, string>, int> 사용하려면

• std::unordered_map에서 사용자 정의 키(pair<string, string>)를 사용하려면, 커스텀 해시 함수와 동등 비교 연산자를 정의해야 합니다.
• 예를 들어, 다음과 같이 해시 함수와 비교 함수를 작성할 수 있습니다:

 

#include <iostream>
#include <unordered_map>
#include <string>
#include <functional> // for std::hash

using namespace std;

// 사용자 정의 해시 함수
struct PairHash {
    template <typename T1, typename T2>
    size_t operator()(const pair<T1, T2>& p) const {
        size_t h1 = hash<T1>()(p.first);  // 첫 번째 요소의 해시
        size_t h2 = hash<T2>()(p.second); // 두 번째 요소의 해시
        return h1 ^ (h2 << 1);            // 해시 값 조합
    }
};

// 사용자 정의 동등 비교 함수 (unordered_map의 기본 요구사항)
struct PairEqual {
    template <typename T1, typename T2>
    bool operator()(const pair<T1, T2>& p1, const pair<T1, T2>& p2) const {
        return p1.first == p2.first && p1.second == p2.second;
    }
};

int main() {
    // unordered_map에서 pair<string, string>을 키로 사용
    unordered_map<pair<string, string>, int, PairHash, PairEqual> umap;

    umap[{"hello", "world"}] = 1;
    umap[{"foo", "bar"}] = 2;

    cout << umap[{"hello", "world"}] << endl; // 출력: 1
    cout << umap[{"foo", "bar"}] << endl;     // 출력: 2

    return 0;
}

 

정리

• **std::map**은 키의 정렬 가능한 순서(std::less)만 필요하므로 pair를 바로 사용할 수 있습니다.
• **std::unordered_map**은 해시 값 계산이 필요하기 때문에, pair를 바로 사용할 수 없으며, 커스텀 해시 함수를 정의해야 합니다.

따라서, unordered_map<pair<string, string>, int>를 사용하려면 커스텀 해시를 제공해야 하지만, map<pair<string, string>, int>는 기본적으로 사용 가능합니다.

 

4o