Can I dynamically add new elements to vector while looping it?

Discussion in 'C++' started by linq936@hotmail.com, Jun 13, 2006.

  1. Guest

    Hi,
    The following is a psudo code to describe my question:

    vector<int> ints;
    vector<int>::iterator itr;
    while (itr != ints.end()){
    int j = some_function(*i);
    if (j>0){
    ints.push_back(j);
    }
    ints.erase(itr);
    }

    Can it work? I dynamically add new element into a vector while I am
    looping the vector.
     
    , Jun 13, 2006
    #1
    1. Advertising

  2. Sharpdew Guest

    Because it pushes the new element into tail of vector, that is OK!
    wrote:
    > Hi,
    > The following is a psudo code to describe my question:
    >
    > vector<int> ints;
    > vector<int>::iterator itr;
    > while (itr != ints.end()){
    > int j = some_function(*i);
    > if (j>0){
    > ints.push_back(j);
    > }
    > ints.erase(itr);
    > }
    >
    > Can it work? I dynamically add new element into a vector while I am
    > looping the vector.
     
    Sharpdew, Jun 13, 2006
    #2
    1. Advertising

  3. Alan Johnson Guest

    wrote:
    > Hi,
    > The following is a psudo code to describe my question:
    >
    > vector<int> ints;
    > vector<int>::iterator itr;
    > while (itr != ints.end()){
    > int j = some_function(*i);
    > if (j>0){
    > ints.push_back(j);
    > }
    > ints.erase(itr);
    > }
    >
    > Can it work? I dynamically add new element into a vector while I am
    > looping the vector.
    >


    In general the answer is no. If insert causes reallocation to happen
    (because it causes size() to exceed capacity()), then your iterator itr
    will become invalid.

    In your specific case, it looks as if you always decrease the size by 1
    during a loop iteration, and sometimes increase the size by 1 (for a net
    change of 0). I suggest you move the erase call ahead of the push_back,
    in which case you can be certain that the size never increases during an
    iteration, which will make the reallocation behavior predictable. That is:

    vector<int> ints;
    vector<int>::iterator itr;
    while (itr != ints.end()){
    int j = some_function(*i);
    ints.erase(itr);
    if (j>0){
    ints.push_back(j);
    }
    }

    Note that in your version, during the first iteration of the loop the
    size of the vector may increase, which may cause reallocation, which may
    invalidate your iterator.

    --
    Alan Johnson
     
    Alan Johnson, Jun 13, 2006
    #3
  4. Alan Johnson Guest

    wrote:
    > Hi,
    > The following is a psudo code to describe my question:
    >
    > vector<int> ints;
    > vector<int>::iterator itr;
    > while (itr != ints.end()){
    > int j = some_function(*i);
    > if (j>0){
    > ints.push_back(j);
    > }
    > ints.erase(itr);
    > }
    >
    > Can it work? I dynamically add new element into a vector while I am
    > looping the vector.
    >


    As an additional note to my other response, if your problem allows it,
    you might consider going through the vector in reverse order. The
    complexity of erase is linear in the number of elements after the one
    you are erasing, meaning that going forward through the vector erasing
    elements is an O(n^2) algorithm, but going through it in reverse would
    be O(n).

    --
    Alan Johnson
     
    Alan Johnson, Jun 13, 2006
    #4
  5. In message <>,
    Sharpdew <> writes

    [top-posting corrected]

    > wrote:
    >> Hi,
    >> The following is a psudo code to describe my question:
    >>
    >> vector<int> ints;
    >> vector<int>::iterator itr;

    itr = ints.begin();
    >> while (itr != ints.end()){
    >> int j = some_function(*i);

    int j = some_function(*itr);
    >> if (j>0){
    >> ints.push_back(j);
    >> }
    >> ints.erase(itr);

    itr = ints.erase(itr);
    >> }
    >>
    >> Can it work? I dynamically add new element into a vector while I am
    >> looping the vector.

    >
    >Because it pushes the new element into tail of vector, that is OK!


    Wrong. The call of erase(itr) invalidates itr, and push_back() may
    trigger a reallocation, invalidating all iterators.

    --
    Richard Herring
     
    Richard Herring, Jun 13, 2006
    #5
  6. rossum Guest

    On Mon, 12 Jun 2006 23:25:34 -0700, Alan Johnson
    <> wrote:

    > wrote:
    >> Hi,
    >> The following is a psudo code to describe my question:
    >>
    >> vector<int> ints;
    >> vector<int>::iterator itr;
    >> while (itr != ints.end()){
    >> int j = some_function(*i);
    >> if (j>0){
    >> ints.push_back(j);
    >> }
    >> ints.erase(itr);
    >> }
    >>
    >> Can it work? I dynamically add new element into a vector while I am
    >> looping the vector.
    >>

    >
    >In general the answer is no. If insert causes reallocation to happen
    >(because it causes size() to exceed capacity()), then your iterator itr
    >will become invalid.
    >

    If the maximum possible size is known in advance, then a call to
    reserve() would avoid the possibility of reallocation during the loop.

    rossum

    >In your specific case, it looks as if you always decrease the size by 1
    >during a loop iteration, and sometimes increase the size by 1 (for a net
    >change of 0). I suggest you move the erase call ahead of the push_back,
    >in which case you can be certain that the size never increases during an
    >iteration, which will make the reallocation behavior predictable. That is:
    >
    > vector<int> ints;
    > vector<int>::iterator itr;
    > while (itr != ints.end()){
    > int j = some_function(*i);
    > ints.erase(itr);
    > if (j>0){
    > ints.push_back(j);
    > }
    > }
    >
    >Note that in your version, during the first iteration of the loop the
    >size of the vector may increase, which may cause reallocation, which may
    >invalidate your iterator.
     
    rossum, Jun 13, 2006
    #6

  7. > vector<int> ints;
    > vector<int>::iterator itr;
    > while (itr != ints.end()){
    > int j = some_function(*i);
    > if (j>0){
    > ints.push_back(j);
    > }
    > ints.erase(itr);
    > }



    instead of iterators you could use indices:

    int count = (int)ints.size();
    while(itr != ints.begin() + count)
    {
    vector<int>::iterator ii(ints.begin() + i);
    int j=some_function(*ii);
    if(j>0) ints.push_back(j);
    ints.erase(itr); // Now you want a --i; as well!!!
    }
     
    Gernot Frisch, Jun 13, 2006
    #7
  8. In message <>, Gernot Frisch
    <> writes
    >
    >> vector<int> ints;
    >> vector<int>::iterator itr;
    >> while (itr != ints.end()){
    >> int j = some_function(*i);
    >> if (j>0){
    >> ints.push_back(j);
    >> }
    >> ints.erase(itr);
    >> }

    >
    >
    >instead of iterators you could use indices:


    So where are they? I don't see anything looking like ints anywhere in
    the following, and it's still full of iterators. How is it supposed to
    be an improvement?
    >
    >int count = (int)ints.size();
    >while(itr != ints.begin() + count)


    That's no different from saving the value of ints.end() and comparing
    against the saved value. And itr hasn't been initialised yet.

    >{
    > vector<int>::iterator ii(ints.begin() + i);
    > int j=some_function(*ii);
    > if(j>0) ints.push_back(j);


    push_back() can invalidate all iterators. The following line is now UB.

    > ints.erase(itr); // Now you want a --i; as well!!!


    erase(itr) invalidates itr. The idiom is

    itr = ints.erase(itr)

    which leaves itr pointing to the element after the one erased, or
    ints.end() if there is no such element.

    >}


    --
    Richard Herring
     
    Richard Herring, Jun 13, 2006
    #8
    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. John Black
    Replies:
    4
    Views:
    446
    Jeff Flinn
    May 28, 2004
  2. robk
    Replies:
    1
    Views:
    508
    Peter Jansson
    Mar 25, 2005
  3. Replies:
    8
    Views:
    1,987
    Csaba
    Feb 18, 2006
  4. Replies:
    16
    Views:
    841
    James Kanze
    Apr 12, 2007
  5. Replies:
    5
    Views:
    294
Loading...

Share This Page