27

I just found myself a little bit surprised being unable to simply use a

std::unordered_set<std::array<int, 16> > test;

because there does not seem to be a std::hash specialization for std::arrays. Why is that? Or did I simply not find it? If there is indeed none, can the following implementation attempt be simplified?

namespace std
{
    template<typename T, size_t N>
    struct hash<array<T, N> >
    {
        typedef array<T, N> argument_type;
        typedef size_t result_type;

        result_type operator()(const argument_type& a) const
        {
            hash<T> hasher;
            result_type h = 0;
            for (result_type i = 0; i < N; ++i)
            {
                h = h * 31 + hasher(a[i]);
            }
            return h;
        }
    };
}

I really feel this should somehow be part of the standard library.

Community
  • 1
  • 1
fredoverflow
  • 256,549
  • 94
  • 388
  • 662
  • 3
    There really isn't one, only `std::string` and friends have that privilege. Would I be really unpopular if I said that it's because C++'s effort to drag itself towards the current state of the art in terms of standard data structures has not yet done the whole job? Actually, there aren't any required `hash` specializations for templates (and which would in turn require their template arguments to be hashable). The only required specializations are for built-in type and four concrete string classes. So I suspect that a line was drawn there. – Steve Jessop Nov 06 '11 at 13:54
  • @Steve: Which 4 concrete string classes? – fredoverflow Nov 06 '11 at 14:05
  • 2
    `string`, `u16string`, `u32string`, `wstring` (21.6 in C++11). I'd say that `pair` and `tuple` should be the next-highest-priority targets, followed by standard containers, followed by a default hash for any aggregate type composed of hashable members. – Steve Jessop Nov 06 '11 at 14:08
  • 1
    Obviously the `string` hasher requires an internal function for hashing a block of memory. I wonder why they did not require implementations to expose it directly? – Nemo Nov 06 '11 at 14:12
  • @Nemo: I don't think it's necessarily that simple, the collation locale facet has a `hash` function of its own, presumably so that you can collapse different characters together in a locale-dependent manner to keep `hash` consistent with comparisons. So it is exposed, but I don't know whether or not the specializations of `std::hash` for string types are supposed to use it, I'm not properly familiar with this stuff. – Steve Jessop Nov 06 '11 at 14:15
  • 1
    @FredOverflow: I would look up the code of `boost::hash_combine`, were I to implement hashing on collection. – Matthieu M. Nov 06 '11 at 14:47
  • 2
    @nemo Nobody wrote it up as a paper to the committee. Things only get into the standard if somebody cares enough to make it happen. – Alan Stokes Nov 06 '11 at 19:58
  • 1
    `boost::hash_combine` uses `seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);` if anyone is curious. That looks a bit more robust. – Rag Feb 08 '14 at 01:31
  • Unfortunately I think this code in theory results in undefined behavior (at least in C++11), because the declaration does not depend on a user-defined type. From §17.6.4.2.1.1: "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." – Sami Liedes Jul 03 '14 at 10:17

2 Answers2

12

Not an answer, but some useful information. The Feb draft of the C++11 standard specifies that std::hash is specialized for these types:

  • error_code § 19.5.5
  • bitset<N> § 20.5.3
  • unique_ptr<T, D> § 20.7.2.36
  • shared_ptr<T, D> § 20.7.2.36
  • type_index § 20.13.4
  • string § 21.6
  • u16string § 21.6
  • u32string § 21.6
  • wstring § 21.6
  • vector<bool, Allocator> § 23.3.8
  • thread::id § 30.3.1.1

And all these types: § 20.8.12

template <> struct hash<bool>;
template <> struct hash<char>;
template <> struct hash<signed char>;
template <> struct hash<unsigned char>;
template <> struct hash<char16_t>;
template <> struct hash<char32_t>;
template <> struct hash<wchar_t>;
template <> struct hash<short>;
template <> struct hash<unsigned short>;
template <> struct hash<int>;
template <> struct hash<unsigned int>;
template <> struct hash<long>;
template <> struct hash<long long>;
template <> struct hash<unsigned long>;
template <> struct hash<unsigned long long>;
template <> struct hash<float>;
template <> struct hash<double>;
template <> struct hash<long double>;
template<class T> struct hash<T*>;
Mooing Duck
  • 64,318
  • 19
  • 100
  • 158
11

I'm not sure why the standard library hasn't included this, but Boost has hashing for all sorts of things made up from hashable types. The key function for this is hash_combine, which you are welcome to copy from boost/functional/hash/hash.hpp.

Using hash_combine, Boost derives a range_hash (just combining the hashes of a each element of a range), as well as pair and tuple hashers. The range_hash in turn can be used to hash any iterable container.

Kerrek SB
  • 464,522
  • 92
  • 875
  • 1,084