469,591 Members | 1,601 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 469,591 developers. It's quick & easy.

Strange vector iterator problem - possible bug

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>::push_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!

Jul 22 '05 #1
2 2193
Dave wrote:
When calling vector<int>::push_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.
--
<mailto:di***********@yahoo.com> <http://www.dietmar-kuehl.de/>
<http://www.contendix.com> - Software Development & Consulting

Jul 22 '05 #2
Thank you very much! It's so nice to get a clear and complete answer :)

Jul 22 '05 #3

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

29 posts views Thread by Hagen | last post: by
5 posts views Thread by Ernst Murnleitner | last post: by
17 posts views Thread by Michael Hopkins | last post: by
3 posts views Thread by codefixer | last post: by
14 posts views Thread by cayblood | last post: by
33 posts views Thread by Simon | last post: by
4 posts views Thread by Johan Pettersson | last post: by
4 posts views Thread by lutorm | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.