How to make a c++11 std::unordered_set of std::wea

Question

I have a set like this: set<weak_ptr<Node>, owner_less<weak_ptr<Node> > > setName;

It works fine. But I would like to change it to an unordered set. However, I get about six pages of errors when I do that. Any ideas how to do that?

After looking through all the pages of error messages I found to lines that might help.

/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

The short and unfortunate answer is that while shared_ptr<> can be used safely as a key in an unordered set or map, weak_ptr<> cannot and must not. No amount of trickery can make it safe.

This is because weak_ptr's interface does not expose access to the shared control object, which is the basis of comparing by owner_before() when used in an ordered set or map.

While it may seem reasonable to lock the pointer and then hash the shared_ptr, it is not. If the last shared_ptr goes out of scope the hash value will change, which will result in undefined behaviour next time your set or map is iterated. This will most likely go un-noticed until your code is in production in front of customers where you get unexpected and inexplicable loss of functionality occasionally, but your unit tests will still pass flawlessly, giving you the false idea that your test coverage is good, your code is reliable and it is the users, hardware or network that's to blame.

So, in summary, if you're going to use weak_ptr's to build your non-owning object caches (for which they are excellent) you need use a std::set<weak_ptr> and suffer the miniscule performance hit (although in reality this will be dwarfed by the performance loss caused by the mutex that protects the set).

If you really want to use a weak_ptr as an unordered key you will have to write your own (hint: use the address of the shared control block as the basis for the hash function).

Answer 2

I don't think that suggested hash function is correct. If all shared pointers to the object disappears then weak_ptr<X>::lock() will return empty shared_ptr, whose hash value is probably zero. So the hash function can return different values throughout time.

I think that the correct solution here is to use boost::unordered_map<X*, boost::weak_ptr<X>>. Type X* can be easily use as a key to hash map and weak_ptr<X> as the value gives you chance to find out whether referenced object still exists.

To store value to this hash, you can use something like:

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

Answer 3

Since unordered_sets are hash-based you have to provide a hash function object for the std::weak_ptr data-type.

If you take a look at the unordered_set template-parameters

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

you'll notice that std::unordered_set provides you with a default std::hash<> template parameter. But since std::hash does only provide specializations for a specific set of data types, you might have to provide your own.

The error-message you quoted tells you, that no std::hash<> specialization for std::weak_ptr<> exists, so you have to provide your own hashing function for that:

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

Edit: You also need to provide an equality function, since no std::equal_to for weak_ptr is provided. Taking a possible way to do this from "Equality-compare std::weak_ptr" on Stackoverflow:

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

All combined this gives us the following:

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

Answer 4

Thanks to lx the following code now builds. To get it to build with gcc 4.7.2 I had to add two more 'const', so now the code bellow should be a complete working example of putting std::weak_ptr into a std::unordered_set.

#include <cstdlib>
#include <iostream>
#include <memory>
#include <string>
#include <unordered_set>
#include <functional>

using namespace std;

template<typename T>
struct MyWeakPtrHash : public std::unary_function<std::weak_ptr<T>, size_t> {
   size_t operator()(const std::weak_ptr<T>& wp) const
   {
      auto sp = wp.lock();
      return std::hash<decltype(sp)>()(sp);
   }
};

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) const
   {
      return !left.owner_before(right) && !right.owner_before(left);
   }
};

int main() {
    unordered_set<std::weak_ptr<string>, MyWeakPtrHash<string>,
                   MyWeakPtrEqual<string> > stringset;

    shared_ptr<string> shptr(new string("Hi there") );
    stringset.insert( shptr );
    cout << stringset.size() << endl;
}