Unordered map where key is a pair

Question

I have an unordered map where my key is a pair of <int, const Foo*> and value is a vector. I do not see any compilation or runtime error during insertion or lookup but I am not sure if this is most efficient code. Will the compiler create an efficient hash function for computing hash value of the key or should I use boost::hash?


class Foo {
  public:
   Foo():var1(0){};
   ~Foo();
   void func(int a) {
      var1 = a;
   }
   int var1;
}

int main()
{
    Foo f1;
    f1.func(10);
    const Foo* fp = &f1;
    std::unordered_map<std::pair<uint,const Foo*>,std::vector<uint>> umap1;
    umap1[std::make_pair(1,fp)].emplace_back(100);
}

`Will the compiler create an efficient hash function for computing hash value of the key` no, c++ compiler never creates any hash functions — Iłya Bursov, Jan 25 '23 at 00:58
Why is it not failing during compile time? So, I should use boost to create a hash function? — Pirate, Jan 25 '23 at 00:59
it fails to compile, see https://stackoverflow.com/questions/32685540/why-cant-i-compile-an-unordered-map-with-a-pair-as-key — Iłya Bursov, Jan 25 '23 at 01:02
You don't need boost for creating hash function, see example at https://en.cppreference.com/w/cpp/utility/hash. You'll also need function for keys comparison - but it is also covered in the link I provided — TenerowiczS, Jan 25 '23 at 01:13

Yakk - Adam Nevraumont · Answer 1 · 2023-01-30T18:20:07.453

std::hash<T> has no std::pair<X,Y> specialization. You have to provide one.

Boost's one isn't as bad as the first one you are likely to write, so feel free to use it. (It isn't perfect, but it isn't horrid).

The hashing trick I use is to first start with an ADL helper:

namespace MyNS {
  template<class T, class...Unused>
  std::size_t hash( T const& t, Unused... )->decltype( std::hash<T>{}(std::declval<T const&>()) ) {
    return std::hash<T>{}(t);
  }
  struct hasher {
    template<class T>
    std::size_t operator()(T const& t)const {
      return hash(t);
    }
  }
}

as written, MyNS::Hasher passed to a std::unordered_map<X,Y, MyNS::Hasher> will invoke std::hash<X> as its hasher.

But if you override hash in the namespace of X or in MyNS you'll call it instead. This allows us to extend stuff nicely.

namespace MyNS {
  std::size_t hash_combine( std::size_t lhs, std::size_t rhs ) {
    return ((lhs<<6)+(lhs>>3)) + rhs;
  }
  template<class...Szs>
  std::size_t hash_combine( std::size_t lhs ) {
    return lhs;
  }
  template<class...More>
  std::size_t hash_combine( std::size_t lhs, std::size_t rhs, More...more ) {
    return hash_combine( hash_combine(lhs, rhs), more... );
  }

  template<class T, class U>
  std::size_T hash( std::pair<T, U> const& p ) {
    return hash_combine( hash(p.first), hash(p.second) );
  }
}

I then add this. hash_combine can be written better (boost has an example of a better one), but it combines two size_t hashes into one. But the above one is better than nothing.

It takes 1 or more arguments and combines their hashes into one hash.

I then add an overload to hash for std::pair It invokes hash on its elements; this means pairs of pairs are supported. We can add tuple support:

  template<std::size_t...Is, class Tup>
  std::size_T hash( std::index_sequence<Is...>, Tup const& tup ) {
    return hash_combine( std::get<Is>(tup)... );
  }
  template<class...Ts>
  std::size_T hash( std::tuple<Ts...> const& tup ) {
    return hash_combine( std::make_index_sequence<sizeof...(Ts)>{}, tup );
 }

and vector support:

 template<class Seq>
 std::size_t hash_sequence(Seq const& v) {
   std::size_t r = 0;
   for (auto const& e:v) {
     r = hash_combine( r, hash(e) );
   }
   return r;
 }
 template<class T, class A>
 std::size_t hash(std::vector<T,A> const& v) {
   return hash_sequence(v);
 }

and similar for other containers.

Any class you need to support hash for is easy:

namespace SomeRandomNS {
  struct some_random_type {
    int state;
  };
  inline std::size_t hash( some_random_type const& x ) {
    using MyNS::hash;
    return hash(x.state);
  }
}

and done. For something more complex:

namespace SomeRandomNS {
  struct some_random_type {
    int state;
    double more_state;
    std::string even_more;
  };
  inline std::size_t hash( some_random_type const& x ) {
    using MyNS::hash;
    return hash(std::tie(x.state, x.more_state, x.even_more));
  }
}

and we are done (the tuple hash does the work for us).

Can you give me an example of what would be perfect way to implement this? — Pirate, Jan 30 '23 at 06:38

Unordered map where key is a pair

1 Answers1