Why isn't `std::hash` a customization point by overload as `std::begin`?

Question

As the title says, std::begin, std::end, std::swap, etc, are very well known std "customization points" (functions meant to be found by ADL). However, std::hash is, I think, the only std behaviour customizable by the user that implies to (A) open std namespace (B) create a partial specialization.

Why hasn't std::hash being designed as a customization point like the other ones, by overloading a function instead of partial specializing a class?

Also, to the best of my knowledge, `std::distance` is not a CPO at all. And `std::begin` itself is not either; `std::ranges::begin` is. — L. F., Sep 08 '19 at 03:31
I'll have to check that, but for your benefit, the C++11 and C++14 final drafts are available at https://timsong-cpp.github.io/cppwp/n3337/ and https://timsong-cpp.github.io/cppwp/n4140/ — L. F., Sep 08 '19 at 03:44
BTW, where does the standard library take a container? Because I didn't seem to find any. — L. F., Sep 08 '19 at 03:54
@L.F. iterator adaptors like `insert_iterator` takes them. `std::stack`, `std::queue` and `std::priority_queue` depends on them, and range-based loops are implemented by enabling ADL on `begin` and `end`: https://timsong-cpp.github.io/cppwp/n3337/stmt.ranged#1.3 — ABu, Sep 08 '19 at 04:00
Let us [continue this discussion in chat](https://chat.stackoverflow.com/rooms/199131/discussion-between-l-f-and-peregring-lk). — L. F., Sep 08 '19 at 04:16
@L.F. Question edited. I say this in a comment to reflect that our discussion refers to a previous version of the question. — ABu, Sep 08 '19 at 04:36
I think you're getting this all wrong. Neither `std::hash` nor `std::begin` are customization points. To allow your usertype to work with `std::begin` you simply add a `begin()` member function to it. For `std::hash` the situation is different. This is simply the default implementation of the hasher used in standard containers and the customization point is the `Hash` template argument of the container, not prying open `namespace std` and specializing `std::hash`. — Henri Menke, Sep 08 '19 at 05:19
@HenriMenke `begin` is always called in a ADL-friendly manner. This is basically the definition of a customization point. — ABu, Sep 16 '19 at 08:13

Henri Menke · Answer 1 · 2019-09-08T05:42:57.627

You have been taken in by a common misconception, but std::hash is not a customization point for hashing of user-defined types. Instead, std::hash is the default implementation of the hasher that is used by the standard containers. If you want to use the standard containers with user-defined types, then you should use their template arguments to supply a hasher.

Correct

All standard containers that require a hash function for their contents have a template argument that takes a function object whose call operator computes the hash.

#include <boost/functional/hash.hpp>
#include <unordered_set>

struct Point { int x, y; };

struct PointHasher {
    size_t operator()(Point const &p) {
        size_t seed = 0;
        boost::hash_combine(seed, p.x);
        boost::hash_combine(seed, p.y);
        return seed;
    }
};

int main() {
    std::unordered_set<Point, PointHasher> m;
}

Wrong

Writing into namespace std is usually undefined behaviour, see also What are the reasons that extending the std namespace is considered undefined behavior? There is an exception for template specializations under certain circumstances, but in this case it is not even necessary.

#include <boost/functional/hash.hpp>
#include <unordered_set>

struct Point { int x, y; };

namespace std {
    template<> struct hash<Point> {
        size_t operator()(Point const &p) {
            size_t seed = 0;
            boost::hash_combine(seed, p.x);
            boost::hash_combine(seed, p.y);
            return seed;
        }
    };
}

int main() {
    std::unordered_set<point> m;
}

By marking the common and recommended approach as Wrong, you are excluding the possibility of providing a default hash function for the standard unordered associative containers. `std::hash` is designed like this for a reason. — L. F., Sep 08 '19 at 06:56
It's allowed by the standard to add user specializations for `std` function or class templates as far as it depends on user-defined types. — ABu, Sep 16 '19 at 08:11

L. F. · Answer 2 · 2019-09-08T05:22:15.860

0

Like std::less, std::hash is meant to be a function object. For example, std::unordered_set takes a Hash template argument:

template <
    class Key                            ,
    class Hash      = std::hash<Key>     , // function object type
    class KeyEqual  = std::equal_to<Key> ,
    class Allocator = std::allocator<Key>
> class unordered_set;

That's why std::hash is a class template instead of a function template. You can specialize std::hash and make unordered_set default to using it, or you can provide your own hash function object.

edited Sep 08 '19 at 05:22

answered Sep 08 '19 at 05:10

L. F.

19,445
8
48
82

You should add that the customization point is the `Hash` template argument and not prying open `namespace std` and specializing `std::hash` for `Key`. – Henri Menke Sep 08 '19 at 05:20
1

“You can specialize `std::hash` and make `unordered_set` default to using it” No, you can't. Writing stuff into `namespace std` is undefined behaviour. – Henri Menke Sep 08 '19 at 05:39
4

@HenriMenke Specilizing `std::hash` is _not_ undefined. The standard makes an allowance for specializing standard library class templates for user-defined types. See [namespace.std](http://eel.is/c++draft/namespace.std#2). – Miles Budnek Sep 08 '19 at 06:35
The standard makes allowance to specialize any std template free function (not member functions) or template class as far as it depends on user defined types. This includes `std::hash`. – ABu Sep 08 '19 at 13:30

Why isn't `std::hash` a customization point by overload as `std::begin`?

2 Answers2

Correct

Wrong