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

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>]’:

Lactam

"I have a set like this: set, owner_less > > setName;" What do you mean by that? – Salaam

@jogojapan Thanks I already tried that, and it does not help. – Lactam

@JoachimPileborg I have only ask about five questions and only one has ever been answered, and that was by me. So that is why I have never accepted any answers. Thanks for the reminder. – Lactam

You have a total of eight questions, of which six have answers. Two of the questions have multiple answers. And even when you write your own answer, you can still accept it. – Cortie

Answer 1

Please read Richard Hodges answer below as mine is incorrect, despite being the accepted solution.

---

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;

Month

Is it possible to make MyWeakPtrHash take a weak_ptr<Node> and then turn it into a shared_ptr and get the hash of that and return it. I have been trying a few different things but have not got anything to compile. – Lactam

Since std::hash provides a specialization for std::shared_ptr you could utilize that. I updated the example to make use of this. I don't know if this will work as expected though... :| – Month

The hash of a key is assumed to be constant, but your function lets it be modified: if the weak_ptr expires, wp.lock() will return an empty shared_ptr, which will have a different hash. This will cause undefined behavior. – Disdainful

Using this with T=void results in an error about qualifiers being discarded. Why? How to fix? – Bartlett

Answer 2

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

Minoan

I was thinking about this a bit. Given weak_ptr doesn't provide any access to its internal state, it's kinda tricky. What about a wrapper class that contains a weak_ptr<T> and a const T* where upon construction, the T* gets set to weak.lock().get() and is used for hashing, but equality testing would compare against weak.lock(). That way, the T could be destroyed and the hash wouldn't change but equality would. – Milligan

@Milligan this assumes that the address is never used twice for two different objects. This is not necessarily true. – Minoan

yes if it’s intended as a unique hash, like a sha1, where we assume hash equality means object equality, but shouldn’t it work fine (ish) in a hash table? As in, you insert an item, the pointed-to object gets destroyed, you make a new object that happens to be in the same memory location, you insert it, it hashes the same but compares non-equal since the original item now compares as nullptr so the new thing is added. I smell red flags, but I’m not convinced this approach is doomed. – Milligan

@Milligan it's doomed. If you're going to wrap the weak_ptr, then you'll want to generate a unique ident with each object. Every weak_ptr created will need to know the unique_id. In this case, why not just use the unique_id as an unordered_map key? – Minoan

I see the problem. What if the standard provided a hash along the lines of owner_before? In my implementation, std::weak_ptr<T>::owner_before(const weak_ptr<U>& p) is just { return __cntrl_ < p.__cntrl_; } where __cntrl_ is a pointer to the control block. So if std::weak_ptr provided a std::size_t unique_id() const method that cast __cntrl_ to a std::size_t, we could key off that unique_id() and could hash it. – Milligan

@Milligan yes, it's a shame that wasn't made available. – Minoan

This answer appears to not be entirely correct. It's partly right, in that "you can't do it today", but the C++ standards committee has discussed this, and they do have a way to do it. See this proposal and a discussion from 12 years ago: #4751004 – Manuelmanuela

@Manuelmanuela I don’t think I claimed that there was no way to do it. Adding hash and equality support to the control block is an obvious solution, which to this day has not been proposed or implemented in the standard. – Minoan

I linked the proposal above. It is here – Manuelmanuela

... and last but not least: there is a working solution to this problem given in #70131967 – Manuelmanuela

@Manuelmanuela I saw the proposal but it unfortunately has not been adopted. Yakk’s solution is a good one. – Minoan

Answer 3

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

Psychoactive

This uses the memory location of a possibly-expired object as the key, which means that you need to think about the possibility that an object to be inserted may have been allocated at the same location as a previous object whose key is still present in the map. – Pratique

weka_ptr<...> makes sure whether previous object still lives or not. If it lives, one cannot have different object with the same address, if it doesn't then one can replace it. Insert doesn't allow to insert <K, V> with the same key twice (if you don't have multimap), so the above satement should in fact check, whether insert succeeded or not and act accordingly. – Psychoactive

Answer 4

A working solution is given here: How to compute hash of std::weak_ptr? Below is a slightly expanded variant that adds missing details. Unlike the earlier answers given above, this works because the hash is computed and stored before the shared_ptr count drops to zero.

namespace foobar
{
// Public inheritance was used to avoid having to
// duplicate the rest of the API. Unfortunately this
// allows object slicing. So, an alternate solution is
// to use private inheritance, and `using` to provide
// the missing API.
template<class T>
struct hashable_weak_ptr : public std::weak_ptr<T>
{
   hashable_weak_ptr(std::shared_ptr<T>const& sp) :
      std::weak_ptr<T>(sp)
   {
      if (!sp) return;
      _hash = std::hash<T*>{}(sp.get());
   }

   std::size_t get_hash() const noexcept { return _hash; }

   // Define operator<() in order to construct operator==()
   // It might be more efficient to store the unhashed
   // pointer, and use that for equality compares...
   friend bool operator<(hashable_weak_ptr const& lhs,
                         hashable_weak_ptr const& rhs)
   {
      return lhs.owner_before(rhs);
   }
   friend bool operator!=(hashable_weak_ptr const& lhs,
                          hashable_weak_ptr const& rhs)
   {
      return lhs<rhs or rhs<lhs;
   }
   friend bool operator==(hashable_weak_ptr const& lhs,
                          hashable_weak_ptr const& rhs)
   {
      return not (lhs != rhs);
   }
   private:
      std::size_t _hash = 0;
};
} // namespace foobar

namespace std
{

// Specializations in std namespace needed
// for above to be usable.
template<class T>
struct owner_less<foobar::hashable_weak_ptr<T>>
{
   bool operator()(const foobar::hashable_weak_ptr<T>& lhs,
                   const foobar::hashable_weak_ptr<T>& rhs) const noexcept
   {
      return lhs.owner_before(rhs);
   }
};

template<class T>
struct hash<foobar::hashable_weak_ptr<T>>
{
   std::size_t operator()(const foobar::hashable_weak_ptr<T>& w) const noexcept
   {
      return w.get_hash();
   }
};
} // namespace std

A variant of this question was first asked here: Why was std::hash not defined for std::weak_ptr in C++0x? and the latest standards committee draft that resolves this is here: JTC1 WG21 P1901.

Manuelmanuela