Is a moved-from vector always empty?

Solution 1:

I'm coming to this party late, and offering an additional answer because I do not believe any other answer at this time is completely correct.

Question:

Is a moved-from vector always empty?

Answer:

Usually, but no, not always.

The gory details:

vector has no standard-defined moved-from state like some types do (e.g. unique_ptr is specified to be equal to nullptr after being moved from). However the requirements for vector are such that there are not too many options.

The answer depends on whether we're talking about vector's move constructor or move assignment operator. In the latter case, the answer also depends on the vector's allocator.

vector<T, A>::vector(vector&& v)

This operation must have constant complexity. That means that there are no options but to steal resources from v to construct *this, leaving v in an empty state. This is true no matter what the allocator A is, nor what the type T is.

So for the move constructor, yes, the moved-from vector will always be empty. This is not directly specified, but falls out of the complexity requirement, and the fact that there is no other way to implement it.

vector<T, A>&
vector<T, A>::operator=(vector&& v)

This is considerably more complicated. There are 3 major cases:

One:

allocator_traits<A>::propagate_on_container_move_assignment::value == true

(propagate_on_container_move_assignment evaluates to true_type)

In this case the move assignment operator will destruct all elements in *this, deallocate capacity using the allocator from *this, move assign the allocators, and then transfer ownership of the memory buffer from v to *this. Except for the destruction of elements in *this, this is an O(1) complexity operation. And typically (e.g. in most but not all std::algorithms), the lhs of a move assignment has empty() == true prior to the move assignment.

Note: In C++11 the propagate_on_container_move_assignment for std::allocator is false_type, but this has been changed to true_type for C++1y (y == 4 we hope).

In case One, the moved-from vector will always be empty.

Two:

allocator_traits<A>::propagate_on_container_move_assignment::value == false
    && get_allocator() == v.get_allocator()

(propagate_on_container_move_assignment evaluates to false_type, and the two allocators compare equal)

In this case, the move assignment operator behaves just like case One, with the following exceptions:

1. The allocators are not move assigned.
2. The decision between this case and case Three happens at run time, and case Three requires more of T, and thus so does case Two, even though case Two doesn't actually execute those extra requirements on T.

In case Two, the moved-from vector will always be empty.

Three:

allocator_traits<A>::propagate_on_container_move_assignment::value == false
    && get_allocator() != v.get_allocator()

(propagate_on_container_move_assignment evaluates to false_type, and the two allocators do not compare equal)

In this case the implementation can not move assign the allocators, nor can it transfer any resources from v to *this (resources being the memory buffer). In this case, the only way to implement the move assignment operator is to effectively:

typedef move_iterator<iterator> Ip;
assign(Ip(v.begin()), Ip(v.end()));

That is, move each individual T from v to *this. The assign can reuse both capacity and size in *this if available. For example if *this has the same size as v the implementation can move assign each T from v to *this. This requires T to be MoveAssignable. Note that MoveAssignable does not require T to have a move assignment operator. A copy assignment operator will also suffice. MoveAssignable just means T has to be assignable from an rvalue T.

If the size of *this is not sufficient, then new T will have to be constructed in *this. This requires T to be MoveInsertable. For any sane allocator I can think of, MoveInsertable boils down to the same thing as MoveConstructible, which means constructible from an rvalue T (does not imply the existence of a move constructor for T).

In case Three, the moved-from vector will in general not be empty. It could be full of moved-from elements. If the elements don't have a move constructor, this could be equivalent to a copy assignment. However, there is nothing that mandates this. The implementor is free to do some extra work and execute v.clear() if he so desires, leaving v empty. I am not aware of any implementation doing so, nor am I aware of any motivation for an implementation to do so. But I don't see anything forbidding it.

David Rodríguez reports that GCC 4.8.1 calls v.clear() in this case, leaving v empty. libc++ does not, leaving v not empty. Both implementations are conforming.

Solution 2:

While it might not be a sane implementation in the general case, a valid implementation of the move constructor/assignment is just copying the data from the source, leaving the source untouched. Additionally, for the case of assignment, move can be implemented as swap, and the moved-from container might contain the old value of the moved-to container.

Implementing move as copy can actually happen if you use polymorphic allocators, as we do, and the allocator is not deemed to be part of the value of the object (and thus, assignment never changes the actual allocator being used). In this context, a move operation can detect whether both the source and the destination use the same allocator. If they use the same allocator the move operation can just move the data from the source. If they use different allocators then the destination must copy the source container.