Strange vector iterator problem - possible bug

Discussion in 'C++' started by Dave, Jan 6, 2005.

  1. Dave

    Dave Guest

    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!
    Dave, Jan 6, 2005
    #1
    1. Advertising

  2. 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:> <http://www.dietmar-kuehl.de/>
    <http://www.contendix.com> - Software Development & Consulting
    Dietmar Kuehl, Jan 6, 2005
    #2
    1. Advertising

  3. Dave

    Dave Guest

    Thank you very much! It's so nice to get a clear and complete answer :)
    Dave, Jan 6, 2005
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. pmatos
    Replies:
    6
    Views:
    23,733
  2. Replies:
    4
    Views:
    283
    Kenny McCormack
    Feb 21, 2006
  3. Replies:
    8
    Views:
    1,895
    Csaba
    Feb 18, 2006
  4. Javier
    Replies:
    2
    Views:
    547
    James Kanze
    Sep 4, 2007
  5. zl2k
    Replies:
    27
    Views:
    1,557
    Francesco S. Carta
    Sep 7, 2010
Loading...

Share This Page