vector push_back in STL?

Question

I found a sample program which i tried for STL Vectors

#include <vector>
#include <iostream>
using namespace std;
/* This one may well work with some compilers/OS, and crash with
 others. Who said the STL was safe ?? */
int main() {
 vector<int> v;
 v.push_back(1);
 v.push_back(2);
 v.push_back(3);
 v.push_back(4);
 for (vector<int>::iterator i = v.begin();
 i != v.end(); i++) {
 cout << *i << endl;
 if (*i == 1) {
 v.push_back(5);
 }
 }
}

I was expecting result: 1 2 3 4 5

but, result is very weird - 1 0 3 4 0 0 33 0 0 0 0 0 0 0 49 0 1 2 3 4 5 5

I am guessing, this has some logic which i am missing because these don't seem like garbage values, because result is same always. After doing push_back, is iterator getting reset or something? I have read it somewhere that appending to a vector while iterating over it isn't a good idea. My question is why?

After some search over internet,

 if (*i == 1) {
 size_t diff = i-v.begin();
 v.push_back(5);
 i = v.begin()+diff;
 }

this will solve the issue.

• user2486888: Keyword: iterator invalidation.
• Remy Lebeau: Regarding your workaround, have a look at std::distance() and std::advance() instead of using the - and + operators.
• Vishwadeep Singh: Okay. which will be the pure STL solution. by single problem, i had figured out lot of things. Thanks

Answer 1

You are modifying the std::vector while looping through it. When calling std::vector::push_back(), if its current size() is equal to its current capacity(), the std::vector will have to reallocate its internal data storage to increase its capacity before it can store the new value. That reallocation will invalidate the loop iterator (the end() iterator is always invalidated, but you are re-evaluating it on each iteration, so it is OK in this case).

To do what you are attempting, either:

1. reserve() the vector's capacity before entering the loop to avoid reallocation and thus avoid invalidating the loop iterator.

2. reset the iterators after each reallocation.

3. use a std::list instead, as the loop iterator will not get invalidated by std::list::push_back().

• Vishwadeep Singh: got it. STL is a very deep sea.
• Vishwadeep Singh: reserve seems a good approach and will save some temp variable handing.
• Remy Lebeau: @Vishwadeep: don't confuse reserve() with resize(). reserve() merely allocates the vector's internal memory and sets its capacity(), but does not affect its size(), so you would still need temp variables and push_back() and such. If you use resize() instead, which does affect size(), then you could avoid push_back() and use pointers/references to the vector elements directly.
• Vishwadeep Singh: yes you are correct. anyways i will go with the thumb rule that appending to a vector while iterating over it isn't a good idea. Else handle the situation.

Answer 2

Because std::vector::push_back might invalidate all iterators.

If the new size() is greater than capacity() then all iterators and references (including the past-the-end iterator) are invalidated.

For your code, you can use std::vector::reserve to avoid reallocation.

Increase the capacity of the container to a value that's greater or equal to new_cap.

int main() {
 vector<int> v;
 v.reserve(5); // ensure no reallocation until size() == 5
 v.push_back(1);
 v.push_back(2);
 v.push_back(3);
 v.push_back(4);
 for (vector<int>::iterator i = v.begin();
 i != v.end(); i++) {
 cout << *i << endl;
 if (*i == 1) {
 v.push_back(5);
 }
 }
}

And as you said, appending to a vector while iterating over it isn't a good idea.

• Vishwadeep Singh: oh ok. means it will invalidate when capacity is increased, this i would have done after 6-7 items, then i wouldn't have faced the issue. This gave me a better picture. Thanks

Answer 3

Some good options in existing answers, but worth mentioning another oft forgotten option when you know you're facing potential iterator invalidation due to push_back resizing beyond capacity:

for (size_t i = 0; i < v.size(); ++i) {
 cout << v[i] << endl;
 if (v[i] == 1)
 v.push_back(5);
}

It's "C style", but simple and intuitive.