高效地从 unordered_set 中删除 unique_ptr

Question

我使用 unique_ptr 将某些对象的所有权存储在 unordered_set 中。但是我不知道有什么好的方法可以在适当的时候从集合中删除其中一个。

代码看起来像这样：

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

有办法吗？当然，我可以用 begin() 和 end() 迭代整个集合，但将它们放入集合的全部意义在于使这些查找更加高效。

有些事情我已经想到了：

使用shared_ptr。对于我的情况，这是错误的抽象。所有权是唯一的。
使用原始指针，忘记 unique_ptr。这放弃了 unique_ptr 提供的所有优势。
找到 unordered_set::begin(key) 的桶。据我所知，我无法创建一个与我要删除的 unique_ptr 相匹配的密钥。但我很高兴被证明是错误的 (:

（事实上，我使用 eastl::unordered_set 解决了这个问题，它的 find_as 自定义键功能）

Answer 1

这是一个棘手的案例。 erase 有一个重载需要一个 const key_type& 参数，所以我们可以尝试创建一个 "stale" unique_ptr 来获取要擦除的元素的哈希值：

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)

然而，这个版本通常不是异常安全的，因为如果 set.erase 抛出异常，则不会调用 release。在这种情况下这不是问题，因为 std::equal_to<std::unique_ptr<T>>::operator() 从不抛出异常。在一般情况下，我们可以滥用 unique_ptr (!) 通过确保无论函数是正常退出还是异常退出都调用 release 来强制执行异常安全：

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)

Answer 2

在 C++20 中，std::unordered_set::find 可以使用 equivalent key with transparent hash 和 KeyEqual，那么你可能会这样做类似于：

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);
    }
}

高效地从 unordered_set 中删除 unique_ptr

Efficiently erase a unique_ptr from an unordered_set

c++

unordered-set

unique-ptr

c++14