c++boosthashstandards

Why did the C++ standards committee not include std::hash for pair and tuple?


As pointed out in answers to Generic hash for tuples in unordered_map / unordered_set and elsewhere, Boost has an implementation of boost::hash<tuple<string, string>>.

So, we can do things like:

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

std::tuple<string, string> t;
size_t bh = boost::hash<tuple<string, string>>{}(t);
boost::unordered_map<tuple<string, string>, int> bm;

but not:

size_t sh = std::hash<tuple<string, string>>{}(t); // error C2338: The C++ Standard doesn't provide a hash for this type.
std::unordered_map<tuple<string, string>, int> sm; // same error

Why didn't this make it into the C++ standard?

Extra points for references with a rationale given by the committee or other experts.


Solution

  • Proposals surrounding hashing of pairs and tuples have been written in one form or another numerous times:

    The original paper for std::unordered_map, N1456, even mentions the hashing of pairs in section V "Unresolved issues."

    P0029 mentions, as a problem with the design of std::hash, that:

    • It does not support composition efficiently or conveniently: if you want to implement your std::hash specialization in terms of the specializations of your members, you'll have to invent your own way of combining their hash values, and the result will be inefficient because it repeats the costly step of reducing the temporary hashing state to a size_t (notably, this is the reason std::hash is not specialized for std::pair, std::tuple, or containers).

    The committee initially seemed to be interested in P1406, details in the GitHub issue, however, the committee decided against it in a 2020 committee meeting:

    POLL: We want to go on with the direction (specialization of std::hash for the product types) of the paper, if the concerns (ODR, generic string hash) can be fixed.

    1 2 4 3 0

    No consensus

    CONSENSUS: We will not pursue P1406 (Add more std::hash specializations).

    To summarize: std::hash does not exist for pairs and tuples due to a handful of technical considerations including design questions and ODR.