0

Same goes for std::unordered_map vs std::map. It means that std::map can store objects of type std::array<T,N> for primitive T's but std::unordered_map cannot.

TonySalimi
  • 8,257
  • 4
  • 33
  • 62
abcdefasf
  • 79
  • 1
  • 3

1 Answers1

0

std::array<T, N> is not hashable by default. So, you need to implement your own hashing function for this type. A simple example hash function can be like this (adopted from here):

#include <set>
#include <array>
#include <unordered_set>

const int N = 10;


struct array_hasher
{
   std::size_t operator()(std::array<int, N> const& arr) const 
   {
      std::size_t seed = 0;
      for (const auto& i : arr) 
      {
         seed ^= std::hash<int>{}(i) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
      }
      return seed;
   }
};

int main()
{
   std::set<std::array<int, N>> x = {};
   std::unordered_set<std::array<int, N>, array_hasher> y = {};

   return 0;
}
TonySalimi
  • 8,257
  • 4
  • 33
  • 62
  • That's a good tidbit, but it's worth pointing out that `unordered_set` requires that its members have unchanging values. That is, if the array or its hash changes, all guarantees go out the window. – Tim Roberts Aug 18 '22 at 23:55
  • Oh so std::set doesn't need a hashing function? – abcdefasf Aug 18 '22 at 23:58
  • @abcdefasf `std::set` is ordered. You need comparison instead. – Deduplicator Aug 18 '22 at 23:59
  • @TimRoberts Agreed ! In an `unordered_set<>`, each object's value is its key. So, the objects should not be changed. – TonySalimi Aug 19 '22 at 00:03
  • @abcdefasf As pointed by @Deduplicator, `std::set` is a tree-like data structure. It means that it always needs a comparison mechanism for its elements (which is already supported by `std::array` itself). On the other hand, `std::unordered_set` is a hash-table-like data structure, so it needs a hashing function for its elements. As far as this hashing function does not exist by default in standard library (for `std::array`), you need to implement it yourself ! – TonySalimi Aug 19 '22 at 00:08
  • 4
    Specializing `std::hash` on a `std::array` is UB. Furthermore, that's a really bad hash function. – Passer By Aug 19 '22 at 00:40
  • More specifically, specializing `std::hash` on a standard library type is Undefined Behavior. And this hash only produces odd numbers. – Drew Dormann Aug 19 '22 at 01:39
  • No reason to specialize `std::hash` for `std::array` (technical UB) Just add a lambda – doug Aug 19 '22 at 04:48