Search code examples
c++c++14unique-ptrunordered-set

Efficiently erase a unique_ptr from an unordered_set


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)


Solution

  • 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)