unordered_set using hash of value object's address

Question

I have a class which needs to have a std::unordered_set which holds non-copyable, non-moveable entity objects, and whose hash function hashes the instance's address. Something like the following:

class A
{
public:
    A();
    A(const A&) = delete;
    A(A&&) = delete;
    void operator=(const A&) = delete;
    void operator=(A&&) = delete;

    bool operator==(const A& other) { return this == &other; }
};

template<>
struct std::hash<A>
{
    size_t operator()(const A& obj) const
    {
        return std::hash<A*>()(&obj);
    }
};

class B
{
private:
    std::unordered_set<A> entities;
};

If emplace() is always used instead of insert(), is it safe to use unordered_set in this way? Does the standard specify that an implementation can't move node objects after they are constructed?

What about if A were moveable? Is it guaranteed that the hash function will be called on the object owned by the set, or since the standard library prefers to think of everything as value-objects, is it allowed to hash an inserted object before storage is allocated for it?

As a final thought, I know I could get around all this by using std::unordered_set<std::unique_ptr<A>>, but I'd like to use a custom allocator for the A objects, and I don't want to override new and delete for A.

Answer 1

I still think you are better off using a std::list. Consider:

#include <iostream>
#include <list>

class A
{
public:
    int i_;
    A(int i) : i_(i) {}
    A(const A&) = delete;
    A(A&&) = delete;
    void operator=(const A&) = delete;
    void operator=(A&&) = delete;
};

int main()
{
    std::list< A > l;

    // inserting elements
    auto it1 = l.emplace( l.end(), 1 ); // note: complexity is O(1)
    auto it2 = l.emplace( l.end(), 2 );
    auto it3 = l.emplace( l.end(), 3 );
    auto it4 = l.emplace( l.end(), 4 );

    // deleting an element by iterator
    l.erase( it2 ); // note: complexity is O(1)
    // note: it2 is now invalid

    // accessing element by iterator
    it3->i_ = 42;

    for( const auto& e : l ) {
        std::cout << e.i_ << std::endl;
    }

    // silence compiler warnings
    (void)it1;
    (void)it4;
}

In the above, all your use-cases should have an efficient implementation. You can avoid the overhead of calculating the hash and having the hash-map. It's even more efficient as your hash-based approach, for the list both operations are O(1) and much more light-weigth wrt the implementation. And storing the iterator is not much different from storing a pointer to the element directly.

Also, it is guaranteed that this works for non-copyable and non-movable types. See the documentation for std::list::emplace.

Answer 2

Using the address of an object as a hash pretty much guarantees that you won't find the object unless you already hold a pointer to the object other than iteration through the hash. You'll need to come up with a different approach to get a hash from your object. That said, once consructed inside the hash the object's address won't change.

Answer 3

As Dietmar mentions, once constructed, the value's address can't change. As far as the second part of the question, the standard seems to not only allow, but require implementations to call the hash/equal_to functors on an object passed to insert() by reference, rather than requiring the construction of a node first and calling the functions on that object:

From 23.2.5 Table 103 — Unordered associative container requirements

pair<iterator, bool> a_uniq.insert(t)

Effects: Inserts t if and only if there is no element in the container with key equivalent to the key of t.