hash map of vectors, check for span key

Question

Given an unordered_map<vector<T*>,V> with appropriate hash function, is it possible to check the existence of a value for a key in the form of a span<T*> without transforming it to a vector (and allocating heap memory) first? We can assume sizes of all keys (both vectors and spans) being equal, but unknown at compile time.

The best I can come up with is to make a hash set set<int64_t> of hash values in the map, calculate the hash of the span, and only convert it to a vector if its hash exists. But all of this seems quite cumbersome, given that a span has all the information needed in this use case.

I'd be happy too if we find some alternative key type for the map that works with spans. Heck, maybe unordered_map<span<T*>,pair<vector<T*>,V>> works, where the span key actually stores the data pointer and size of its corresponding value vector?

Answer 1

You want a transparent hash (and equality) for your map. Because you can construct a std::span from a std::vector, you only need to implement it for std::span<T*>. You will have to use find rather than operator[] or at, until C++26.

struct hash_span {
    using is_transparent = void;
    std::size_t operator()(std::span<T*> data) { /* existing code here */ }
};

struct equal_span {
    using is_transparent = void;
    bool operator()(std::span<T*> lhs, std::span<T*> rhs) { /* existing code here */  }
};

Which then gets used as unordered_map<vector<T*>, V, hash_span, equal_span>.