Strange vector iterator problem - possible bug

[Dave]

I'm crossposting this to both comp.lang.c++ and gnu.gcc because I'm not
sure if this is correct behavior or not, and I'm using the gcc STL and
compiler.

When calling vector<int>:ush_back(0), an iterator that I've set in a
loop gets changed. Here's an example of the problem (sorry about the
lack of indentation, posting this from Google):

#include <vector>
#include <iostream>

using namespace std;

typedef vector<int> T;
typedef T::iterator I;

T foo;

foo.push_back(1);

for (I i = foo.begin(); i != foo.end(); ++i) {

// Output of this is 0.
cout << (i - foo.begin());

foo.push_back(0);

// Output of this is -8.
cout << (i - foo.begin());

}

Now, I know that foo.end() will change because of the push_back and
this would create an infinite loop, but that's not an issue in my code,
I've just left out the irrelevant parts of the loop. I've put those
cout()s directly around the push_back(), and that's what I got. Should
an iterator be completely invalidated by a push_back? If so, is there a
way to re-align the iterator without something like "tmp = i -
foo.begin(); foo.push_back(0); i = foo.begin() + tmp;"? If not, and
this is a bug, how do I go about reporting this problem to the GCC
devs?

Thanks for your time and help!

 

[Dietmar Kuehl]

When calling vector<int>:ush_back(0), an iterator that I've set in a
loop gets changed.

No, it isn't changed, it is invalidated! The 'vector's internal array
is moved to a different location when inserting more items if
insufficient memory was allocated. You can avoid this by using
'reserve()'.

Here's an example of the problem (sorry about the
lack of indentation, posting this from Google):

I'm also posting through the new Google interface which *sucks*. I'm
prefixing lines with a pipe to allow readable indentation...

#include <vector>
#include <iostream>

using namespace std;

typedef vector<int> T;
typedef T::iterator I;

T foo;

foo.push_back(1);

for (I i = foo.begin(); i != foo.end(); ++i) {

// Output of this is 0.
cout << (i - foo.begin());

foo.push_back(0);

This line invalidates all iterators, pointers, and reference to 'foo'
or its elements. This is expected behavior (although the standard makes
no guarantee when exactly the iterators are really invalidated: an
implementation may choose to overallocate the elements).

// Output of this is -8.
cout << (i - foo.begin());

The "-8" is just an accidental reasonably sized value. It could be
anything. You can avoid this problem by inserting

foo.reserve(16);

prior to the loop (well, the problem will occur at some point anyway
because you created an infinite loop as far as I can tell).

}

Now, I know that foo.end() will change because of the push_back and
this would create an infinite loop, but that's not an issue in my code,
I've just left out the irrelevant parts of the loop. I've put those
cout()s directly around the push_back(), and that's what I got. Should
an iterator be completely invalidated by a push_back?

Invalidating iterators normally has no impact on the iterator itself:
it is just unchanged but using it is a programming error. There are
some STL implementations (e.g. Safe STL) which try to capture problems
like this and give meaningful error messages.

If so, is there a
way to re-align the iterator without something like "tmp = i -
foo.begin(); foo.push_back(0); i = foo.begin() + tmp;"?

You can a priori 'reserve()' an approriate number of elements. If this
is unfeasable, you need to realign your iterators in a way similar to
what you have posted. Of course, you may also choose to use indices in
this case as these don't get invalidated unless you shrink the
'vector'.

If not, and
this is a bug, how do I go about reporting this problem to the GCC
devs?

It isn't a bug.

 

[Dave]

Thank you very much! It's so nice to get a clear and complete answer