Using a tuple in unordered_map

Question

I want to use a tuple consisting of int , char , char in my unordered_map . I do like this:

 #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 it gives me the 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]' 

How am I wrong about this?

Answer 1

The template arguments for unordered_map are as follows:

 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::hash does not specialize in tuples (scroll down to standard specializations for library types). Therefore, you need to provide your own, something like this:

 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 has already mentioned, you need to use 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 std :: tuple as the key for std :: unordered_map and here is a Live Example .

Answer 2

First mistake:

 map.cpp:9:21: error: expected a type, got 'kk' 

As the error clearly states, the template parameter must be a type. kk not a type, it is an object. Perhaps you wanted to make this a typedef?

 typedef tuple <int,char,char> kk; unordered_map<kk,int> map; 

Second error:

 map[1,"c","b"]=23; 

Two problems here. First, entering commas between values ​​does not create a tuple from them. You should be frank in this matter by calling a constructor like your tuple or using a function that returns a tuple (for example, std::make_tuple ). Secondly, your tuple expects characters ( 'c','b' ), not strings ( "c","b" ).

 map[std::make_tuple(1,'c','b')] = 23; 

Answer 3

As stated, std :: hash is not specialized for tuples. However, if your tuple consists of standard hash types of type string and int, the following code from generic-hash-for-tuples-in-unordered-map-unordered-set will automatically add such support in C ++ 11.

Just paste the code into the header file and include it if necessary:

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

Answer 4

I had a card requirement instead of an unordered card:
the key was a 3-tuple and
the value was a 4-tuple

seeing all the answers, I was going to switch 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

Answer 5

Here is a method for using a tuple as a key for unordered_map without using hash specialization:

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

Exit:

 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 

Answer 6

After reading a few other posts, I ended up with this. It uses an efficient hashing algorithm and does not specialize in the std . You will need to do extra work if you want this code to work for any set of hash elements in general.

This works in C ++ 11 and above. In C ++ 03, you can use boost::hash instead of 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;