7

Creating an object and giving ownership to a container using a unique_ptr is no problem. How would one remove an element by raw pointer?

std::set<std::unique_ptr<MyClass>> mySet;

MyClass *myClass = new MyClass();
mySet.insert(std::unique_ptr<MyClass>(myClass));

// remove myClass from mySet?
mazatwork
  • 1,275
  • 1
  • 13
  • 20

5 Answers5

3

You will need to find the iterator corresponding to the myClass element and then pass that iterator to mySet.erase(). The iterator may be found using the std::find_if algorithm with a custom Predicate functor that understands how to dereference unique_ptr and compare it to the raw pointer myClass.

You can not use the overloaded size_t set::erase ( const key_type& x ); since the raw pointer (even if wrapped in a temporary unique_ptr) will not be found in mySet.

vim keytar
  • 391
  • 1
  • 5
  • If the raw pointer is wrapped in a temporary `unique_ptr<>`, §20.7.1.4/2 guarantees that the `set::size_type set::erase(key_type const&);` overload **will** work. However, that is almost guaranteed to create object lifetime issues unless a custom deleter is used for the temporary, so the `std::find_if` approach is probably still better. – ildjarn Aug 01 '11 at 23:37
  • I am failing to find the relevant section in either the 1998 standard, the revised 2003 standard or the new C++0X draft. Could you please direct me to the name of the correct document to which you are referring? – vim keytar Aug 02 '11 at 02:46
  • I am referring to the C++0x FDIS (N3290), §20.7.1.4/2, page 549. – ildjarn Aug 02 '11 at 03:38
  • As a side note, one could achieve std::set's logarithmic search time by re-factoring the code to use a `std::map>` instead. There would be a little more memory overhead, but if we're talking about big sets that have elements deleted frequently, it's worth it to circumvent's `find_if`'s linear search time. Also, don't forget about `unordered_set` and `unordered_map`. They do most of the same things but have constant search time. – jbatez Aug 28 '12 at 12:44
  • find_if is a bad approach because it's O(n), defeating the purpose of using a set<> – nilton Oct 11 '16 at 01:40
3

Not as pretty as I would've liked. But the following does the job:

#include <memory>
#include <set>
#include <iostream>

struct do_nothing
{
    void operator()(const void*) const {}
};

struct MyClass
{
    MyClass() {std::cout << "MyClass()\n";}
    MyClass(const MyClass&) {std::cout << "MyClass(const MyClass&)\n";}
    ~MyClass() {std::cout << "~MyClass()\n";}
};

int main()
{
    std::set<std::unique_ptr<MyClass>> mySet;

    MyClass *myClass = new MyClass();
    mySet.insert(std::unique_ptr<MyClass>(myClass));

    // remove myClass from mySet?
    std::set<std::unique_ptr<MyClass>>::iterator i =
        lower_bound(mySet.begin(), mySet.end(),
                    std::unique_ptr<MyClass, do_nothing>(myClass));
    if (i != mySet.end() && *i == std::unique_ptr<MyClass, do_nothing>(myClass))
        mySet.erase(i);
}
Howard Hinnant
  • 206,506
  • 52
  • 449
  • 577
  • Hm, this is fairly ugly, but I suppose that matches the unusual requirement: If the pointer is unique, then how could you even have another copy of it to search by value? I'm suspicious mainly of the OP's motives. – Kerrek SB Aug 02 '11 at 08:04
  • I think i have a good solution based on your proposal. See my posted solution. – mazatwork Aug 03 '11 at 00:07
1

It seems i am able to retrieve an iterator using a custom Predicate with lower_bound. Since std::set is an ordered container, lower_bound should perform logarithmically.

std::set<std::unique_ptr<MyClass>>::iterator i =
    std::lower_bound(mySet.begin(), mySet.end(), myClass, MyPredicate<MyClass>());

template<class Type>
struct MyPredicate
{
    bool operator()(const std::unique_ptr<Type>& left, const Type* right) const
    {
        return left.get() < right;
    }
}
mazatwork
  • 1,275
  • 1
  • 13
  • 20
  • lower_bound is not logarithmic in this case because the iterator returned by set<>.begin()/set<>.end() is not a RandomAccessIterator. http://en.cppreference.com/w/cpp/algorithm/lower_bound – nilton Oct 11 '16 at 01:44
0

You might like the answer over here: Efficiently erase a unique_ptr from an unordered_set

That's for C++14, but I think applies to C++11 as well.

It is not pretty, but does the efficient thing — no scanning the container, but using proper hash-based lookup.

jwd
  • 10,837
  • 3
  • 43
  • 67
0

Still not the best solution but for the moment i go with:

PointerMap<MyFoo>::Type myFoos;

MyFoo * myFoo = new MyFoo();
myFoos.insert(PointerMap<MyFoo>::Item(myFoo));

The header is:

#include <map>
#include <memory>
#include <utility>

template<typename T>
struct PointerMap
{
    typedef std::map<T *, std::unique_ptr<T>> Type;

    struct Item : std::pair<T *, std::unique_ptr<T>>
    {
        Item(T * pointer)
            : std::pair<T *, std::unique_ptr<T>>(pointer, std::unique_ptr<T>(pointer))
        {
        }
    };
};
mazatwork
  • 1,275
  • 1
  • 13
  • 20