問題描述

我正在嘗試創(chuàng)建一個 unordered_map 來映射整數對:

I am trying to create an unordered_map to map pairs with integers:

#include <unordered_map>

using namespace std;
using Vote = pair<string, string>;
using Unordered_map = unordered_map<Vote, int>;

我有一個類，我將 Unordered_map 聲明為私有成員.

I have a class where I have declared an Unordered_map as a private member.

但是，當我嘗試編譯它時出現以下錯誤:

However, I am getting the following error when I try to compile it:

/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/include/c++/v1/type_traits:948:38: 未定義模板的隱式實例化 'std::__1::hash, std::__1::basic_string > >'

/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/include/c++/v1/type_traits:948:38: Implicit instantiation of undefined template 'std::__1::hash, std::__1::basic_string > >'

如果我使用像 map<pair<string, string>, int> 這樣的常規(guī)映射而不是 unordered_map，我不會收到這個錯誤.

I am not getting this error if I use a regular map like map<pair<string, string>, int> instead of an unordered_map.

在無序映射中不能使用 pair 作為鍵嗎?

Is it not possible to use pair as key in unordered maps?

推薦答案

您需要為您的密鑰類型提供合適的散列函數.一個簡單的例子:

You need to provide a suitable hash function for your key type. A simple example:

#include <unordered_map>
#include <functional>
#include <string>
#include <utility>

// Only for pairs of std::hash-able types for simplicity.
// You can of course template this struct to allow other hash functions
struct pair_hash {
    template <class T1, class T2>
    std::size_t operator () (const std::pair<T1,T2> &p) const {
        auto h1 = std::hash<T1>{}(p.first);
        auto h2 = std::hash<T2>{}(p.second);

        // Mainly for demonstration purposes, i.e. works but is overly simple
        // In the real world, use sth. like boost.hash_combine
        return h1 ^ h2;  
    }
};

using Vote = std::pair<std::string, std::string>;
using Unordered_map = std::unordered_map<Vote, int, pair_hash>;

int main() {
    Unordered_map um;
}

這可以工作，但沒有最好的哈希屬性^?.你可能想看看像 boost.hash_combine 在組合散列時獲得更高質量的結果.這也在這個答案中進行了更詳細的討論——包括上述boost的解決方案.

This will work, but not have the best hash-properties^?. You might want to have a look at something like boost.hash_combine for higher quality results when combining the hashes. This is also discussed in greater detail – including the aforementioned solution from boost – in this answer.

對于現實世界的使用:Boost 還提供了函數集 hash_value 已經為 std::pair 以及 std::tuple 和大多數標準容器提供了一個哈希函數.

For real world use: Boost also provides the function set hash_value which already provides a hash function for std::pair, as well as std::tuple and most standard containers.

^?更準確地說，它會產生過多的碰撞.例如，每個對稱對都將散列到 0，并且僅在排列上不同的對將具有相同的散列.這對于您的編程練習來說可能沒問題，但可能會嚴重損害現實世界代碼的性能.

^?More precisely, it will produce too many collisions. E.g., every symmetric pair will hash to 0 and pairs that differ only by permutation will have the same hash. This is probably fine for your programming exercise, but might seriously hurt performance of real world code.

這篇關于為什么我不能用一對作為鍵編譯 unordered_map ?的文章就介紹到這了，希望我們推薦的答案對大家有所幫助，也希望大家多多支持html5模板網！