Raw pointer lookup for sets of unique_ptrs

Question

I often find myself wanting to write code like this:

class MyClass
{
public:
  void addObject(std::unique_ptr<Object>&& newObject);

  void removeObject(const Object* target);

private:
  std::set<std::unique_ptr<Object>> objects;
};

However, much of the std::set interface is kind of useless with std::unique_ptrs since the lookup functions require std::unique_ptr parameters (which I obviously don't have because they're owned by the set itself).

I can think of two main solutions to this.

1. Create a temporary unique_ptr for lookup. For example, the above removeObject() could be implemented like:

   void MyClass::removeObject(const Object* target)
   {
     std::unique_ptr<Object> targetSmartPtr(target);
     objects.erase(targetSmartPtr);
     targetSmartPtr.release();
   }
   

2. Replace the set with a map of raw pointers to unique_ptrs.

     // ...
     std::map<const Object*, std::unique_ptr<Object>> objects;
   };
   

However, both seem slightly stupid to me. In solution 1, erase() isn't noexcept, so the temporary unique_ptr might delete the object it doesn't really own, and 2 requires double the storage for the container unnecessarily.

I know about Boost's pointer containers, but their current features are limited compared to modern C++11 standard library containers.

I was recently reading about C++14 and came across "Adding heterogeneous comparison lookup to associative containers". But form my understanding of it, the lookup types must be comparable to the key types, but raw pointers aren't comparable to unique_ptrs.

Anyone know of a more elegant solution or an upcoming addition to C++ that solves this problem?

Answer 1

Exception-safe solution with efficient hash-based lookup and no transparency restriction (this is a copy of my answer to a similar question):

/*
 * Behaves like an std::unique_ptr that
 * does not delete the pointer on destruction
*/
template<typename T>
class bad_ptr
{
private:
    std::unique_ptr<T> m_ptr;

public:
    // construct from a pointer
    bad_ptr(T* ptr) : m_ptr{ptr} { }

    // convert to an std::unique_ptr&
    operator const std::unique_ptr<T>&() {
        return m_ptr;
    }

    // release the pointer without deleting it
    ~bad_ptr() {
        m_ptr.release();
    }
};

Usage:

struct test_struct {
    int a;
    int b;
};

int main()
{
    std::unordered_set<std::unique_ptr<test_struct>> set;
    auto raw_ptr = set.insert(std::make_unique<test_struct>(1, 2)).first->get();

    // error
    // set.erase(raw_ptr);

    // works
    set.erase(bad_ptr{raw_ptr});
}

So here you'd have:

void MyClass::removeObject(const Object* target)
{
  objects.erase(bad_ptr{target});
}

Answer 2

Another possibility, close to the accepted answer, but a little different and simplified.

We can exploit the fact that standard comparator std::less<> (with no template arguments) is transparent. Then, we can supply our own comparison functions in the global namespace:

// These two are enough to be able to call objects.find(raw_ptr)
bool operator<(const unique_ptr<Object>& lhs, const Object* rhs) {
  return std::less<const Object*>()(lhs.get(), rhs);
}
bool operator<(const Object* lhs, const unique_ptr<Object>& rhs) {
  return std::less<const Object*>()(lhs, rhs.get());
}

class MyClass
{
  // ...

private:
  std::set<std::unique_ptr<Object>, std::less<>> objects;  // Note std::less<> here
};

Answer 3

In C++14, std::set<Key>::find is a template function if Compare::is_transparent exists. The type you pass in does not need to be Key, just equivalent under your comparator.

So write a comparator:

template<class T>
struct pointer_comp {
  typedef std::true_type is_transparent;
  // helper does some magic in order to reduce the number of
  // pairs of types we need to know how to compare: it turns
  // everything into a pointer, and then uses `std::less<T*>`
  // to do the comparison:
  struct helper {
    T* ptr;
    helper():ptr(nullptr) {}
    helper(helper const&) = default;
    helper(T* p):ptr(p) {}
    template<class U, class...Ts>
    helper( std::shared_ptr<U,Ts...> const& sp ):ptr(sp.get()) {}
    template<class U, class...Ts>
    helper( std::unique_ptr<U, Ts...> const& up ):ptr(up.get()) {}
    // && optional: enforces rvalue use only
    bool operator<( helper o ) const {
      return std::less<T*>()( ptr, o.ptr );
    }
  };
  // without helper, we would need 2^n different overloads, where
  // n is the number of types we want to support (so, 8 with
  // raw pointers, unique pointers, and shared pointers).  That
  // seems silly:
  // && helps enforce rvalue use only
  bool operator()( helper const&& lhs, helper const&& rhs ) const {
    return lhs < rhs;
  }
};

then use it:

typedef std::set< std::unique_ptr<Foo>, pointer_comp<Foo> > owning_foo_set;

