Document Number: N3573

Date: 2013-03-10

Project: Programming Language C++, Library Working Group

Reply-to: Mark Boyall wolfeinstein@gmail.com

Heterogenous extensions to unordered containers

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.