Map*_*let 45 c++ dictionary unordered-map keyvaluepair
我正在尝试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在无序地图中使用密钥？
Bau*_*gen 60
您需要为密钥类型提供合适的哈希函数.一个简单的例子:
#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在组合哈希时,您可能希望查看类似于更高质量结果的内容.
对于现实世界的应用:加速还提供了功能集hash_value,其已经提供了一个散列函数std::pair,以及std::tuple最标准箱.
†更准确地说,它会产生太多的碰撞.例如,每个对称对将散列为0,并且仅通过置换而不同的对将具有相同的散列.这可能适合您的编程练习,但可能严重损害现实代码的性能.
Efr*_*eto 15
如果使用pair不是严格要求，您可以简单地使用 map 两次。
#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
Zhu*_* He 12
我解决此问题的首选方法是定义一个key函数,将您的对转换为唯一的整数(或任何可哈希的数据类型).此密钥不是哈希密钥.它是数据对的唯一ID,然后由它进行最佳散列unordered_map.例如,您想要定义一个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每对都是唯一的,也就是说,没有两个不同的对可以拥有相同的密钥,或者可能存在非常难以找到的错误.
小智 9
对于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;
}
参考：C++ 标准库：教程和参考，第二版第 7.9.2 章：创建和控制无序容器
我在 Google 找到的所有解决方案都用来XOR生成 的哈希码pair，这是完全糟糕的。请参阅Why-is-xor-the-default-way-to-combine-hashes。然而，这本书给了我们最好的解决方案，使用hash_combine，它取自Boost。当我在Online Judge（ Atcoder ）中测试时，该解决方案比XOR好得多。我将代码组织为模板，如下所示。您可以尽可能多地复制和粘贴它。并且可以方便地更改它以适应任何自定义结构/类。
更新：为元组添加哈希模板。
#include <functional>
namespace hash_tuple {
template <typename TT> struct hash {
size_t operator()(TT const &tt) const { return std::hash<TT>()(tt); }
};
// from boost (functional/hash):
// see http://www.boost.org/doc/libs/1_35_0/doc/html/hash/combine.html template
template <class T> inline void hash_combine(std::size_t &seed, T const &v) {
seed ^= hash_tuple::hash<T>()(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
// Recursive template code derived from Matthieu M.
template <class Tuple, size_t Index = std::tuple_size<Tuple>::value - 1>
struct HashValueImpl {
void operator()(size_t &seed, Tuple const &tuple) const {
HashValueImpl<Tuple, Index - 1>{}(seed, tuple);
hash_combine(seed, std::get<Index>(tuple));
}
};
template <class Tuple> struct HashValueImpl<Tuple, 0> {
void operator()(size_t &seed, Tuple const &tuple) const {
hash_combine(seed, std::get<0>(tuple));
}
};
template <typename... TT> struct hash<std::tuple<TT...>> {
size_t operator()(std::tuple<TT...> const &tt) const {
size_t seed = 0;
HashValueImpl<std::tuple<TT...>>{}(seed, tt);
return seed;
}
};
// auxiliary generic functions to create a hash value using a seed
template <typename T> inline void hash_val(std::size_t &seed, const T &val) {
hash_combine(seed, val);
}
template <typename T, typename... Types>
inline void hash_val(std::size_t &seed, const T &val, const Types &... args) {
hash_combine(seed, val);
hash_val(seed, args...);
}
template <typename... Types>
inline std::size_t hash_val(const Types &... args) {
std::size_t seed = 0;
hash_val(seed, args...);
return seed;
}
struct pair_hash {
template <class T1, class T2>
std::size_t operator()(const std::pair<T1, T2> &p) const {
return hash_val(p.first, p.second);
}
};
} // namespace hash_tuple
#include <bits/stdc++.h>
int main() {
using ll = long long;
// std::unordered_map<std::pair<ll, ll>, ll, hash_tuple::pair_hash>
// hashmapPair; std::unordered_set<std::pair<ll, ll>, hash_tuple::pair_hash>
// hashsetPair;
std::unordered_map<std::pair<ll, ll>, ll, hash_tuple::pair_hash>
hashmapPair;
hashmapPair[{0, 0}] = 10;
std::unordered_set<std::pair<ll, ll>, hash_tuple::pair_hash> hashsetPair;
hashsetPair.insert({1, 1});
using TI = std::tuple<ll, ll, ll, ll>;
std::unordered_map<TI, ll, hash_tuple::hash<TI>> hashmapTuple;
hashmapTuple[{0, 1, 2, 3}] = 10;
std::unordered_set<TI, hash_tuple::hash<TI>> hashsetTuple;
hashsetTuple.emplace(0, 1, 2, 3);
return 0;
}
正如您的编译错误所示，std::hash<std::pair<std::string, std::string>>您的 std 命名空间中没有有效的实例化。
根据我的编译器：
错误 C2338 C++ 标准不提供此类型的散列。c:\程序文件 (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;
}