now, owning_foo_set::find will accept unique_ptr<Foo> or Foo* or shared_ptr<Foo> (or any derived class of Foo) and find the correct element.

Outside of C++14, you are forced to use the map to unique_ptr approach, or something equivalent, as the signature of find is overly restrictive. Or write your own set equivalent.

Answer 4

While definitely a hack, I just realized it's possible to construct a temporary "dumb" unique_ptr with placement new and not risk de-allocation. removeObject() could be written something like this:

void MyClass::removeObject(const Object* target)
{
  alignas(std::unique_ptr<Object>)
  char dumbPtrData[sizeof(std::unique_ptr<Object>)];

  objects.erase(
      *::new (dumbPtrData) std::unique_ptr<Object>(const_cast<Object *>(target)));
}

This solution would work for std::unordered_set, std::map keys, and std::unordered_map keys as well, all using standard C++11 only, with practically zero unnecessary overhead.

Answer 5

UPDATE 2: Yakk is correct, there is no way to do this with standard C++11 containers without significant compromises. Either something will run in linear time in the worst case or there are those workarounds that you write in your question.

There are two workarounds that I would consider.

I would try a sorted std::vector, similarly to boost::container::flat_set. Yes, the inserts / erases will be linear time in the worst case. Still, it might be much faster than you probably think: Contiguous containers are very cache friendly compared to node based containers, such as std::set. Please read what they write at boost::container::flat_set. Whether this compromise is acceptable for you, I cannot tell / measure.

Others also mentioned std::share_ptr. I personally try to avoid them, mainly because "a shared pointer is as good as a global variable" (Sean Parent). Another reason why I don't use them is because they are heavy weight, partly because of all the multi-threading stuff that I usually don't need. However, boost::shared_ptr, when BOOST_SP_DISABLE_THREADS is defined, removes all that overhead associated with multi-threading. I believe using boost::shared_ptr would be the easiest solution in your case.

---

UPDATE: As Yakk kindly pointed out, my approach has linear time complexity... :(

---

---

(The first version.)

You can do it by passing a custom comparator to std::lower_bound(). Here is a rudimentary implementation how:

#include <algorithm>
#include <cassert>
#include <iostream>
#include <memory>
#include <set>
#include <string>

using namespace std;

template <typename T>
class Set {

private:

    struct custom_comparator {
        bool operator()(const unique_ptr<T>& a, const T* const & b){
            return a.get() < b;
        }
    } cmp;

    set<unique_ptr<T>> objects; // decltype at begin() and end()
                                // needs objects to be declared here
public:

    auto begin() const -> decltype(objects.begin()) { return objects.begin(); }

    auto   end() const -> decltype(objects.end()  ) { return objects.end();   }

    void addObject(unique_ptr<T>&& newObject) {

        objects.insert(move(newObject));
    }

    void removeObject(const T* target) {

        auto pos = lower_bound(objects.begin(), objects.end(), target, cmp);

        assert (pos!=objects.end()); // What to do if not found?

        objects.erase(pos);
    }
};

void test() {

    typedef string T;

    Set<T> mySet;

    unique_ptr<T> a{new T("a")};
    unique_ptr<T> b{new T("b")};
    unique_ptr<T> c{new T("c")};

    T* b_ptr = b.get();

    mySet.addObject(move(a));
    mySet.addObject(move(b));
    mySet.addObject(move(c));

    cout << "The set now contains: " << endl;

    for (const auto& s_ptr : mySet) {

        cout << *s_ptr << endl;
    }

    mySet.removeObject(b_ptr);

    cout << "After erasing b by the pointer to it:" << endl;

    for (const auto& s_ptr : mySet) {

        cout << *s_ptr << endl;
    }
}

int main() {

    test();
}

Answer 6

You can try to use boost::multi_index_container with additional indexing by Object*. Something like this:

typedef std::unique_ptr<Object> Ptr;
typedef multi_index_container<
  Ptr,
  indexed_by<
    hashed_unique<Ptr>,
    ordered_unique<const_mem_fun<Ptr,Object*,&Ptr::get> >
  >
> Objects;

Fore more information see Boost Multi-index Containers documentation

Or may be you can use std::shared_ptr everywhere, or use raw pointers in set instead?

Why you need to lookup by raw pinter? If you store it anywhere and check that object with this pointer is valid then better to use std::shared_ptr for storing in container and std::weak_ptr for other objects. In this case before usage you don't need lookup by raw pointer at all.

Answer 7

You're using unique pinters here. This means, your set has unique ownership of objects. Now, this should mean that if object does exist, it's either in the set or you have unique pointer with it. You don't even need to look up the set in this case.

But to me it looks like it's not hte case. I suppose you're better off with shared pointer in this case. Just store shared pointers and pass them around since someone beside this set clearly stores them.