Efficiently erase a unique_ptr from an unordered_set

Question

I am storing the ownership of some objects inside an unordered_set, using unique_ptrs. But I don't know a good way to erase one of them from the set, when the time comes.

Code looks something like this:

typedef unique_ptr<MyType> MyPtr;

unordered_set<MyPtr> owner;

MyPtr p = make_unique<MyType>("foo")
MyType *pRaw = p.get();
owner.insert(std::move(p));

// Later ...

// I want to do something like this (cannot be written as-is, of course):
// owner.erase(pRaw);

Is there a way to do this? I can, of course, iterate the entire set with begin() and end(), but the whole point of putting them in the set is to make these lookups efficient.

Some things I have thought of already:

Use shared_ptr. This is the wrong abstraction for my case. Ownership is unique.
Use raw pointers, and forget about unique_ptr. This abandons all the advantages that unique_ptr provides.
Find the bucket with unordered_set::begin(key). As far as I know, there is no way for me to create a key that will match the unique_ptr I want to delete. But I'm happy to be proven wrong (:

(In truth, I solved this using eastl::unordered_set, with its find_as function for custom keys)

@Eljay: `erase` takes an iterator. How do I get the iterator? The other form of `erase` wants a `unique_ptr`, but I can't create one of those because they are ... unique (: — jwd, Feb 14 '20 at 05:04
Use `unordered_map` as mentioned here: https://stackoverflow.com/q/18939882 or wait till c++20 to get templated find method https://en.cppreference.com/w/cpp/container/unordered_set/find — balki, Feb 14 '20 at 05:23
How about storing the iterator returned from `insert` rather than the `unique_ptr`/raw pointer? — YiFei, Feb 14 '20 at 05:23
Umm I'm thinking when you insert you store the returned iterator and when you want to erase you use that one. Like `auto pRaw_iter = owner.insert(std::move(p)).first; owner.erase(pRaw_iter) /* instead of owner.erase(pRaw) */;`. This works if you know for sure which ones to erase, but if that's "to be determined" then this would be pretty painful... — YiFei, Feb 14 '20 at 05:26

L. F. · Accepted Answer · 2020-02-14T05:29:23.230

This is a tough case. erase has an overload that takes a const key_type& parameter, so we can try to create a "stale" unique_ptr to get the hash value of the element to be erased:

template <typename T>
auto erase(std::unordered_set<std::unique_ptr<T>>& set, T* ptr)
{
    std::unique_ptr<T> stale_ptr{ptr};
    auto ret = set.erase(stale_ptr);
    stale_ptr.release();
    return ret;
}

(live demo)

This version, however, is not exception safe in general, because release will not be called if set.erase throws an exception. This is not a problem in this case, since std::equal_to<std::unique_ptr<T>>::operator() never throws exception. In the general case, we can abuse unique_ptr (!) to enforce exception safety by ensuring that release is called regardless of whether the function is exited normally or exceptionally:

template <typename T>
auto erase(std::unordered_set<std::unique_ptr<T>>& set, T* ptr)
{
    std::unique_ptr<T> stale_ptr{ptr};

    auto release = [](std::unique_ptr<T>* p) { p->release(); };
    std::unique_ptr<std::unique_ptr<T>, decltype(release)> release_helper{&stale_ptr, release};

    return set.erase(stale_ptr);
}

(live demo)

Could we give a custom deleter to the `stale_ptr` instead? i.e. `auto release = [](T* p){};std::unique_ptr stale_ptr{ptr, release};return set.erase(stale_ptr);` It would be exception-safe because `release` will be invoked in the `unique_ptr`'s destructor. — Bernard, Feb 14 '20 at 13:35
@Bernard Supplying a deleter to `stale_ptr` directly would be nice, but unfortunately, the `erase` overload only accepts `const key_type&`, so `set.erase(stale_ptr)` will spit out errors :( — L. F., Feb 14 '20 at 14:32

Jarod42 · Answer 2 · 2020-02-14T13:24:24.197

In C++20, std::unordered_set::find can use equivalent key with transparent hash and KeyEqual, then you might do something similar to:

struct MyHash
{
    using is_transparent = void;

    auto operator()(MyType* p) const { return std::hash<MyType*>{}(p); }
    auto operator()(const MyPtr& p) const { return std::hash<MyType*>{}(p.get()); }
};

struct MyEqual
{
    using is_transparent = void;

    template <typename LHS, typename RHS>
    auto operator()(const LHS& lhs, const RHS& rhs) const
    {
        return AsPtr(lhs) == AsPtr(rhs);
    }
private:
    static const MyType* AsPtr(const MyType* p) { return p; }
    static const MyType* AsPtr(const MyPtr& p) { return p.get(); }

};

int main()
{
    std::unordered_set<MyPtr, MyHash, MyEqual> owner;

    MyPtr p = std::make_unique<MyType>();
    MyType *pRaw = p.get();
    owner.insert(std::move(p));

    auto it = owner.find(pRaw);
    if (it != owner.end()) {
        owner.erase(it);
    }
}

Efficiently erase a unique_ptr from an unordered_set

2 Answers2

Linked