我正在尝试创建一个unordered_map
来映射成对的整数:
#include <unordered_map>
using namespace std;
using Vote = pair<string, string>;
using Unordered_map = unordered_map<Vote, int>;
我有一个班级,我已宣布Unordered_map
为私人会员。
但是,当我尝试编译它时,我收到以下错误:
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/include/c++/v1/type_traits:948:38:未定义模板的隐式实例化'std :: __ 1 :: hash,std :: __ 1: :basic_string >>'
如果我使用像map<pair<string, string>, int>
这样的常规地图而不是unordered_map
,我不会收到此错误。
是不是可以在无序地图中使用pair
作为关键?
您需要为密钥类型提供合适的哈希函数。一个简单的例子:
#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还提供了功能集hash_value
,它已经为std::pair
以及std::tuple
和大多数标准容器提供了哈希函数。
†更准确地说,它会产生太多的碰撞。例如,每个对称对将散列为0,并且仅通过排列而不同的对将具有相同的散列。这可能适合您的编程练习,但可能严重损害现实代码的性能。
我解决此问题的首选方法是定义一个key
函数,将您的对转换为唯一的整数(或任何可哈希的数据类型)。此密钥不是哈希密钥。它是unordered_map
最佳散列的数据对的唯一ID。例如,您想要定义类型的unordered_map
unordered_map<pair<int,int>,double> Map;
并且您想使用Map[make_pair(i,j)]=value
或Map.find(make_pair(i,j))
在地图上操作。然后你必须告诉系统如何散列一对整数make_pair(i,j)
。而不是那样,我们可以定义
inline size_t key(int i,int j) {return (size_t) i << 32 | (unsigned int) j;}
然后将地图类型更改为
unordered_map<size_t,double> Map;
我们现在可以使用Map[key(i,j)]=value
或Map.find(key(i,j))
在地图上运行。现在每个make_pair
都会调用内联key
函数。
这种方法保证了密钥的最佳散列,因为现在散列部分由系统完成,系统总是选择内部散列表大小来确定每个桶的可能性。但是你必须让自己100%确定key
对于每一对都是唯一的,即,没有两个不同的对可以具有相同的密钥,或者可能存在非常难以找到的错误。
对于pair键,我们可以使用boost对散列函数:
#include <iostream>
#include <boost/functional/hash.hpp>
#include <unordered_map>
using namespace std;
int main() {
unordered_map<pair<string, string>, int, boost::hash<pair<string, string>>> m;
m[make_pair("123", "456")] = 1;
cout << m[make_pair("123", "456")] << endl;
return 0;
}
类似地,我们可以对向量使用boost hash,
#include <iostream>
#include <boost/functional/hash.hpp>
#include <unordered_map>
#include <vector>
using namespace std;
int main() {
unordered_map<vector<string>, int, boost::hash<vector<string>>> m;
vector<string> a({"123", "456"});
m[a] = 1;
cout << m[a] << endl;
return 0;
}
正如您的编译错误所示,您的std命名空间中没有有效的std::hash<std::pair<std::string, std::string>>
实例化。
根据我的编译器:
错误C2338 C ++标准不提供此类型的哈希。 c:\ program files(x86)\ microsoft visual studio 14.0 \ vc \ include \ xstddef 381
您可以为std::hash<Vote>
提供自己的专业化,如下所示:
#include <string>
#include <unordered_map>
#include <functional>
using namespace std;
using Vote = pair<string, string>;
using Unordered_map = unordered_map<Vote, int>;
namespace std
{
template<>
struct hash<Vote>
{
size_t operator()(Vote const& v) const
{
// ... hash function here ...
}
};
}
int main()
{
Unordered_map m;
}
我知道与其他答案相比,这是太天真的实现,但有一个解决方法。
如果你正在接受对的输入,只需在输入时使用unordered_hash中的另一个整数对该对进行散列,然后间接使用该整数值来对该对进行散列,即
unordered_hash<int, Vote> h;
using Unordered_map = unordered_map<i, int>; // i is corresponding value to pair
在Baum mit Augen对answer的评论中,用户Joe Black asked for an example使用lambda expressions而不是定义哈希函数。我同意Baum mit Augen的opinion,这可能会损害可读性,特别是如果你想实现更通用的解决方案。因此,我想通过关注针对std::pair<std::string, std::string>
的特定解决方案来保持我的例子,如OP所示。该示例还使用了handcrafted函数调用的std::hash<std::string>
组合:
using Vote = std::pair<std::string, std::string>;
auto hash = [](const Vote& v){
return std::hash<std::string>()(v.first) * 31 + std::hash<std::string>()(v.second);
};
using Unordered_map = std::unordered_map<Vote, int, decltype(hash)>;
Unordered_map um(8, hash);
如果使用pair
不是一个严格的要求,你可以简单地使用地图两次。
#include <unordered_map>
using namespace std;
using Unordered_map = unordered_map<string, unordered_map<string, int>>;
Unordered_map um;
um["Region1"]["Candidate1"] = 10;
cout << um["Region1"]["Candidate1"]; // 10