Why does this vector iterator not become invalidated?

Question

I've read a few posts concerning iterator invalidation, and it seems that inserts that require a vector reallocation would invalidate iterators. Also shouldn't erases in the middle of the vector cause an invalidation?

I don't have a clear understanding of this, not sure why using these iterators after resizes and erases from begin, middle, and end doesn't break them:

#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(int argc, char** argv) {

    vector<int> v;
    v.reserve(10);

    for (int i = 0; i < 10; i++)
        v.push_back(i);

    for (auto x = v.begin(); x != v.end(); x++) {
        cout << *x << endl;
    }

    cout << endl << "RESIZE" << endl << endl;

    for (int i = 10; i < 20; i++)
        v.push_back(i);

    for (auto x = v.begin(); x != v.end(); x++) {
        cout << *x << endl;
    }

    cout << endl << "RESIZE 2" << endl << endl;

    for (int i = 20; i < 200; i++)
        v.push_back(i);

    for (auto x = v.begin(); x != v.end(); x++) {
        cout << *x << endl;
    }

    cout << endl << "REMOVES" << endl << endl;

    v.erase(v.begin());
    v.pop_back();
    v.erase(v.begin() + 17);

    for (auto x = v.begin(); x != v.end(); x++) {
        cout << *x << endl;
    }

    return 0;
}

Iterator validity depends on the type of container and on the operation. For example, for vector::erase, check the Iterator Validity section at http://www.cplusplus.com/reference/vector/vector/erase/ — jsantander, Apr 04 '14 at 23:04
That says that iterators pointing to the first element and beyond for a vector would be invalidated from an erase, but that seems to not be happening here where my `x` points to the first? — Instinct, Apr 04 '14 at 23:06
@Instinct I don't see any reuse of iterators going on here. Can you please indicate the line(s) on which you think this is happening? — Praetorian, Apr 04 '14 at 23:10
You don't make any insertions, erases etc. during the lifetime of any of the `x`'s. — M.M, Apr 04 '14 at 23:14
In your code you're grabbing new iterators every time you iterate over the container, so you're not really testing the erase and re-size cases you mention. Iterator invalidation happens when you copy the return value of say b.begin() to an iterator type, then call v.push_back(...) a few times, then try to use the iterator. Vectors, have a logical size, and a physical size s.t. physical >= logical. — Apriori, Apr 05 '14 at 01:40
Vectors are implemented with contiguous memory, so when a push_back(...) results in a logical size greater than the current physical size, the underlying memory has to be copied to a larger contiguous block of memory. The iterator has an internal pointer to this memory, so when this "grow" operation happens the iterators now internally reference a chunk of memory that is no longer part of the vector, hence they are invalidated. — Apriori, Apr 05 '14 at 01:41
An erase operation will never result in growing the vector, so the iterators will never be invalidated in this way, because they still point to valid memory. However, if you have an iterator to say 3 in the array {1,2,3,4} and you erase it, now your iterator points to 4, but it is still valid. — Apriori, Apr 05 '14 at 01:42
@Apriori This makes sense but I've rewritten the code having `auto x = v.begin();` right after the first 10 slot vector fill then removing `auto` from all future `x`'s in loops as to not redefine it, yet it still works perfectly? o_O — Instinct, Apr 05 '14 at 22:52
Try calling v.capacity() and storing the return value in some temporary after initializing your iterators. v.capacity() returns the current number of total allocated elements in the vector and is greater than or equal to v.size(). Now call v.push_back(...) until the vector's size exceeds the value returned from capacity() stored in the temporary value. It's when you increase the size past the previous capacity that the vector grows and the iterators are invalidated. — Apriori, Apr 07 '14 at 15:16
Just tried this, after each set of push backs the vector had to resize and up its capacity from its previous one I stored at first, yet the iterators still work. Are they still invalidated anyway? — Instinct, Apr 08 '14 at 23:08

jsantander · Answer 1 · 2014-04-04T23:20:27.133

4

Note that calling begin() or end() will always provide a sane iterator

However something like:

std:vector<int> v;
....

std::vector<int>::iterator i=v.begin();
v.erase(i);
std::cout << *i << std::endl;  // i iterator was invalidated by erasing it
                               // trying to access it or increment it is undefined behaviour.
std::cout << *v.begin() << std::endl;  // begin() provides always a sane iterator.

edited Apr 04 '14 at 23:20

answered Apr 04 '14 at 23:10

jsantander

4,972
16
27

In general, I always assume that it will not work :)... only if I need to do something fancy, I'll check the rules for each container and each operation... ;) – jsantander Apr 04 '14 at 23:13
In the case of UB if it "works" it actually doesn't work. "It works" is an expression that indicates something does /what it is intended to do/. With UB, there is /no intended behaviour/ so, you can't claim that it does it. – sehe Apr 04 '14 at 23:16
@sehe: Actually, there is what the naive and blissfully unaware programmer expects. At least that is the most reasonable definition for *it works* I could come up with. – Deduplicator Apr 04 '14 at 23:19
@sehe and Deduplicator... changed the wording... from the the *too colloquial* working/not working... :D – jsantander Apr 04 '14 at 23:21
@jsantander: I like to see sanity reign. +1 – Deduplicator Apr 04 '14 at 23:22

Deduplicator · Answer 2 · 2014-04-04T23:17:52.393

2

In your code, always when iterators are reused, there was no intervening modification of the vector, so no invalidation.

Iterators may be invalidated on resizing and inserting. Erasing only invalidates iterators at or after the erased element.

At least, those are the paraphrased rules for std::vector.

edited Apr 04 '14 at 23:17

answered Apr 04 '14 at 23:05

Deduplicator

44,692
7
66
118

What exactly qualifies as an "intervening modification"? I thought erasing from the middle certainly would be, and forcing a vector resize/copy of all elements to a new, larger array also? – Instinct Apr 04 '14 at 23:07
Yes, anything which might change element count. Also, explicitly reserving space. – Deduplicator Apr 04 '14 at 23:10
Actually, deletion invalidates all iterators beyond the deleted iterator(s) too. See **[Iterator Invalidation Rules](http://stackoverflow.com/questions/6438086/iterator-invalidation-rules)** – sehe Apr 04 '14 at 23:14
@Deduplicator then why does erasing the first element when `x` points to `v.begin()` not invalidate it? Assuming I'm not redeclaring x like in my original post, because for some reason declaring `auto x = v.begin();` immediately after the original 10 slot vector fill and removing `auto` from all future loop `x`'s as to not redeclare still works perfectly? – Instinct Apr 05 '14 at 22:57
It does invalidate. That does not guarantee a crash though. Also, if you assign a new one, the old one is gone... – Deduplicator Apr 05 '14 at 23:02

Why does this vector iterator not become invalidated?

2 Answers2