Are there no specializations of std::hash for standard containers?

Question

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.

Brawn

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. – Petrozavodsk

@Steve: Which 4 concrete string classes? – Brawn

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. – Petrozavodsk

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? – Kraken

@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. – Petrozavodsk

@FredOverflow: I would look up the code of boost::hash_combine, were I to implement hashing on collection. – Pirozzo

@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. – Precatory

boost::hash_combine uses seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2); if anyone is curious. That looks a bit more robust. – Chuff

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." – Lowdown

Answer 1

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.

Reggi

Yeah, range_hash sounds like it should be in the standard. – Brawn

Answer 2

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

Vanhoose