C++ 在 unordered_map 中使用元组
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/20834838/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Using tuple in unordered_map
提问by Xara
I want to use tuple consisting of int,char,charin my unordered_map. I am doing like this:
我想使用的元组组成的int，char，char在我的unordered_map。我这样做：
#include <string>
#include <unordered_map>
#include <cstring>
#include <iostream>
#include <tuple>
using namespace std;
tuple <int,char,char> kk;
unordered_map<kk,int> map;
int main()
{
map[1,"c","b"]=23;
return 0;
}
but this gives me following errors:
但这给了我以下错误：
map.cpp:9:21: error: type/value mismatch at argument 1 in template parameter list for ‘template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> class std::unordered_map'
map.cpp:9:21: error: expected a type, got ‘kk'
map.cpp:9:21: error: template argument 3 is invalid
map.cpp:9:21: error: template argument 4 is invalid
map.cpp:9:21: error: template argument 5 is invalid
map.cpp:9:26: error: invalid type in declaration before ‘;' token
map.cpp: In function ‘int main()':
map.cpp:14:16: error: assignment of read-only location ‘"b"[map]'
What I am doing wrong in this?
我在这做错了什么？
回答by
The template arguments for an unordered_map looks like this:
unordered_map 的模板参数如下所示：
template<
class Key,
class T,
class Hash = std::hash<Key>,
class KeyEqual = std::equal_to<Key>,
class Allocator = std::allocator< std::pair<const Key, T> >
> class unordered_map;
std::hashis not specialized for tuples(scroll down to Standard specializations for library types). Therefore you need to provide your own, something like this:
std::hash是不是专门为元组（向下滚动到标准专业化的库类型）。因此，您需要提供自己的，如下所示：
typedef std::tuple<int, char, char> key_t;
struct key_hash : public std::unary_function<key_t, std::size_t>
{
std::size_t operator()(const key_t& k) const
{
return std::get<0>(k) ^ std::get<1>(k) ^ std::get<2>(k);
}
};
// ..snip..
typedef std::unordered_map<const key_t,data,key_hash,key_equal> map_t;
// ^ this is our custom hash
And finally, as Benjamin Lindley answer already addresses, you need to use std::make_tuple:
最后，正如本杰明·林德利 (Benjamin Lindley) 已经回答的那样，您需要使用std::make_tuple：
// d is data
m[std::make_tuple(1, 'a', 'b')] = d;
auto itr = m.find(std::make_tuple(1, 'a', 'b'));
The code was grabbed from Using a std::tuple as key for std::unordered_mapand here is the Live Example.
代码是从Using a std::tuple as key for std::unordered_map 中获取的，这里是Live Example。
回答by Benjamin Lindley
First error:
第一个错误：
map.cpp:9:21: error: expected a type, got ‘kk'
As the error clearly says, the template parameter needs to be a type. kkis not a type, it is an object. Perhaps you meant to make it a typedef?
正如错误明确指出的那样，模板参数需要是一个类型。kk不是类型，它是一个对象。也许您打算将其设为 typedef？
typedef tuple <int,char,char> kk;
unordered_map<kk,int> map;
Second error:
第二个错误：
map[1,"c","b"]=23;
Two problems here. First, putting commas between values does not make a tuple out of them. You need to be explicit about it, either calling the constructor of your tuple type, or using a function which returns a tuple (e.g. std::make_tuple). Second, your tuple is expecting chars ('c','b'), not strings ("c","b").
这里有两个问题。首先，在值之间放置逗号不会将它们变成一个元组。您需要明确说明它，要么调用元组类型的构造函数，要么使用返回元组的函数（例如std::make_tuple）。其次，您的元组需要字符 ( 'c','b')，而不是字符串 ( "c","b")。
map[std::make_tuple(1,'c','b')] = 23;
回答by Leo Goodstadt
As pointed out, std::hash is not specialized for tuples. However, if your tuple consists of standard hashable types like string and int, the following code from generic-hash-for-tuples-in-unordered-map-unordered-setwill automatically add such support in c++11.
正如所指出的， std::hash 不是专门用于元组的。但是，如果您的元组包含标准的可散列类型，例如 string 和 int，那么来自generic-hash-for-tuples-in-unordered-map-unordered-set的以下代码将自动在 c++11 中添加此类支持。
Just paste the code in a header file and include it whenever needed:
只需将代码粘贴到头文件中，并在需要时包含它：
#include <tuple>
// function has to live in the std namespace
// so that it is picked up by argument-dependent name lookup (ADL).
namespace std{
namespace
{
// Code from boost
// Reciprocal of the golden ratio helps spread entropy
// and handles duplicates.
// See Mike Seymour in magic-numbers-in-boosthash-combine:
// https://stackoverflow.com/questions/4948780
template <class T>
inline void hash_combine(std::size_t& seed, T const& v)
{
seed ^= 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
{
static void apply(size_t& seed, Tuple const& tuple)
{
HashValueImpl<Tuple, Index-1>::apply(seed, tuple);
hash_combine(seed, get<Index>(tuple));
}
};
template <class Tuple>
struct HashValueImpl<Tuple,0>
{
static void apply(size_t& seed, Tuple const& tuple)
{
hash_combine(seed, 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...> >::apply(seed, tt);
return seed;
}
};
}
回答by Manohar Reddy Poreddy
I had a requirement of map instead of unordered map:
key was 3-tuple and
value was a 4-tuple
我需要映射而不是无序映射：
键是 3 元组，
值是 4 元组
seeing all answers, I was about to change to pairs
看到所有的答案，我正要换成对
but, below worked for me:
但是，以下对我有用：
// declare a map called map1
map <
tuple<short, short, short>,
tuple<short, short, short, short>
> map1;
// insert an element into map1
map1[make_tuple(1, 1, 1)] = make_tuple(0, 0, 1, 1);
// this also worked
map1[{1, 1, 1}] = { 0, 0, 1, 1 };
I am using visual studio community 2015 ide
我正在使用 Visual Studio 社区 2015 ide
回答by Daniel Stracabo?ko
For those using boostthey can just reroute hashing to boost's implementation using this
对于那些使用boost他们的人，他们可以使用这个重新路由散列以提升实现
#include "boost/functional/hash.hpp"
#include <string>
#include <unordered_map>
#include <cstring>
#include <iostream>
#include <tuple>
using Key = std::tuple<int, char, char>;
struct KeyHash {
std::size_t operator()(const Key & key) const
{
return boost::hash_value(key);
}
};
using Map = std::unordered_map<Key, int, KeyHash>;
int main()
{
Map map;
map[1,"c","b"] = 23;
return 0;
}
回答by edW
Here is a method to use tuple as a key for an unordered_map without using a hash specialization:
这是一种使用元组作为 unordered_map 的键而不使用哈希特化的方法：
#include <string>
#include <tuple>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <vector>
#include <unordered_map>
using namespace std;
string fToStr(unordered_map<double,int>& dToI,float x)
{
static int keyVal=0;
stringstream ss;
auto iter = dToI.find(x);
if(iter == dToI.end()) {
dToI[x]=++keyVal;
ss << keyVal;
} else {
ss << iter->second;
}
return ss.str();
}
typedef tuple<int,char,char> TICC;
const char ReservedChar=',';
string getKey(TICC& t)
{
stringstream ss;
ss << get<0>(t) << ReservedChar << get<1>(t) << ReservedChar << get<2>(t);
return ss.str();
}
int main()
{
unordered_map< string,TICC > tupleMp;
vector<TICC> ticc={make_tuple(1, 'a', 'b'),make_tuple(1, 'b', 'c'),make_tuple(2, 'a', 'b')};
for(auto t : ticc)
tupleMp[getKey(t)]=t;
for(auto t : ticc) {
string key = getKey(t);
auto val = tupleMp[key];
cout << "tupleMp[" << key << "]={" << get<0>(val) << "," << get<1>(val) << ","<< get<2>(val) << "} ";
}
cout << endl;
//for float tuple elements use a second float to int key map
unordered_map< double,int > dToI;
vector<float> v{1.234,1.234001,1.234001};
cout << "\nfloat keys: ";
for(float f : v)
cout << setprecision(7) << f << "=" << fToStr(dToI,f) << " ";
cout << endl;
return 0;
}
Output is:
输出是：
tupleMp[1,a,b]={1,a,b} tupleMp[1,b,c]={1,b,c} tupleMp[2,a,b]={2,a,b}
float keys: 1.234=1 1.234001=2 1.234001=2
回答by Kyle
After reading a fewotherpostsI ended up with this. It uses an efficient hash combination algorithm and doesn't specialize things in the stdnamespace. You'll need to do some more work if you want this code to work for any tuple of hashable elements in general.
阅读后几个其他职位我结束了这一点。它使用高效的散列组合算法并且不专门化std命名空间中的事物。如果您希望此代码通常适用于任何可散列元素的元组，则需要做更多的工作。
This works in C++11 and above. In C++03 you can use boost::hashinstead of std::hash.
这适用于 C++11 及更高版本。在C ++ 03可以使用boost::hash的替代std::hash。
typedef tuple<int, char, char> MyTuple;
// define a hash function for this tuple
struct KeyHash : public std::unary_function<MyTuple, std::size_t> {
std::size_t operator()(const MyTuple& k) const {
// the magic operation below makes collisions less likely than just the standard XOR
std::size_t seed = std::hash<int>()(std::get<0>(k));
seed ^= std::hash<char>()(std::get<1>(k)) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
return seed ^ (std::hash<char>()(std::get<2>(k)) + 0x9e3779b9 + (seed << 6) + (seed >> 2));
}
};
// define the comparison operator for this tuple
struct KeyEqual : public std::binary_function<MyTuple, MyTuple, bool> {
bool operator()(const MyTuple& v0, const MyTuple& v1) const {
return (std::get<0>(v0) == std::get<0>(v1) && std::get<1>(v0) == std::get<1>(v1) &&
std::get<2>(v0) == std::get<2>(v1));
}
};
typedef unordered_map<MyTuple, int, KeyHash, KeyEqual> MyMap;
