如何制作std :: weak_ptr的c ++ 11 std :: unordered_set

Question

我有这样的一套: set<weak_ptr<Node>, owner_less<weak_ptr<Node> > > setName;

它工作正常.但我想将它改为无序集.但是,当我这样做时,我得到大约六页的错误.任何想法如何做到这一点？

查看了所有错误消息页面后,我发现了可能有用的行.

/usr/include/c++/4.7/bits/functional_hash.h:60:7: error: static assertion failed: std::hash is not specialized for this type
/usr/include/c++/4.7/bits/stl_function.h: In instantiation of ‘bool std::equal_to<_Tp>::operator()(const _Tp&, const _Tp&) const [with _Tp = std::weak_ptr<Node>]’:

Answer 1

简短而不幸的答案是,虽然shared_ptr<>可以安全地用作无序集或地图中的密钥,weak_ptr<>但不能也不能.没有多少诡计可以使它安全.

这是因为它weak_ptr的接口不公开对共享控制对象的访问,这是owner_before()在有序集或映射中使用时的比较基础.

虽然锁定指针然后散列它似乎是合理的shared_ptr,但事实并非如此.如果最后一个shared_ptr超出范围,则哈希值将更改,这将导致下次迭代set或map时出现未定义的行为.在您的代码在客户面前投入生产之前,您很可能不会注意到,偶尔会出现意外和无法解释的功能,但您的单元测试仍然会完美无缺,让您错误地认为您的测试覆盖率良好,您的代码是可靠的,应该归咎于用户,硬件或网络.

因此,总而言之,如果您打算使用weak_ptr来构建非拥有对象缓存(它们非常出色),您需要使用a std::set<weak_ptr>并遭受微乎其微的性能损失(尽管实际上这会因性能损失而相形见绌)由mutex保护集合引起的).

如果你真的想使用a weak_ptr作为无序密钥,你必须自己编写(提示:使用共享控制块的地址作为散列函数的基础).

Answer 2

我不认为建议的哈希函数是正确的.如果对象的所有共享指针都消失,那么weak_ptr<X>::lock()将返回空的shared_ptr,其哈希值可能为零.因此哈希函数可以在整个时间内返回不同的值.

我认为这里正确的解决方案是使用 boost::unordered_map<X*, boost::weak_ptr<X>>.类型X*可以很容易地用作哈希映射的关键字,weak_ptr<X>因为该值可以让您查明引用的对象是否仍然存在.

要将值存储到此哈希,您可以使用以下内容:

if (boost::shared_ptr<X> p = wp.lock()) {
    // weak_ptr is still valid
    ptrs.insert(std::make_pair(p.get(), p));
}

Answer 3

请阅读下面理查德·霍奇斯的答案，因为我的答案是不正确的，尽管这是公认的解决方案。

由于unordered_sets是基于哈希的，因此您必须为 std::weak_ptr 数据类型提供哈希函数对象。

如果你看一下 unordered_set 模板参数

template<class Key,
    class Hash = std::hash<Key>,
    class Pred = std::equal_to<Key>,
    class Alloc = std::allocator<Key> >
    class unordered_set;

您会注意到 std::unordered_set 为您提供了默认的 std::hash<> 模板参数。但由于 std::hash 只提供特定数据类型集的专业化，因此您可能必须提供自己的数据类型。

您引用的错误消息告诉您，不存在 std::weak_ptr<> 的 std::hash<> 专门化，因此您必须为此提供自己的哈希函数：

template<typename T>
struct MyWeakPtrHash : public std::unary_function<std::weak_ptr<T>, size_t> {
   size_t operator()(const std::weak_ptr<T>& wp)
   {
      // Example hash. Beware: As zneak remarked in the comments* to this post,
      // it is very possible that this may lead to undefined behaviour
      // since the hash of a key is assumed to be constant, but will change
      // when the weak_ptr expires
      auto sp = wp.lock();
      return std::hash<decltype(sp)>()(sp);
   }
};

编辑： 您还需要提供一个相等函数，因为没有为weak_ptr提供std::equal_to。从Stackoverflow 上的“Equality-compare std::weak_ptr”中采取一种可能的方法来做到这一点：

template<typename T>
struct MyWeakPtrEqual : public std::unary_function<std::weak_ptr<T>, bool> {

   bool operator()(const std::weak_ptr<T>& left, const std::weak_ptr<T>& right)
   {
      return !left.owner_before(right) && !right.owner_before(left);
   }
};

所有这些结合起来给我们带来以下结果：

std::unordered_set<std::weak_ptr<T>,
                   MyWeakPtrHash<T>,
                   MyWeakPtrEqual<T>> wpSet;