So can unique_ptr be used safely in stl collections?

Question

I am confused with unique_ptr and rvalue move philosophy.

Let's say we have two collections:

std::vector<std::auto_ptr<int>> autoCollection;
std::vector<std::unique_ptr<int>> uniqueCollection;

Now I would expect the following to fail, as there is no telling what the algorithm is doing internally and maybe making internal pivot copies and the like, thus ripping away ownership from the auto_ptr:

std::sort(autoCollection.begin(), autoCollection.end());

I get this. And the compiler rightly disallows this happening.

But then I do this:

std::sort(uniqueCollection.begin(), uniqueCollection.end());

And this compiles. And I do not understand why. I did not think unique_ptrs could be copied. Does this mean a pivot value cannot be taken, so the sort is less efficient? Or is this pivot actually a move, which in fact is as dangerous as the collection of auto_ptrs, and should be disallowed by the compiler?

I think I am missing some crucial piece of information, so I eagerly await someone to supply me with the aha! moment.

Solution 1

I think it's more a question of philosophy than technic :)

The underlying question is what is the difference between Move and Copy. I won't jump into technical / standardista language, let's do it simply:

• Copy: create another identical object (or at least, one which SHOULD compare equal)
• Move: take an object and put it in another location

As you said, it is possible to implement Move in term of Copy: create a copy into the new location and discard the original. However there are two issues there. One is of performance, the second is about objects used for RAII: which of the two should have ownership ?

A proper Move constructor solves the 2 issues:

• It is clear which object has ownership: the new one, since the original will be discarded
• It is thus unnecessary to copy the resources pointed to, which allows for greater efficiency

The auto_ptr and unique_ptr are a very good illustration of this.

With an auto_ptr you have a screwed Copy semantic: the original and the copy don't compare equal. You could use it for its Move semantic but there is a risk that you'll lose the object pointed to somewhere.

On the other hand, the unique_ptr is exactly that: it guarantees a unique owner of the resource, thus avoiding copying and the inevitable deletion issue that would follow. And the no-copy is guaranteed at compile-time too. Therefore, it's suitable in containers as long as you don't try to have copy initialization.

typedef std::unique_ptr<int> unique_t;
typedef std::vector< unique_t > vector_t;

vector_t vec1;                           // fine
vector_t vec2(5, unique_t(new Foo));     // Error (Copy)
vector_t vec3(vec1.begin(), vec1.end()); // Error (Copy)
vector_t vec3(make_move_iterator(vec1.begin()), make_move_iterator(vec1.end()));
    // Courtesy of sehe

std::sort(vec1.begin(), vec1.end()); // fine, because using Move Assignment Operator

std::copy(vec1.begin(), vec1.end(), std::back_inserter(vec2)); // Error (copy)

So you can use unique_ptr in a container (unlike auto_ptr), but a number of operations will be impossible because they involve copying which the type does not support.

Unfortunately Visual Studio may be quite lax in the enforcement of the standard and also has a number of extensions that you would need to disable to ensure portability of the code... don't use it to check the standard :)

Solution 2

The unique_ptrs are being moved using their move constructor. unique_ptr is Movable, but not CopyConstructable.

There's a great article on rvalue references here. If you haven't read about them yet, or are confused, take a look!

Solution 3

std::sort could work only with move operations and no copying, as long as there is only one live copy of each object at any given time. This is a weaker requirement than working in-place, since in principle you could allocate another array temporarily and move all objects to while reordering them.

for example with std::vector<std::unique_ptr<T>> exceeding its capacity, it allocates storage for a larger vector and then moves all objects from old storage to the new one. This is not an in-place operation but it's perfectly valid.

As it turns out, sorting algorithms like quick-sort and heap-sort can in fact work in-place without difficulty. quick-sort's partition routine uses std::swap internally, which counts as a move operation for both objects involved. When selecting a pivot, one trick is to swap it with the first element in the range, this way it will never be moved until partitioning is finished.

Comments

[Billy ONeal]

Actually the compiler should complain about std::vector<std::auto_ptr<int>> autoCollection; because COAPS (Containers of Auto Pointers) are not allowed in any description.

[DanDan]

Using VS2010. I do not even get a warning at/W4.

[DanDan]

or get a warning that auto_ptr is depreciated.

[bitmask]

It Is Not Called The STL, Mmkay?

[DanDan]

Hey thanks for the great article! It got a little crazy around page 7 though but I learned a lot. But my original problem remains. Why are moves safe yet copies are not? Isn't a unique_ptr's move the same as an auto_ptr's copy? If the object's move constructor is using std::move, ie transfer of ownership, is this not the default behaviour of an auto_ptr copy?

[rlbond]

Yes, but auto_ptr was from before c++0x and is expressly not allowed in containers. On the other hand, since unique_ptr can be safely moved, you (and the compiler) can rest assured that ownership is not violated. Also, keep in mind that the STL's sort algorithm is unspecified, and in c++0x is required to only move things around. However it's possible to do quicksort in-place, so no copies are required.

[DanDan]

Thank you, great answer and examples :)

[sehe]

In your comment "fine, because using Move constructor" did you mean "move assignment or swap"? Also, for completeness, here's how the 'impossibles' could be done using std::move and std::make_move_iterator: coliru.stacked-crooked.com/a/6b032d70a9ed6f5c

[jterm]

Moving doesn't put anything in a new location. It is a transfer of ownership of an address space from one object to another.