Bizarre vector insertion behavior - can someone please enlighten?

Discussion in 'C++' started by ckfan.painter@gmail.com, Mar 7, 2007.

  1. Guest

    I've run into a seemingly bizarre problem with insert() for
    std::vector. (This was done on Microsoft Visual C++ 2005 express
    version 8...maybe it is a compiler specific bug?)

    Here's the code:

    //===================

    // vector tester 3.cpp : main project file.

    #include "stdafx.h"
    #include<vector>

    int main(array<System::String ^> ^args)
    {
    std::vector<int> vectorList;

    for (unsigned int i = 0; i < 45; ++i) // works if 45 is
    replaced with smaller value.
    vectorList.push_back(i);

    unsigned int aBegin = 25;
    unsigned int aEnd = 35; // works if 35 is replaced with 34.

    vectorList.insert(vectorList.begin() + 35, // works if 35 is
    replaced by 36, 37, 38 ...
    // but not if 35 is replaced by 34, 33, 32...
    vectorList.begin() + aBegin, vectorList.begin() + aEnd);

    return 0;
    }

    //========================

    When this is run, an error occurs during the insertion about
    incompatible vector iterators.
    At first I thought, maybe this is happening because I'm trying to
    insert into the range that I am copying...but, if the size of the
    vector is just changed from 45 elements long to 44 elements long...the
    program works! I think that is just bizarre.

    Does anybody understand what is going on here? It would be crazy to
    write code that might fail whenever it encounters a vector.insert() so
    I would like to understand the reason this code fails but when the 45
    is replaced with 44, it works.

    Any insight appreciated!

    CK
     
    , Mar 7, 2007
    #1
    1. Advertising

  2. wrote:
    > I've run into a seemingly bizarre problem with insert() for
    > std::vector. (This was done on Microsoft Visual C++ 2005 express
    > version 8...maybe it is a compiler specific bug?)
    >
    > Here's the code:
    >
    > //===================
    >
    > // vector tester 3.cpp : main project file.
    >
    > #include "stdafx.h"


    You might want to consider weeding MS-isms out before posting here.

    > #include<vector>
    >
    > int main(array<System::String ^> ^args)


    That's not Standard C++, sorry. For managed extensions, try MS
    newsgroups.

    > {
    > std::vector<int> vectorList;
    >
    > for (unsigned int i = 0; i < 45; ++i) // works if 45 is
    > replaced with smaller value.


    What "works"? By extension, what "doesn't"?

    > vectorList.push_back(i);
    >
    > unsigned int aBegin = 25;
    > unsigned int aEnd = 35; // works if 35 is replaced with 34.
    >
    > vectorList.insert(vectorList.begin() + 35, // works if 35 is
    > replaced by 36, 37, 38 ...
    > // but not if 35 is replaced by 34, 33, 32...
    > vectorList.begin() + aBegin, vectorList.begin() + aEnd);


    Any insertion into the middle of the vector can invalidate _all_
    of its iterators (the one returned by 'begin()' included). Your
    program most likely has undefined behaviour.

    You can avoid that if you reserve memory in the vector:

    vectorList.reserve(vectorList.size() + how_many_to_insert);

    >
    > return 0;
    > }
    >
    > //========================
    >
    > When this is run, an error occurs during the insertion about
    > incompatible vector iterators.


    "incompatible"? I don't think this is a Standard term.

    > At first I thought, maybe this is happening because I'm trying to
    > insert into the range that I am copying...but, if the size of the
    > vector is just changed from 45 elements long to 44 elements long...the
    > program works! I think that is just bizarre.


    It isn't. See above.

    > Does anybody understand what is going on here? It would be crazy to
    > write code that might fail whenever it encounters a vector.insert() so
    > I would like to understand the reason this code fails but when the 45
    > is replaced with 44, it works.


    Do not insert the elements of a vector into itself without reserving
    first.

    V
    --
    Please remove capital 'A's when replying by e-mail
    I do not respond to top-posted replies, please don't ask
     
    Victor Bazarov, Mar 7, 2007
    #2
    1. Advertising

  3. Guest

    Hi Victor,

    Thank you for your tips about posting here. It was my first post to
    this newsgroup.

    I thought of the reserve possibility, and it doesn't fix the problem.
    When the code is run, I get:

    Debug Assertion Failed!

    Program:...
    File: C:\Program Files\Microsoft Visual Studio 8\VC\include\vector
    Line: 238

    Expression: vector iterators incompatible


    I took a look at Stroustrup's examples with fruit (3rd ed., p. 453),
    and noticed that he avoids inserting a segment of a vector into
    itself. However, Microsoft's own help on vector insert does use an
    example of such an insertion. Also Stroustrup does not mention any
    concern with self-insertion.

    The only way I have of getting around this error that I hope is a
    consistent fix is to do the following:

    std::vector<int> temp;
    temp.assign(vectorList.begin() + aBegin, vectorList.begin() +
    aEnd);
    vectorList.insert(vectorList.begin() + 35, temp.begin(),
    temp.end());

    Does the code I posted earlier run without the error on other
    compilers? Sorry about the MS-isms.

    CK
     
    , Mar 7, 2007
    #3
  4. Kai-Uwe Bux Guest

    Victor Bazarov wrote:

    > wrote:

    [snip}
    >> std::vector<int> vectorList;
    >>
    >> for (unsigned int i = 0; i < 45; ++i) // works if 45 is
    >> replaced with smaller value.

    >
    > What "works"? By extension, what "doesn't"?
    >
    >> vectorList.push_back(i);
    >>
    >> unsigned int aBegin = 25;
    >> unsigned int aEnd = 35; // works if 35 is replaced with 34.
    >>
    >> vectorList.insert(vectorList.begin() + 35, // works if 35 is
    >> replaced by 36, 37, 38 ...
    >> // but not if 35 is replaced by 34, 33, 32...
    >> vectorList.begin() + aBegin, vectorList.begin() + aEnd);

    [snip]
    >> Does anybody understand what is going on here? It would be crazy to
    >> write code that might fail whenever it encounters a vector.insert() so
    >> I would like to understand the reason this code fails but when the 45
    >> is replaced with 44, it works.

    >
    > Do not insert the elements of a vector into itself without reserving
    > first.


    Actually, that can be phrased more general: never use

    a.insert(p,i,j) // p : iterator into the vector
    // i,j : iterators

    to insert elements of a vector into itself. The precondition for this method
    is stated in Table 67 as: pre: i,j are not iterators into a.


    Best

    Kai-Uwe Bux
     
    Kai-Uwe Bux, Mar 7, 2007
    #4
  5. Hi,
    I'm not sure, but I think the iterator doesn't keep a pointer to
    its vector, but a pointer to the vector's data (which is an array).
    Now I think, when you insert into the vector and the vector has
    to reallocate its data array, the pointer in the iterator becomes
    invalid. Maybe it works for values lower than 35, because reallocation
    doesn't happen then. But that's just a wild guess.

    Regards
    Thorsten
     
    Thorsten Kiefer, Mar 7, 2007
    #5
  6. wrote:
    > [..]
    > Does the code I posted earlier run without the error on other
    > compilers? [..]


    I am not even going to try. It has undefined behaviour, and
    as such can cause nasal demons to take to the air.

    V
    --
    Please remove capital 'A's when replying by e-mail
    I do not respond to top-posted replies, please don't ask
     
    Victor Bazarov, Mar 7, 2007
    #6
  7. Guest

    Thanks to all for their replies.

    It seems that the lesson I have to learn is that an official reference
    to the standard template library would be valuable.

    Is that what the "Table 67" is from that Kae-Uwe Bux refers to? Could
    you please provide the name of the reference source? I googled it and
    did find a Table 67 in a gcc.gnu.org website. Is that the source?

    CK
     
    , Mar 7, 2007
    #7
  8. wrote:
    > Thanks to all for their replies.
    >
    > It seems that the lesson I have to learn is that an official reference
    > to the standard template library would be valuable.
    >
    > Is that what the "Table 67" is from that Kae-Uwe Bux refers to? Could
    > you please provide the name of the reference source? I googled it and
    > did find a Table 67 in a gcc.gnu.org website. Is that the source?


    The Standard document. Table 67 is titled "Sequence requirements (in
    addition to container)". See FAQ or search the archives on how to get
    a copy of the Standard.

    V
    --
    Please remove capital 'A's when replying by e-mail
    I do not respond to top-posted replies, please don't ask
     
    Victor Bazarov, Mar 7, 2007
    #8
  9. Dave Steffen Guest

    writes:

    > Thanks to all for their replies.
    >
    > It seems that the lesson I have to learn is that an official reference
    > to the standard template library would be valuable.


    Every C++ programmer should have Josuttis' "The C++ Standard Library"
    on their desk, among others.

    ----------------------------------------------------------------------
    Dave Steffen, Ph.D. Disobey this command!
    Software Engineer IV - Douglas Hofstadter
    Numerica Corporation
    dg@steffen a@t numerica d@ot us (remove @'s to email me)
     
    Dave Steffen, Mar 7, 2007
    #9
  10. Alan Johnson Guest

    wrote:
    > Thanks to all for their replies.
    >
    > It seems that the lesson I have to learn is that an official reference
    > to the standard template library would be valuable.
    >
    > Is that what the "Table 67" is from that Kae-Uwe Bux refers to? Could
    > you please provide the name of the reference source? I googled it and
    > did find a Table 67 in a gcc.gnu.org website. Is that the source?
    >
    > CK
    >


    Not "official", but this is a quite good reference:
    http://www.sgi.com/tech/stl/table_of_contents.html

    --
    Alan Johnson
     
    Alan Johnson, Mar 8, 2007
    #10
    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. Steve
    Replies:
    6
    Views:
    431
    Andrew Glasgow
    Feb 14, 2004
  2. Ray
    Replies:
    23
    Views:
    758
    Christian Tismer
    Dec 25, 2005
  3. Replies:
    8
    Views:
    1,999
    Csaba
    Feb 18, 2006
  4. Replies:
    0
    Views:
    520
  5. kevin

    Please enlighten me:-0 HELP Please

    kevin, Sep 1, 2003, in forum: Javascript
    Replies:
    2
    Views:
    119
    kevin
    Sep 4, 2003
Loading...

Share This Page