How to Transfer unique_ptrs From a Set to Another Set

Transferring a std::unique_ptr to another std::unique_ptr is an easy thing to do:

std::unique_ptr<int> p1 = std::make_unique<int>(42);
std::unique_ptr<int> p2;

p2 = std::move(p1); // the contents of p1 have been transferred to p2

Easy peasy, lemon squeezy.

Now what if those unique_ptrs are living inside of two sets? It should be just as easy to transfer those in the first set over to the second set, right?

It turns out that it’s not easy, neither peasy, and even less lemon squeezy. Unless you have C++17, in which case it’s a breeze. But before C++17, it’s not. Here are various alternatives you can use to approach this.

Let’s see the motivating problem first.

The case: transfering sets of unique_ptrs

We start by seeing what a std::set of std::unique_ptr would represent, and then we see what problem happens when trying to transfer the contents of one set to another.

Sets of unique_ptrs: unique and polymorphic

To begin with, you may have wondered why do a unique_ptr on an int as in the above example. Except for showing a simple example, well, it has no use at all.

A more realistic case would be one of runtime polymorphism via inheritance, with a Base class that can have Derived classes:

And we would use the base class polymorphically by holding it with some sort of handle (pointer or reference). To encapsulate the memory management, we would use a std::unique_ptr<Base>.

Now if we want a collection of several objects implementing Base, but that could be of any derived classes, we can use a collection of unique_ptr<Base>s.

Finally, we may want to prevent our collection to have duplicates. This is what std::set does. Note that to implement this constraint, std::set needs a way to compare its objects together.

Indeed, by declaring a set this way:

std::set<std::unique_ptr<Base>>

the comparison between elements of the set will call the operator< of std::unique_ptr, which compares the memory addresses of the pointers inside them.

In most cases, this is not what you want. When we think “no duplicates”, it generally means “no logical duplicates” as in: no two elements have the same value. And not “no two elements are located at the same address in memory”.

To implement no logical duplicates, we need to call the operator< on Base (provided that it exists, maybe using an id provided by Base for instance) to compare elements and determines whether they are duplicates. And to make the set use this operator, we need to customize the comparator of the set:

struct ComparePointee
{
    template<typename T>
    bool operator()(std::unique_ptr<T> const& up1, std::unique_ptr<T> const& up2)
    {
        return *up1 < *up2;
    }
};

std::set<std::unique_ptr<int>, ComparePointee> mySet;

To avoid writing this type every time we instantiate such a set in code, we can hide its technical aspects behind an alias:

template<typename T>
using UniquePointerSet = std::set<std::unique_ptr<T>, ComparePointee>;

Transferring unique_ptrs between two sets

Ok. We’re all set (ha-ha) and ready to transfer the elements of a set to another one. Here are our two sets:

UniquePointerSet<Base> source;
source.insert(std::make_unique<Derived>());

UniquePointerSet<Base> destination;

To transfer elements efficiently, we use the insert method:

destination.insert(begin(source), end(source));

But this leads to a compilation error!

error: use of deleted function 'std::unique_ptr<_Tp, _Dp>::unique_ptr(const std::unique_ptr<_Tp, _Dp>&) [with _Tp = Base; _Dp = std::default_delete<Base>]'

Indeed, the insert methods attemps to make a copy of the unique_ptr elements.

What to do then?

C++17’s new method on set: merge

sets and maps in C++ are internally implemented as trees. This lets them ensure the algorithmic complexities guaranteed by the methods of their interface. Before C++17, it didn’t show in the interface.

C++17 adds the merge method to sets:

destination.merge(source);

This makes destination take over the nodes of the tree inside of source. It’s like performing a splicing on lists. So after executing this line, destination has the elements that source had, and source is empty.

And since it’s only the nodes that get modified, and not what’s inside them, the unique_ptrs don’t feel a thing. They are not even moved.

destination now has the unique_ptrs, end of story.

Now if you don’t have C++17 in production, which is the case of a lot of people at the time I’m writing these lines, what can you do?

We can’t move from a set

