Using tuple in unordered_map

user_1170920 0
Viewed 62768

I want to use tuple consisting of int,char,char in my unordered_map. I am doing 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 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?

unordered-map stdtuple hashmap c++
8 Answers

For those using boost they can just reroute hashing to boost's implementation using this

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

Here is a method to use tuple as a key for an unordered_map without using a 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;
}

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
user_18129420

After reading a few other posts I ended up with this. It uses an efficient hash combination algorithm and doesn't specialize things in the std namespace. You'll need to do some more work if you want this code to work for any tuple of hashable 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;
user_19388590

Using std::integer_sequence can help:

struct hash_tuple {
    template <std::size_t...Index>
    size_t recursive_hash(const auto &x) const{
        return (boost::get<Index>(x) ^ ... );
    }

    template <template <typename> class Ts,typename...Args>
    size_t operator()(const Ts<Args...>& x) const{
        return recursive_hash<std::make_integer_sequence<int,sizeof...(Args)>>(x);
    }
};

using Map = std::unordered_map<Key, int, hash_tuple>;

This code is universal for all tuples to be uses as keys

user_176891600
Related