Using tuple in unordered_map

Question

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?

Oloroso

Answer 1

The template arguments for an unordered_map looks like this:

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 is not specialized for 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 answer already addresses, 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 a std::tuple as key for std::unordered_map and here is the Live Example.

Intelligent

Can you please explain how you have defined key_hash? or what is being done inside key_hash? – Oloroso

@Zara See the link for more information. key_hash is defined above. Later, we use it as one of the template arguments (where unordered_map requires a Hash). – Intelligent

XOR'ing the fields is a terrible hash function. Please do not use this code as-is. See e.g. open-std.org/jtc1/sc22/wg21/docs/papers/2014/n3876.pdf – Willwilla

Answer 2

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. kk is not a type, it is an object. Perhaps you meant to make it a 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").

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

Stomachic

Answer 3

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-set will automatically add such support in 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;                                 
        }                                              

    };
}

Dumbbell

Answer 4

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

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

Pudens

map<T> works because it doesn't require the key type to be hashable. – Library

Answer 5

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

Salon

Thank you! By the way the functional hash has moved. I am not sure when, but in boost 1.72 it is in #include <boost/container_hash/extensions.hpp> I am not sure why the boost hash function for a tuple is not documented somewhere. Thanks again for the tip! – Voiceful

Answer 6

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

Ushaushant

white space is your friend. – Holiness

Answer 7

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;

Oligarch

Answer 8

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.

Prelacy

Note, this code requires boost:: – Holiness