Does Resizing a Vector Invalidate Iterators

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 resizing an STL vector erase/invalidate its previous contents?

Resizing an STL vector may require reallocating the underlying storage. This may cause any number of elements to be destroyed and recreated, and all iterators are invalidated. Accessing an invalidated iterator is a common source of errors when using the STL.

The contents of each element will be the same, unless the copy constructor doesn't work.

int main(int argc, char *argv[])
{
    int data[] = { 1, 2, 3 };

    std::vector vec(data, data + 3);
    // vector contains 1, 2, 3

    std::vector::iterator i = vec.begin();
    cout << *i << endl; // prints 1
    int &ref = *i;
    cout << ref << endl; // prints 1

    vec.resize(6, 99);
    // vector now contains 1, 2, 3, 99, 99, 99

    // WRONG! may crash, may do the wrong thing, might work...
    // cout << *i << endl;

    // WRONG! invalid reference
    // cout << ref << endl;

    return 0;
}

Does std::string::resize(smaller_than_capacity) guarantee existing iterators are still valid?

Such requirement does not exist in Standard. See 21.3.3.2:

References, pointers, and iterators referring to the elements of a
basic_string sequence may be invalidated by the following uses of
that basic_string object:

(4.1) Passing as an argument to any
standard library function taking a reference to non-const
basic_string as an argument.

(4.2) Calling non-const member
functions, except operator[], at, data, front, back, begin, rbegin,
end, and rend.

Does std::vector::reserve guarantee that the implementation will not invalidate iterators in this case?

As long as you don't exceed preallocated capacity no reallocation should happen and no references or iterators referring to vector items should get invalidated. However since iterator returned by end() does not refer to any vector items it may still get invalidated.

23.3.11.3 vector capacity [vector.capacity]

...No reallocation shall take place during insertions that happen after a call to reserve() until the time when an insertion would make the size of the vector greater than the value of capacity()

...

23.3.11.5 vector modifiers [vector.modifiers]

...If no reallocation happens, all the iterators and references before the insertion point remain valid.

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.

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.

Does vector::erase reduce vector::capacity?

Not necessarily no. When reading the C++ standard (and cppreference proxies the standard remarkably well), if something is not explicitly mentioned, then assume such a something is not required.

It would possibly be sub-optimal for a C++ Standard Library implementation to do so.

What if size argument for std::vector::resize is equal to the current size?

This is probably just an error in the linked reference. The standard says following:

void resize(size_type sz);

Effects: If sz < size(), erases the last size() - sz elements from the sequence. Otherwise, appends sz - size() default-inserted elements to the sequence.

Since sz - size() is 0 in your case, it doesn't do anything.

Does Resizing a Vector Invalidate Iterators