Document Number: N3573
Date: 2013-03-10
Project: Programming Language C++, Library Working Group
Reply-to: Mark Boyall wolfeinstein@gmail.com
The rationale for this proposal is a simple pair of use cases, and extends the Standard unordered_map and unordered_set to permit them. The first is the use of alternative types as key. For example, currently, it is impossible to look up by a type other than the key type. This sounds reasonable but is actually fairly limiting. Consider
int main() {
std::unordered_set<std::unique_ptr<T>> set;
}Whilst it's possible to insert into the set, there is no means to erase or test for membership, as that would involve constructing two unique_ptr to the same resource. However, there is no implementation reason to prevent lookup by an arbitrary key type, T, as long as hash(t) == hash(k) for any key k in the map, if t == k.
Secondly, it is impossible to override the hash or equivalence function for a given lookup. This can be used for localized optimizations- especially caching. For example,
int main() {
std::unordered_map<std::string, int> map;
std::string value;
std::size_t hash_cache;
bool dirty;
// later
map.find(value, [&](std::string& val) {
if (!dirty) return hash_cache; else return std::hash<>()(val);
});
}
Additionally, in n3421, std::hash was left out of the list of function objects which are now more generic. This proposal would add it. The templated function call operator of std::hash<>() would forward it to the explicit argument version.
namespace std {
template<typename T = void> struct hash;
template<> struct hash<void> {
template<typename T> std::size_t operator()(T&& t) {
return std::hash<typename std::decay<T>::type>()(std::forward<T>(t));
}
};
}
These two interface limitations are overcome by presenting new functions. Whilst insertion cannot be further generalized, erasure and lookup both can be.
template<typename T, typename Hash = std::hash<>, typename Eq = std::equal_to<>>
iterator find(T t, Hash h = Hash(), Eq e = Eq());
template<typename T, typename Hash = std::hash<>, typename Eq = std::equal_to<>>
const_iterator find(T t, Hash h = Hash(), Eq e = Eq()) const;
In this case, h(t) gives the hash value of t, and e(t, k) returns whether or not t is equal to k, for some key k. Also proposed are similar variants for erase(), and operator[] for unordered_map. The operator can't take the additional function object arguments, so std::hash<> and std::equal_to<> will be used. Given these functions, it's quite possible to implement both of the use cases described above.