Does moving a vector invalidate iterators?

Question

If I have an iterator into vector a, then I move-construct or move-assign vector b from a, does that iterator still point to the same element (now in vector b)? Here's what I mean in code:

#include <vector>
#include <iostream>

int main(int argc, char *argv[])
{
    std::vector<int>::iterator a_iter;
    std::vector<int> b;
    {
        std::vector<int> a{1, 2, 3, 4, 5};
        a_iter = a.begin() + 2;
        b = std::move(a);
    }
    std::cout << *a_iter << std::endl; // Is a_iter valid here?
    return 0;
}

Is a_iter still valid since a has been moved into b, or is the iterator invalidated by the move? For reference, std::vector::swap does not invalidate iterators.

Answer 1

While it might be reasonable to assume that iterators are still valid after a move, I don't think the Standard actually guarantees this. Therefore, the iterators are in an undefined state after the move.

---

There is no reference I can find in the Standard which specifically states that iterators that existed before a move are still valid after the move.

On the surface, it would seem to be perfectly reasonable to assume that an iterator is typically implemented as pointers in to the controlled sequence. If that's the case, then the iterators would still be valid after the move.

But the implementation of an iterator is implementation-defined. Meaning, so long as the iterator on a particular platform meets the requirements set forth by the Standard, it can be implemented in any way whatsoever. It could, in theory, be implemented as a combination of a pointer back to the vector class along with an index. If that's the case, then the iterators would become invalid after the move.

Whether or not an iterator is actually implemented this way is irrelevant. It could be implemented this way, so without a specific guarantee from the Standard that post-move iterators are still valid, you cannot assume that they are. Bear in mind also that there is such a guarantee for iterators after a swap. This was specifically clarified from the previous Standard. Perhaps it was simply an oversight of the Std comittee to not make a similar clarification for iterators after a move, but in any case there is no such guarantee.

Therefore, the long and the short of it is you can't assume your iterators are still good after a move.

EDIT:

23.2.1/11 in Draft n3242 states that:

Unless otherwise specified (either explicitly or by defining a function in terms of other functions), invoking a container member function or passing a container as an argument to a library function shall not invalidate iterators to, or change the values of, objects within that container.

This might lead one to conclude that the iterators are valid after a move, but I disagree. In your example code, a_iter was an iterator in to the vector a. After the move, that container, a has certainly been changed. My conclusion is the above clause does not apply in this case.

Answer 2

I think the edit that changed move construction to move assignment changes the answer.

At least if I'm reading table 96 correctly, the complexity for move construction is given as "note B", which is constant complexity for anything except std::array. The complexity for move assignment, however, is given as linear.

As such, the move construction has essentially no choice but to copy the pointer from the source, in which case it's hard to see how the iterators could become invalid.

For move assignment, however, the linear complexity means it could choose to move individual elements from the source to the destination, in which case the iterators will almost certainly become invalid.

The possibility of move assignment of elements is reinforced by the description: "All existing elements of a are either move assigned to or destroyed". The "destroyed" part would correspond to destroying the existing contents, and "stealing" the pointer from the source -- but the "move assigned to" would indicate moving individual elements from source to destination instead.

Answer 3

tl;dr : Yes, moving a std::vector<T, A> possibly invalidates the iterators

_{The common case (with std::allocator in place) is that invalidation does not happen but there is no guarantee and switching compilers or even the next compiler update might make your code behave incorrect if you rely on the fact the your implementation currently does not invalidate the iterators.}

---

On move assignment:

The question whether std::vector iterators can actually remain valid after move-assignment is connected with the allocator awareness of the vector template and depends on the allocator type (and possibly the respective instances thereof).

In every implementation I have seen, move-assignment of a std::vector<T, std::allocator<T>>¹ will not actually invalidate iterators or pointers. There is a problem however, when it comes down to making use of this, as the standard just cannot guarantee that iterators remain valid for any move-assignment of a std::vector instance in general, because the container is allocator aware.

Custom allocators may have state and if they do not propagate on move assignment and do not compare equal, the vector must allocate storage for the moved elements using its own allocator.

Let:

std::vector<T, A> a{/*...*/};
std::vector<T, A> b;
b = std::move(a);

Now if

1. std::allocator_traits<A>::propagate_on_container_move_assignment::value == false &&
2. std::allocator_traits<A>::is_always_equal::value == false && (possibly as of c++17)
3. a.get_allocator() != b.get_allocator()

then b will allocate new storage and move elements of a one by one into that storage, thus invalidating all iterators, pointers and references.

The reason is that fulfillment of above condition 1. forbidds move assignment of the allocator on container move. Therefore, we have to deal with two different instances of the allocator. If those two allocator objects now neither always compare equal (2.) nor actually compare equal, then both allocators have a different state. An allocator x may not be able to deallocate memory of another allocator y having a different state and therefore a container with allocator x cannot just steal memory from a container which allocated its memory via y.

If the allocator propagates on move assignment or if both allocators compare equal, then an implementation will very likely choose to just make b own as data because it can be sure to be able to deallocate the storage properly.

¹: std::allocator_traits<std::allocator<T>>::propagate_on_container_move_assignment and std::allocator_traits<std::allocator<T>>::is_always_equal both are typdefs for std::true_type (for any non-specialized std::allocator).

---

On move construction:

std::vector<T, A> a{/*...*/};
std::vector<T, A> b(std::move(a));

The move constructor of an allocator aware container will move-construct its allocator instance from the allocator instance of the container which the current expression is moving from. Thus, the proper deallocation capability is ensured and the memory can (and in fact will) be stolen because move construction is (except for std::array) bound to have constant complexity.

Note: There is still no guarantee for iterators to remain valid even for move construction.

---

On swap:

Demanding the iterators of two vectors to remain valid after a swap (now just pointing into the respective swapped container) is easy because swapping only has defined behaviour if

1. std::allocator_traits<A>::propagate_on_container_swap::value == true ||
2. a.get_allocator() == b.get_allocator()

Thus, if the allocators do not propagate on swap and if they do not compare equal, swapping the containers is undefined behaviour in the first place.

Answer 4

Since there's nothing to keep an iterator from keeping a reference or pointer to the original container, I'd say you can't rely on the iterators remaining valid unless you find an explicit guarantee in the standard.