問題描述

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

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>;

我有一個(gè)類，我將 Unordered_map 聲明為私有成員.

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

但是，當(dāng)我嘗試編譯它時(shí)出現(xiàn)以下錯(cuò)誤:

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: 未定義模板的隱式實(shí)例化 '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，我不會(huì)收到這個(gè)錯(cuò)誤.

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?

推薦答案

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

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 在組合散列時(shí)獲得更高質(zhì)量的結(jié)果.這也在這個(gè)答案中進(jìn)行了更詳細(xì)的討論——包括上述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.

對于現(xiàn)實(shí)世界的使用:Boost 還提供了函數(shù)集 hash_value 已經(jīng)為 std::pair 以及 std::tuple 和大多數(shù)標(biāo)準(zhǔn)容器提供了一個(gè)哈希函數(shù).

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.

^?更準(zhǔn)確地說，它會(huì)產(chǎn)生過多的碰撞.例如，每個(gè)對稱對都將散列到 0，并且僅在排列上不同的對將具有相同的散列.這對于您的編程練習(xí)來說可能沒問題，但可能會(huì)嚴(yán)重?fù)p害現(xiàn)實(shí)世界代碼的性能.

^?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.

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