Is a moved-from vector always empty?

Question

I know that generally the standard places few requirements on the values which have been moved from:

N3485 17.6.5.15 [lib.types.movedfrom]/1:

Objects of types defined in the C++ standard library may be moved from (12.8). Move operations may be explicitly specified or implicitly generated. Unless otherwise specified, such moved-from objects shall be placed in a valid but unspecified state.

I can't find anything about vector that explicitly excludes it from this paragraph. However, I can't come up with a sane implementation that would result in the vector being not empty.

Is there some standardese that entails this that I'm missing or is this similar to treating basic_string as a contiguous buffer in C++03?

Answer 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.

Answer 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.

Answer 3

In a lot of situations, move-construction and move-assignment can be implemented by delegating to swap - especially if no allocators are involved. There are several reasons for doing that:

• swap has to be implemented anyway
• developer efficiency because less code has to be written
• runtime efficiency because fewer operations are executed in total

Here is an example for move-assignment. In this case, the move-from vector will not be empty, if the moved-to vector was not empty.

auto operator=(vector&& rhs) -> vector&
{
    if (/* allocator is neither move- nor swap-aware */) {
        swap(rhs);
    } else {
        ...
    }
    return *this;
}

Answer 4

I left comments to this effect on other answers, but had to rush off before fully explaining. The result of a moved-from vector must always be empty, or in the case of move assignment, must be either empty or the previous object's state (i.e. a swap), because otherwise the iterator invalidation rules cannot be met, namely that a move does not invalidate them. Consider:

std::vector<int> move;
std::vector<int>::iterator it;
{
    std::vector<int> x(some_size);
    it = x.begin();
    move = std::move(x);
}
std::cout << *it;

Here you can see that iterator invalidation does expose the implementation of the move. The requirement for this code to be legal, specifically that the iterator remains valid, prevents the implementation from performing a copy, or small-object-storage or any similar thing. If a copy was made, then it would be invalidated when the optional is emptied, and the same is true if the vector uses some kind of SSO-based storage. Essentially, the only reasonable possible implementation is to swap pointers, or simply move them.

Kindly view the Standard quotes on requirements for all containers:

X u(rv)    
X u = rv    

post: u shall be equal to the value that rv had before this construction

a = rv

a shall be equal to the value that rv had before this assignment

Iterator validity is part of the value of a container. Although the Standard does not unambiguously state this directly, we can see in, for example,

begin() returns an iterator referring to the first element in the container. end() returns an iterator which is the past-the-end value for the container. If the container is empty, then begin() == end();

Any implementation which actually did move from the elements of the source instead of swapping the memory would be defective, so I suggest that any Standard wordings saying otherwise is a defect- not least of which because the Standard is not in fact very clear on this point. These quotes are from N3691.