Does .push_back invalidate existing vector iterators?

[Jim Langston]

Someone is working on some code, and during the iteration of a vector may
delete an element and push_back a new one. I was thinking that this may
invalidate the iteration iterator, but in my test it doesn't seem to. Here
is my test with the expected output of:

0 1 2 3 4 5
0 1 3 4 5 6
0 1 4 5 6 7
0 1 5 6 7 8
0 1 6 7 8 9

Is this just luck or is it defined behavior? That is, can push_back
invalidate an existing vector iterator? (In my code it would be it )

#include <iostream>
#include <string>
#include <vector>

int main()
{
std::vector<int> MyVector;

int Value;
for ( Value = 0; Value < 5; ++Value )
MyVector.push_back( Value );

for ( int i = 0; i < 5; ++i )
{
int Count = 0;
for ( std::vector<int>::iterator it = MyVector.begin(); it !=
MyVector.end(); )
{
std::cout << *it << " ";
if ( Count++ == 2 )
{
it = MyVector.erase( it );
MyVector.push_back( Value++ );
}
else
++it;
}
std::cout << std::endl;
}

std::string wait;
std::getline( std::cin, wait );
return 0;
}

 

[Rolf Magnus]

Someone is working on some code, and during the iteration of a vector may
delete an element and push_back a new one. I was thinking that this may
invalidate the iteration iterator, but in my test it doesn't seem to.
Here is my test with the expected output of:

0 1 2 3 4 5
0 1 3 4 5 6
0 1 4 5 6 7
0 1 5 6 7 8
0 1 6 7 8 9

Is this just luck or is it defined behavior? That is, can push_back
invalidate an existing vector iterator? (In my code it would be it )

It will, if the vector needs to re-allocate, that is, if before the
push_back() call, size()==capacity().

 

[Greg]

Someone is working on some code, and during the iteration of a vector may
delete an element and push_back a new one. I was thinking that this may
invalidate the iteration iterator, but in my test it doesn't seem to. Here
is my test with the expected output of:

0 1 2 3 4 5
0 1 3 4 5 6
0 1 4 5 6 7
0 1 5 6 7 8
0 1 6 7 8 9

Is this just luck or is it defined behavior? That is, can push_back
invalidate an existing vector iterator? (In my code it would be it )

Increasing the number of items in a vector (by whatever means or by
whatever number) may invalidate the vector's iterators only if the
addition of the item (or items) cause the vector's size to exceed its
current capacity.

Since your program first removes an item before adding one, the size of
the vector never increases beyond its initial size during the course of
the operation. So there is no risk of the vector's capacity being
exceeded and consequently no danger that any of the vector's iterators
will be invalidated.

Greg

 

[fungus]

...I was thinking that this may invalidate the iteration
iterator, but in my test it doesn't seem to. Here
is my test with the expected output of:

0 1 2 3 4 5
0 1 3 4 5 6
0 1 4 5 6 7
0 1 5 6 7 8
0 1 6 7 8 9

Is this just luck or is it defined behavior?

It was just luck. In C++ you should *NEVER* make
assumptions based on "well, it seems to work...".

can push_back invalidate an existing vector iterator?

Yes - see other replies for the reasons why.


--
<\___/>
/ O O \
\_____/ FTB. For email, remove my socks.


We’re judging how a candidate will handle a nuclear
crisis by how well his staff creates campaign ads.
It’s a completely nonsensical process.

 

[Jim Langston]

Someone is working on some code, and during the iteration of a vector may
delete an element and push_back a new one. I was thinking that this may
invalidate the iteration iterator, but in my test it doesn't seem to.
Here is my test with the expected output of:

0 1 2 3 4 5
0 1 3 4 5 6
0 1 4 5 6 7
0 1 5 6 7 8
0 1 6 7 8 9

Is this just luck or is it defined behavior? That is, can push_back
invalidate an existing vector iterator? (In my code it would be it )

#include <iostream>
#include <string>
#include <vector>

int main()
{
std::vector<int> MyVector;

int Value;
for ( Value = 0; Value < 5; ++Value )
MyVector.push_back( Value );

for ( int i = 0; i < 5; ++i )
{
int Count = 0;
for ( std::vector<int>::iterator it = MyVector.begin(); it !=
MyVector.end(); )
{
std::cout << *it << " ";
if ( Count++ == 2 )
{
it = MyVector.erase( it );
MyVector.push_back( Value++ );
}
else
++it;
}
std::cout << std::endl;
}

std::string wait;
std::getline( std::cin, wait );
return 0;
}

Thanks for the answers everyone. So as long as capacity() doesn't change,
the allocatore is valid.

Thanks.

 

[bjeremy]

Thanks for the answers everyone. So as long as capacity() doesn't change,
the allocatore is valid.

Thanks.

Yeah... but you probably want to program defensively and always assume
that the iterator will be invalidated

 

[Jim Langston]

Yeah... but you probably want to program defensively and always assume
that the iterator will be invalidated

True, but then the way around this is to use size_t instead of an iterator.
I prefer using iterators because it's much harder to fall off the end of the
vector.

 

[Mirek Fidler]

True, but then the way around this is to use size_t instead of an iterator.
I prefer using iterators because it's much harder to fall off the end of the
vector.

Interesting. I prefer indices for exactly the same reason

Mirek

 

[Greg]

Yeah... but you probably want to program defensively and always assume
that the iterator will be invalidated.

So in a nutshell: "programming defensively" is really a two-phase
process: in the first phase the programmer pretends that a catastrophic
bug exists in one of the program's third party libraries, in the second
phase the programmer writes code in the program's own sources to fix
the same imaginary bug in the third party library.

Greg

 

[Mirek Fidler]

So in a nutshell: "programming defensively" is really a two-phase
process: in the first phase the programmer pretends that a catastrophic

In nutshell: There is a very limited number of scenarios where
knowledge of iterator not being invalidated by mutating operation would
have any benefit. And there is a very high danger of being shot in the
leg relying on it.

 

[bjeremy]

So in a nutshell: "programming defensively" is really a two-phase
process: in the first phase the programmer pretends that a catastrophic
bug exists in one of the program's third party libraries, in the second
phase the programmer writes code in the program's own sources to fix
the same imaginary bug in the third party library.

Greg

No... I'm not sure what you inferred, I don't know where that whole
"catastrophic bug" rant came from, but what I was implying is that you
probably want to try and reduce your problem as to not introduce
special case scenarios. In this case, upon a push_back, the iterator
may or may not be invalid. This is dtermined at a lower layer you have
not control over this (ok...ok... let's not start arguing semantics),
but at your layer you have three choices on how to handle this
situation:
1. Always assume the iterator to be valid - we all can see how this
would be a train wreck waiting to happen
2. Design two cases, one to handle when the iterator is valid, on to
handle when the iterator is invalid. This creates the special case. I'm
sure you are a very competent programmer, as for myself, the more
special cases (or code for that matter) I write, the more chances I
have for introducing new bugs and reducing readability.
3. Always assume the iterator is invalid, and handle every scenario the
same homogenous way...