Is a Moved-From Vector Always Empty

Is a moved-from vector always empty?

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:

The allocators are not move assigned.
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.

c++ reassign after moved

This is guaranteed. After the move, the vector is guaranteed to be empty, i.e. has no elements. It's fine to be assigned by other contents.

After the move, other is guaranteed to be empty().

Reusing a moved container?

From section 17.3.26 of the spec "valid but unspecified state":

an object state that is not specified except that the object’s invariants are met and operations on the object behave as specified for its type [ Example: If an object x of type std::vector<int> is in a valid but unspecified state, x.empty() can be
called unconditionally, and x.front() can be called only if x.empty() returns false. —end example ]

Therefore, the object is live. You can perform any operation that does not require a precondition (unless you verify the precondition first).

clear, for example, has no preconditions. And it will return the object to a known state. So just clear it and use it as normal.

Moving a vector of unique_ptrs bug

A move results in a "valid but unspecified state":

Moved-from state of library types                     [lib.types.movedfrom]

Objects of types defined in the C++ standard library may be moved from.
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.

A moved-from vector can certainly be empty, that would be "valid". But nothing in the C++ standard requires that. In the case of a moved-from vector of std::unique_ptrs, it would also be "valid" if the moved-from vector remains non-empty, but now has some indeterminate number of default-constructed std::unique_ptrs (the moved-from vector's size can remain the same, or may be different). The original std::unique_ptrs are now in the moved-to vector, and the moved-from vector has some default-constructed std::unique_ptrs. No rules are broken. The moved-from vector is in a "valid" state.

For various practical reasons, it's extremely unlikely for a moved-from vector in any typical C++ library implementation to behave this way, in this case. That's very unlikely. But it would be valid, if it were the case, provided that the overall state is still valid. It would not be valid for both the moved-from and the moved-to vector of std::unique_ptrs to end up with std::unique_ptrs to the same objects.

If you're observing spurious, or extra, object construction or destruction, it must be due to undefined behavior of some other source. There's nothing wrong with the shown code. If there's undefined behavior, it must be in code that's not shown.

Reusing a moved container?

From section 17.3.26 of the spec "valid but unspecified state":

an object state that is not specified except that the object’s invariants are met and operations on the object behave as specified for its type [ Example: If an object x of type std::vector<int> is in a valid but unspecified state, x.empty() can be
called unconditionally, and x.front() can be called only if x.empty() returns false. —end example ]

Therefore, the object is live. You can perform any operation that does not require a precondition (unless you verify the precondition first).

clear, for example, has no preconditions. And it will return the object to a known state. So just clear it and use it as normal.

Capacity of the vector from which data was moved

If your question had been about move construction of a vector, the answer would be easy, the source vector is left empty after the move. This is because of the requirement in

Table 99 — Allocator-aware container requirements

Expression:
  X(rv)
  X u(rv)
Requires: move construction of A shall not exit via an exception.

post: u shall have the same elements as rv had before this construction; the value of u.get_allocator() shall be the same as the value of rv.get_allocator() before this construction.

Complexity: constant

(the A in the requirements clause is the allocator type)

The constant complexity leaves no option but to steal resources from the source vector, which means for it to be in a valid, but unspecified state you'd need to leave it empty, and capacity() will equal zero.

The answer is considerably more complicated in case of a move assignment. The same Table 99 lists the requirement for move assignment as

Expression:
  a = rv
Return type:
  X&
Requires: If allocator_traits<allocator_type>::propagate_on_container_move_assignment::value is
false, T is MoveInsertable into X and MoveAssignable. All existing elements of a are either move assigned to or destroyed.

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

Complexity: linear

There are different cases to evaluate here.

First, say allocator_traits<allocator_type>::propagate_on_container_move_assignment::value == true, then the allocator can also be move assigned. This is mentioned in §23.2.1/8

... The allocator may be replaced only via assignment or swap(). Allocator replacement is performed by copy assignment, move assignment, or swapping of the allocator
only if allocator_traits<allocator_type>::propagate_on_container_copy_assignment::value,
allocator_traits<allocator_type>::propagate_on_container_move_assignment::value, or allocator_traits<allocator_type>::propagate_on_container_swap::value is true within the implementation of the corresponding container operation.

So the destination vector will destroy its elements, the allocator from the source is moved and the destination vector takes ownership of the memory buffer from the source. This will leave the source vector empty, and capacity() will equal zero.

Now let's consider the case where allocator_traits<allocator_type>::propagate_on_container_move_assignment::value == false. This means the allocator from the source cannot be move assigned to the destination vector. So you need to check the two allocators for equality before determining what to do.

If dest.get_allocator() == src.get_allocator(), then the destination vector is free to take ownership of the memory buffer from the source because it can use its own allocator to deallocate the storage.

Table 28 — Allocator requirements

Expression:
  a1 == a2
Return type:
  bool
returns true only if storage allocated from each can be deallocated via the other. ...

The sequence of operations performed is the same as the first case, except the source allocator is not move assigned. This will leave the source vector empty, and capacity() will equal zero.

In the last case, if allocator_traits<allocator_type>::propagate_on_container_move_assignment::value == false and dest.get_allocator() != src.get_allocator(), then the source allocator cannot be moved, and the destination allocator is unable to deallocate the storage allocated by the source allocator, so it cannot steal the memory buffer from source.

Each element from the source vector must be either move inserted or move assigned to the destination vector. Which operation gets done depends on the existing size and capacity of the destination vector.

The source vector retains ownership of its memory buffer after the move assignment, and it is up to the implementation to decide whether to deallocate the buffer or not, and the vector will most likely have capacity() greater than 0.

To ensure you do not run into undefined behavior when trying to resuse a vector that has been move assigned from, you should first call the clear() member function. This can be safely done since vector::clear has no pre-conditions, and will return the vector to a valid and specified state.

Also, vector::capacity has no pre-conditions either, so you can always query the capacity() of a moved from vector.

Moving elements from std::vector to another one

The std::move lets you move the objects, as opposed to copying them, allowing for a potentially faster execution speed. The savings may be even greater when you move a range of values. However, when you do move a range from a container, the container still holds the places that were once occupied by these values.

You need to resize the container manually to remove these placeholders if you want to get rid of them (you don't have to, in case you would prefer reusing these container spots for other elements). One way to do it is to call vector::erase on the same range that you moved out of the container.

Is a Moved-From Vector Always Empty