The standard algorithm to move elements from a collection to another collection is std::move. Here is how it works with std::vector:

std::vector<std::unique_ptr<Base>> source;
source.push_back(std::make_unique<Derived>());

std::vector<std::unique_ptr<Base>> destination;

std::move(begin(source), end(source), std::back_inserter(destination));

after the execution of this line, destination has the elements that source had and source is not empty, but has empty unique_ptrs.

Let’s try to do the same thing with our sets now:

UniquePointerSet<Base> source;
source.insert(std::make_unique<Derived>());

UniquePointerSet<Base> destination;

std::move(begin(source), end(source), std::inserter(destination, end(destination)));

We get the same compilation error as in the beginning, some unique_ptrs are getting copied:

error: use of deleted function 'std::unique_ptr<_Tp, _Dp>::unique_ptr(const std::unique_ptr<_Tp, _Dp>&)

This may look surprising. The purpose of the std::move algorithm is to avoid making copies on the unique_ptr elements and move them instead, so why are they being copied??

The answer lies in how the set provides access to its elements. When dereferenced, a set’s iterator does not return a unique_ptr&, but rather a const unique_ptr&. It is to make sure that the values inside of the set don’t get modified without the set being aware of it. Indeed, it could break its invariant of being sorted.

So here is what happens:

• std::move dereferences the iterator on set and gets a const unique_ptr&,
• it calls std::move on that references, thus getting a const unique_ptr&&,
• it calls the insert method on the insert output iterator and passes it this const unique_ptr&&,
• the insert method has two overloads: one that takes a const unique_ptr&, and one that takes a unique_ptr&&. Because of the const in the type we’re passing, the compiler cannot resolve this call to the second method, and calls the first one instead.

Then the insert output iterator calls calls the insert overload on the set that takes a const unique_ptr& and in turn calls the copy constructor of unique_ptr with that l-value reference, and that leads to the compilation error.

Making a sacrifice

So before C++17, moving elements from a set doesn’t seem to be possible. Something has to give: either moving, or the sets. This leads us to two possible aspects to give up on.

Keeping the set but paying up for the copies

To give up on the move and accepting to copy the elements from a set to another, we need to make a copy of the contents pointed by the unique_ptrs.

For this, let’s assume that Base has is a polymorphic clone implemented by its method cloneBase, overriden in Derived:

class Base
{
public:
    virtual std::unique_ptr<Base> cloneBase() const = 0;

    // rest of Base...
};

class Derived : public Base
{
public:
    std::unique_ptr<Base> cloneBase() const override
    {
        return std::make_unique<Derived>(*this);
    }

    // rest of Derived...
};

At call site, we can make copies of the unique_ptrs from a set over to the other one, for instance this way:

auto clone = [](std::unique_ptr<Base> const& pointer){ return pointer->cloneBase(); };
std::transform(begin(source), end(source), std::inserter(destination, end(destination)), clone);

Or, with a for loop:

for (auto const& pointer : source)
{
    destination.insert(pointer->cloneBase());
}

Keeping the move and throwing away the set

The set that doesn’t let the move happen is the source set. If you only need the destination to have unique elements, you can replace the source set by a std::vector.

Indeed, std::vector does not add a const to the value returned by its iterator. We can therefore move its elements from it with the std::move algorithm:

std::vector<std::unique_ptr<Base>> source;
source.push_back(std::make_unique<Derived>(42));

std::set<std::unique_ptr<Base>> destination;

std::move(begin(source), end(source), std::inserter(destination, end(destination)));

Then the destination set contains a unique_ptr that has the contents that used to be in the one of the source, and the source vector now contains an empty unique_ptr.

Live at head

You can see that there are ways around the problem of transferring unique_ptrs from a set to another one. But the real solution is the merge method of std::set in C++17.

The standard library is getter better and better as the language evolves. Let’s do what we can to move (ha-ha) to the latest version of C++, and never look back.

Related articles:

• Move iterators: where the STL meets move semantics
• Smart developers use smart pointers
• The STL learning resource

Don't want to miss out ? Follow:   
Share this post!