Using shared_ptr/weak_ptr as Keys in Unordered Associative Containers

[Daryl Haresign]

Using shared_ptr/weak_ptr as Keys in Unordered Associative Containers

I recently had a desire to store a collection of weak_ptr objects.  As I had no requirements on the ordering, unordered_set seemed like a natural choice.

As it turns out, I had to use set as the required plumbing for the unordered associative containers is not present.

I therefore propose that the required plumbing is added.

Ordered Associative Containers

Ordered associative containers require a Compare.  For shared_ptr and weak_ptr this is provided through the owner_less function object, which delegates to the owner_before member function.  Typical implementations of this member involve comparing the address of the control blocks.

Unordered Associative Containers

Unordered containers require a Hash and a KeyEqual.  It probably follows to have these work similarly to owner_before, i.e. the Hash would hash the control block address, and the KeyEqual would compare the control block addresses.

To be able to provide the required plumbing, there are at least a few options.

Option 1

The first option would be to provide at the standard library level, a similar suite of member functions and function objects as is provided to support ordered associative containers:

• size_t shared_ptr::owner_hash() const noexcept;
• bool shared_ptr::owner_equal(...) const noexcept;
• size_t weak_ptr::owner_hash() const noexcept;
• bool weak_ptr::owner_equal(...) const noexcept;
• template <class T> struct owner_hash;
• template <class T> struct owner_equal;

This would provide everything someone needs out of the box.

Option 2

The second option observes the fact that given owner_hash, one could derive equality (and indeed ordering), based on that hash.  So it would only look to provide:

• size_t shared_ptr::owner_hash() const noexcept;
  
• size_t weak_ptr::owner_hash() const noexcept;
  
• template <class T> struct owner_hash;

This would require someone to provide their own equality function object which compares the result of calling 'owner_hash()'.

Option 3

Option 3, suggested by my colleague Masud Rahman, is similar in premise to option 2, and would instead provide at the standard library level the bare minimum required:

• const void * shared_ptr::control_block() const noexcept;
  
• const void * weak_ptr::control_block() const noexcept;

This would require someone to provide both a hash function object and an equality function object.

Please let me know what you think of the idea in general, and the options proposed below.  If I missed anything, I'm all ears.

Thanks,

Daryl.