Does Moving a Vector Invalidate Iterators

Does moving a vector invalidate iterators?

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.

Does std::vector::swap invalidate iterators?

The behavior of swap has been clarified considerably in C++11, in large part to permit the Standard Library algorithms to use argument dependent lookup (ADL) to find swap functions for user-defined types. C++11 adds a swappable concept (C++11 §17.6.3.2[swappable.requirements]) to make this legal (and required).

The text in the C++11 language standard that addresses your question is the following text from the container requirements (§23.2.1[container.requirements.general]/8), which defines the behavior of the swap member function of a container:

Every iterator referring to an element in one container before the swap shall refer to the same element in the other container after the swap.

It is unspecified whether an iterator with value a.end() before the swap will have value b.end() after the swap.

In your example, a is guaranteed to be valid after the swap, but b is not because it is an end iterator. The reason end iterators are not guaranteed to be valid is explained in a note at §23.2.1/10:

[Note: the end() iterator does not refer to any element, so it may be
invalidated. --end note]

This is the same behavior that is defined in C++03, just substantially clarified. The original language from C++03 is at C++03 §23.1/10:

no swap() function invalidates any references, pointers, or iterators referring to the elements of the containers being swapped.

It's not immediately obvious in the original text, but the phrase "to the elements of the containers" is extremely important, because end() iterators do not point to elements.

Does resizing a vector invalidate iterators?

Edited with more careful wording

yes, resizing a vector might invalidate all iterators pointing into the vector.

The vector is implemented by internally allocating an array where the data is stored. When the vector grows, that array might run out of space, and when it does, the vector allocates a new, bigger, array, copies the data over to that, and then deletes the old array.

So your old iterators, which point into the old memory, are no longer valid.
If the vector is resized downwards (for example by pop_back()), however, the same array is used. The array is never downsized automatically.

One way to avoid this reallocation (and pointer invalidation) is to call vector::reserve() first, to set aside enough space that this copying isn't necessary. In your case, if you called a.reserve(3) before the first push_back() operation, then the internal array would be big enough that the push_back's can be performed without having to reallocate the array, and so your iterators will stay valid.

Does modifying a std::vector invalidate an iterator?

std::vector::push_back invalidates all iterators on that vector if the new vector size is greater than the previous capacity. (The reason is due to the reallocation of the vector).

The behaviour of using an invalidated iterator is undefined.

std::list::push_back does not invalidate any iterators.

Why std::vector iterator is invalidated after the erase() call?

One of the principles on which the conceptual idea of iterator is built, is as follows: as long as iterator remains non-aliased, dereferenceable and non-modified, it should refer to the same entity. In other words, dereferencing the same iterator multiple times should yield the same value. Algorithms that use iterators may rely on that.

What you proposing would result in an iterator that would "magically" change the value it refers to even though the iterator itself remains unchanged. This is not acceptable within the conceptual idea of iterator.

---

On the second thought, what I said above is obviously flawed in a sense that we can always apply some modifying operation to the vector that shifts elements around (e.g. std::random_shuffle). Such operation would not invalidate any iterators, but would easily change the values the iterators refer to. How is that different from element shifting triggered by erase? It isn't.

std::list - are the iterators invalidated on move?

For containers in general, only swap guarantees that iterators remain valid (and point into the swapped containers).

For std::list, the special member function splice() guarantees that iterators retain their expected meaning.

In general, constructing a container from an rvalue doesn't make guarantees about iterators; the only general requirement is that the new container has the "same value" as the container it was constructed from had originally.

(You can imagine debug iterator implementations that store a reference to the container, and that reference would become dangling after a move.)

Does a vector sort invalidate iterators?

According to the C++ Standard §23.1/11:

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.

§25.3 "Sorting and related operations" doesn't specify that iterators will be invalidated, so iterators in the question should stay valid.

Arithmetic on invalidated iterators

Is behavior of std::distance undefined when called on a pair of std::vector iterators that have been invalidated by moving the vector?

If the iterators are valid before the move, they will remain valid after the move - so you don't need to recalculate them using std::distance.

(emphasis mine below)

std::vector::vector

After container move construction, references, pointers, and iterators (other than the end iterator) to other remain valid, but refer to elements that are now in *this.

The current standard makes this guarantee via the blanket statement in [container.requirements.general/12], and a more direct guarantee is under consideration via LWG 2321.

[container.requirements.general/12] 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.

The same blanket statement goes for the move assignment operator and this means that, in accordance with the standard, the iterators will stay valid after the move.

The current wording in LWG 2321 gives a hint of what a new paragraph in the standard could look like if the library working group finalize this - which seems to be hard. LWG 2321 was opened back in 2013.

no move constructor (or move assignment operator when allocator_traits<allocator_type>::propagate_on_container_move_assignment::value is true) of a container (except for array) invalidates any references, pointers, or iterators referring to the elements of the source container. [Note: The end() iterator does not refer to any element, so it may be invalidated. — end note]

If that's too vague, you can use

[container.requirements.general/11.6]

no swap() function invalidates any references, pointers, or iterators referring to the elements of the containers being swapped. [ Note: The end() iterator does not refer to any element, so it may be invalidated. — end note ]

If the iterators are valid before you swap, they are valid after the swap.

Here's an example class using the guarantee given for swap:

#include <vector>

class Foo {
    std::vector<int> data{};
    std::vector<decltype(data)::iterator> dits{};

public:
    Foo() = default;

    Foo(const Foo&) = delete;    // here, dits would need to be calculated

    // A move constructor guaranteed to preserve iterator validity.
    Foo(Foo&& rhs) noexcept {
        data.swap(rhs.data);
        dits.swap(rhs.dits);
    }

    Foo& operator=(const Foo&) = delete;

    // A move assignment operator guaranteed to preserve iterator validity.
    Foo& operator=(Foo&& rhs) noexcept {
        data.swap(rhs.data);
        dits.swap(rhs.dits);
        return *this;
    }

    ~Foo() = default;
};

Vector iterator invalidation after inserting

First of all. STL iterators are the same insecure as pointers. Good or bad, this is so. We cannot change this. This means that you need to be careful when you are working with iterators.

Now what happens behind the scenes. Both iterators are essentially pointers. First one points to the current beginning of the vector body, the second one to the current end of the vector body. During insertion vector is allowed to move body of the vector to some other place. If vector will move the body, your iterator end will continue pointing to the same place. Even if vector will not move the beginning of the vector (sometimes this happens), your iterator will point to the last valid element (not after that last one as it should in normal case). Again, this will not be what you are expecting.

What is written above is just for understanding. You should never use this knowledge. You should check what actions invalidate what types of iterators and base your code only on what is explicitly allowed in the documentation.

---

Related Topics