Unordered Map with three unsigned chars as key

Question

I have to make an unordered_map consisting of the following keys and value:

• key: unsigned char, unsigned char, unsigned char

• value: structure(int,int)

Here is my code to define that:

namespace G {

typedef std::tuple< unsigned char, unsigned char , unsigned char> key_t;


struct IndexGuide
{
int index;
int SerialNo;

};

typedef std::unordered_map<const key_t,IndexGuide> GuideDouble;

}
using namespace G;

Is there anything wrong in this code because when I link these files on linux terminal. It gives me errors.Some part of the error as follows

In function `std::__detail::_Hash_code_base const, std::pair const, G::IndexGuide>, std::_Select1st const, G::IndexGuide> >, std::equal_to const>, std::hash const>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, false>::_M_bucket_index(std::__detail::_Hash_node const, G::IndexGuide>, false> const*, unsigned int) const':

Answer 1

You have to provide a hash function which tells std::unordered_map how to produce a hash value from your key_t. You can do it by specialization of hash template functor:

provide a Key:

struct Key{
    unsigned char  first;
    unsigned char second;
    unsigned char  third;

    bool operator==(const Key &other) const {
         return (first == other.first
            && second == other.second
            && third == other.third);
    }
};

specialize hash template:

namespace std {

  template <>
  struct hash< Key>
  {
    std::size_t operator()(const Key& k) const
    {
      using std::hash;

      // Compute individual hash values for first,
      // second and third and combine them using XOR
      // and bit shifting:

      return ((hash<char>()( k.first)
               ^ (hash<char>()( k.second) << 1)) >> 1)
               ^ (hash<int>()( k.third) << 1);
    }
  };

}

std::unordered_map< Key, IndexGuide> myMap;

As I said in comments, you can take a look at this SO thread.

Answer 2

So your basic problem is that you don't have a hasher for std::tuple -- the standard library does not currently come with one by default. I think this is an oversight.

You cannot add a default hasher for std::tuple -- either for all tuples or for your particular list -- because the standard says you aren't allowed to:

17.6.4.2.1 Namespace std [namespace.std]/1 The behavior of a C++ program is undefined if it adds declarations or definitions to namespace std or to a namespace within namespace std unless otherwise specified. A program may add a template specialization for any standard library template to namespace std only if the declaration depends on a user-defined type and the specialization meets the standard library requirements for the original template and is not explicitly prohibited.

So this leaves you with either writing a custom hasher for your tuple type, and passing it to your unordered_map, or using a type that isn't merely std::tuple for your key, or writing a custom hasher that supports every tuple (including recursive tuples) while also supporting hash<T> lookup for non-tuples. A 4th option would be to write your own ADL-based hash system and set it up so that types with valid std::hash specializations use that, with various other fallbacks.

I will illustrate the 3rd option above.

First, you want to be able to combine two hash values in a way that doesn't lead to many spurious collisions.

  inline std::size_t hash_result_combine(std::size_t lhs, std::size_t rhs)
  {
      return lhs ^( rhs + 0x9e3779b9 + (lhs<<6) + (lhs>>2));
  }

this takes two hash outputs, and combines them. We can then chain this any number of times. (constants borrowed from https://stackoverflow.com/a/7111460/1774667 )

Next, some indexing boilerplate. Most generic work with std::tuple requires this stuff:

  template<unsigned...>struct indexes{};
  template<unsigned Max, unsigned... Is>struct make_indexes:make_indexes<Max-1,Max-1,Is...> {};
  template<unsigned...Is>struct make_indexes<0,Is...>:indexes<Is...>{};

Finally, a hasher class that works with nearly every type:

  struct my_hasher {
    template<typename... Args>
    std::size_t operator()(indexes<>, std::tuple<Args...> const& tup) const {
      return 0;
    }
    template<unsigned I, unsigned... Is,typename... Args>
    std::size_t operator()(indexes<I, Is...>,std::tuple<Args...> const& tup) const {
      return hash_result_combine( (*this)(std::get<I>(tup)), (*this)(indexes<Is...>, tup) );
    }
    template<typename... Args>
    std::size_t operator()(std::tuple<Args...> const& tup) const {
      return (*this)(make_indexes<sizeof...(Args)>(), tup);
    }
    template<typename T>
    std::size_t operator()(T const& t) const { return std::hash<T>()(t); }
  };

you can pass my_hasher to an unordered_set in place of hash<T> for tuples, tuples containing tuples, or even for scalars -- it is very generous.

typedef std::unordered_map<const key_t,IndexGuide, my_hasher> GuideDouble;

and now we properly hash key_t.

Answer 3

unordered_set is implemented using a hash table.
in order to use unordered_set for a type that you defined you need to specialize the hash<> template for that type, as follows:

namespace std {
    template <> struct hash<key_t>
    {

        size_t operator()(const key_t & t) const
        {
            // the logic for hashing
        }
    };
}

Answer 4

There is no default hasher for std::tuple.

You may use this code snippet Generic hash for tuples in unordered_map / unordered_set