[C++知识库]C++ unordered_map/map的key

unordered_map可以使用基本类型，string作为key，不能使用pair作为key，map可以使用基本类型，string和pair作为key。

以leetcode-2001为例

// 解法1
class Solution {
public:
    int gcd(int a, int b) {
        if (a < b) return gcd(b, a);
        if (a % b == 0) return b;
        return gcd(b, a%b);
    }
    
    // 使用这种嵌套的方式表示两个key
    unordered_map<int, unordered_map<int, long long>> cnt;
    
    long long interchangeableRectangles(vector<vector<int>>& rectangles) {
        for (auto r : rectangles) {
            int c = gcd(r[0], r[1]);
            r[0] /= c;
            r[1] /= c;
            
            cnt[r[0]][r[1]]++;
        }
        
        long long ans = 0;
        
        for (auto iter = cnt.begin(); iter != cnt.end(); iter++) {
            for (auto i = iter->second.begin(); i != iter->second.end(); i++) {
                ans += i->second * (i->second - 1) / 2;
            }
        }
        
        
        return ans;
    }
};
// 解法2
class Solution {
public:
    int gcd(int a,int b)
    {
        if(b == 0)
            return a;
        return gcd(b,a%b);
    }
    long long interchangeableRectangles(vector<vector<int>>& rectangles) 
    {
    	// map可以直接使用pair作为key
        map<pair<int, int>, int, hash_pair> m;
        long long ans = 0;
        for(int i=0;i<rectangles.size();i++)
        {
            int x = rectangles[i][0];
            int y = rectangles[i][1];
            int g = gcd(x,y);
            x /= g;
            y /= g;
            ans += m[make_pair(x,y)];
            m[make_pair(x,y)]++;
        }
        return ans;
    }
};


// 解法3 
// unordered_map要想使用pair作为key，必须要实现一个hash
struct hash_pair { 
    template <class T1, class T2> 
    size_t operator()(const pair<T1, T2>& p) const
    { 
        auto hash1 = hash<T1>{}(p.first); 
        auto hash2 = hash<T2>{}(p.second); 
        return hash1 ^ hash2; 
    } 
}; 

class Solution {
public:
    int gcd(int a,int b)
    {
        if(b == 0)
            return a;
        return gcd(b,a%b);
    }
    long long interchangeableRectangles(vector<vector<int>>& rectangles) 
    {
        unordered_map<pair<int, int>, int, hash_pair> m;
        long long ans = 0;
        for(int i=0;i<rectangles.size();i++)
        {
            int x = rectangles[i][0];
            int y = rectangles[i][1];
            int g = gcd(x,y);
            x /= g;
            y /= g;
            ans += m[make_pair(x,y)];
            m[make_pair(x,y)]++;
        }
        return ans;
    }
};