deleting vector elements while looping thru it

Discussion in 'C++' started by kaferro@hotmail.com, Apr 11, 2007.

  1. Guest

    What is the typical way to loop through a vector while deleting
    certain elements during the loop process? The code below works, but I
    am wondering if there is a better solution.


    vector<int> vTmp;
    vTmp.push_back(1);
    vTmp.push_back(2);
    vTmp.push_back(1);
    vTmp.push_back(2);
    vTmp.push_back(1);
    vTmp.push_back(1);

    for(int x=0; x<vTmp.size(); x++)
    {
    if(vTmp[x]==1)
    {
    vTmp.erase(vTmp.begin()+x,vTmp.begin()+x+1);
    x--; //to account for new size
    }
    }
     
    , Apr 11, 2007
    #1
    1. Advertising

  2. wrote:
    > What is the typical way to loop through a vector while deleting
    > certain elements during the loop process? The code below works, but I
    > am wondering if there is a better solution.
    >
    >
    > vector<int> vTmp;
    > vTmp.push_back(1);
    > vTmp.push_back(2);
    > vTmp.push_back(1);
    > vTmp.push_back(2);
    > vTmp.push_back(1);
    > vTmp.push_back(1);
    >
    > for(int x=0; x<vTmp.size(); x++)
    > {
    > if(vTmp[x]==1)
    > {
    > vTmp.erase(vTmp.begin()+x,vTmp.begin()+x+1);
    > x--; //to account for new size
    > }
    > }


    vTmp.erase(std::remove_if(vTmp.begin(), vTmp.end(), 1));

    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, Apr 11, 2007
    #2
    1. Advertising

  3. none Guest

    Victor Bazarov a écrit :
    > wrote:
    >> What is the typical way to loop through a vector while deleting
    >> certain elements during the loop process? The code below works, but I
    >> am wondering if there is a better solution.
    >>
    >>
    >> vector<int> vTmp;
    >> vTmp.push_back(1);
    >> vTmp.push_back(2);
    >> vTmp.push_back(1);
    >> vTmp.push_back(2);
    >> vTmp.push_back(1);
    >> vTmp.push_back(1);
    >>
    >> for(int x=0; x<vTmp.size(); x++)
    >> {
    >> if(vTmp[x]==1)
    >> {
    >> vTmp.erase(vTmp.begin()+x,vTmp.begin()+x+1);
    >> x--; //to account for new size
    >> }
    >> }

    >
    > vTmp.erase(std::remove_if(vTmp.begin(), vTmp.end(), 1));
    >
    > V


    std::remove_if(vTmp.begin(), vTmp.end(), 1);
    should be enough...
    --
    JF
     
    none, Apr 11, 2007
    #3
  4. Pete Becker Guest

    none wrote:
    > Victor Bazarov a écrit :
    >> wrote:
    >>> What is the typical way to loop through a vector while deleting
    >>> certain elements during the loop process? The code below works, but I
    >>> am wondering if there is a better solution.
    >>>
    >>>
    >>> vector<int> vTmp;
    >>> vTmp.push_back(1);
    >>> vTmp.push_back(2);
    >>> vTmp.push_back(1);
    >>> vTmp.push_back(2);
    >>> vTmp.push_back(1);
    >>> vTmp.push_back(1);
    >>>
    >>> for(int x=0; x<vTmp.size(); x++)
    >>> {
    >>> if(vTmp[x]==1)
    >>> {
    >>> vTmp.erase(vTmp.begin()+x,vTmp.begin()+x+1);
    >>> x--; //to account for new size
    >>> }
    >>> }

    >>
    >> vTmp.erase(std::remove_if(vTmp.begin(), vTmp.end(), 1));
    >>
    >> V

    >
    > std::remove_if(vTmp.begin(), vTmp.end(), 1);
    > should be enough...


    remove_if doesn't actually remove things, it just reshuffles the
    sequence so that the rejected elements are at the end. Having done that,
    you have to tell the vector that those elements are no longer part of
    the controlled sequence. You do that with erase, passing the iterator
    that was returned by remove_if as the start of the sequence to be
    erased, and the vector's end iterator as the end.

    The proposed code isn't quite right. It should use remove (since its
    third argument is a value; remove_if takes a predicate), and it's
    missing an end iterator. Should be:

    vTmpl.erase(std::remove(vTmp.begin(), vTmp.end(), 1), vTmp.end());

    --

    -- Pete
    Roundhouse Consulting, Ltd. (www.versatilecoding.com)
    Author of "The Standard C++ Library Extensions: a Tutorial and
    Reference." (www.petebecker.com/tr1book)
     
    Pete Becker, Apr 11, 2007
    #4
  5. none" <""jf\"@(none) wrote:
    > Victor Bazarov a écrit :
    >> wrote:
    >>> What is the typical way to loop through a vector while deleting
    >>> certain elements during the loop process? The code below works,
    >>> but I am wondering if there is a better solution.
    >>>
    >>>
    >>> vector<int> vTmp;
    >>> vTmp.push_back(1);
    >>> vTmp.push_back(2);
    >>> vTmp.push_back(1);
    >>> vTmp.push_back(2);
    >>> vTmp.push_back(1);
    >>> vTmp.push_back(1);
    >>>
    >>> for(int x=0; x<vTmp.size(); x++)
    >>> {
    >>> if(vTmp[x]==1)
    >>> {
    >>> vTmp.erase(vTmp.begin()+x,vTmp.begin()+x+1);
    >>> x--; //to account for new size
    >>> }
    >>> }

    >>
    >> vTmp.erase(std::remove_if(vTmp.begin(), vTmp.end(), 1));
    >>
    >> V

    >
    > std::remove_if(vTmp.begin(), vTmp.end(), 1);
    > should be enough...


    No, '1' in that case is not a valid predicate. I messed up. It
    ought to be

    vTmp.erase(std::remove(vTmp.begin(), vTmp.end(), 1));

    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, Apr 11, 2007
    #5
  6. Guest

    I oversimplified my question because I take actions before I erase the
    element from the vector.

    Revised example code:

    vector<cObj> vTmp;
    vector<cObj> vErrors;
    vTmp.push_back(obj1);
    vTmp.push_back(obj2);
    vTmp.push_back(obj3);
    vTmp.push_back(obj4);

    for(int x=0; x<vTmp.size(); x++)
    {
    if(vTmp[x].returnName=="NA")
    {
    vErrors.push_back(vTmp[x]);
    vTmp.erase(vTmp.begin()+x,vTmp.begin()+x+1);
    x--; //to account for new size
    }
    }
     
    , Apr 11, 2007
    #6
  7. wrote:
    > I oversimplified my question because I take actions before I erase the
    > element from the vector.
    >
    > Revised example code:
    >
    > vector<cObj> vTmp;
    > vector<cObj> vErrors;
    > vTmp.push_back(obj1);
    > vTmp.push_back(obj2);
    > vTmp.push_back(obj3);
    > vTmp.push_back(obj4);
    >
    > for(int x=0; x<vTmp.size(); x++)
    > {
    > if(vTmp[x].returnName=="NA")
    > {
    > vErrors.push_back(vTmp[x]);
    > vTmp.erase(vTmp.begin()+x,vTmp.begin()+x+1);
    > x--; //to account for new size
    > }
    > }


    struct retNameIs
    {
    const char* name;
    retNameIs(const char* n) : name(n) {}
    bool operator()(cObj const& o) {
    return o.returnName == name;
    }
    };

    ...
    vector<cObj> vTmp;
    vTmp.push_back(obj1);
    vTmp.push_back(obj2);
    vTmp.push_back(obj3);
    vTmp.push_back(obj4);

    vector<cObj>::iterator it =
    std::remove_if(vTmp.begin(), vTmp.end(), retNameIs("NA"));
    vector<cObj> vErrors(it, vTmp.end());
    vTmp.erase(it, vTmp.end());

    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, Apr 11, 2007
    #7
  8. On Wed, 11 Apr 2007 11:17:51 -0400, Pete Becker wrote:
    >remove_if doesn't actually remove things, it just reshuffles the
    >sequence so that the rejected elements are at the end.


    The Standard doesn't specify that 'rejected' elements can be found at
    the end of the sequence.



    --
    Roland Pibinger
    "The best software is simple, elegant, and full of drama" - Grady Booch
     
    Roland Pibinger, Apr 11, 2007
    #8
  9. Roland Pibinger wrote:
    > On Wed, 11 Apr 2007 11:17:51 -0400, Pete Becker wrote:
    >> remove_if doesn't actually remove things, it just reshuffles the
    >> sequence so that the rejected elements are at the end.

    >
    > The Standard doesn't specify that 'rejected' elements can be found at
    > the end of the sequence.


    The algorithm is called "in-place". What besided "reshuffles" can
    that mean? 'remove_if' returns the iterator that points to the _end_
    of the resulting sequence. What besides placing the "removed"
    elements of the sequence beyond the new end could it mean? IOW, if
    you apply all the definitions of what 'remove' ('remove_if') does,
    it results in moving the rejected elements within the same sequence
    beyond what it returns as new end of the sequence.

    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, Apr 11, 2007
    #9
  10. Pete Becker Guest

    Victor Bazarov wrote:
    > Roland Pibinger wrote:
    >> On Wed, 11 Apr 2007 11:17:51 -0400, Pete Becker wrote:
    >>> remove_if doesn't actually remove things, it just reshuffles the
    >>> sequence so that the rejected elements are at the end.

    >> The Standard doesn't specify that 'rejected' elements can be found at
    >> the end of the sequence.

    >
    > The algorithm is called "in-place". What besided "reshuffles" can
    > that mean?


    Actually, he's right, although it's irrelevant to this particular
    discussion. remove and remove_if leave whatever junk they fell like at
    the end of the original sequence. Typically it's the elements that were
    there before, not necessarily the ones that were rejected. So for the
    example under discussion, the tail of the array would not hold all 1's
    unless they were there to begin with. Typically you'd see a vector
    holding, say, 1,3,1,5,7,1 turning into 3,5,7,5,7,1. The last three
    elements are the leftovers.

    --

    -- Pete
    Roundhouse Consulting, Ltd. (www.versatilecoding.com)
    Author of "The Standard C++ Library Extensions: a Tutorial and
    Reference." (www.petebecker.com/tr1book)
     
    Pete Becker, Apr 11, 2007
    #10
  11. Pete Becker Guest

    Pete Becker wrote:
    > Victor Bazarov wrote:
    >> Roland Pibinger wrote:
    >>> On Wed, 11 Apr 2007 11:17:51 -0400, Pete Becker wrote:
    >>>> remove_if doesn't actually remove things, it just reshuffles the
    >>>> sequence so that the rejected elements are at the end.
    >>> The Standard doesn't specify that 'rejected' elements can be found at
    >>> the end of the sequence.

    >>
    >> The algorithm is called "in-place". What besided "reshuffles" can
    >> that mean?

    >
    > Actually, he's right, although it's irrelevant to this particular
    > discussion. remove and remove_if leave whatever junk they fell like at
    > the end of the original sequence. Typically it's the elements that were
    > there before, not necessarily the ones that were rejected. So for the
    > example under discussion, the tail of the array would not hold all 1's
    > unless they were there to begin with. Typically you'd see a vector
    > holding, say, 1,3,1,5,7,1 turning into 3,5,7,5,7,1. The last three
    > elements are the leftovers.
    >


    Forgot to mention: those last two sentences refer to the problem under
    discussion, i.e. removing 1's from the vector.

    Oh, and the "in-place" is in distinction to "copying", which leaves the
    original sequence intact.

    --

    -- Pete
    Roundhouse Consulting, Ltd. (www.versatilecoding.com)
    Author of "The Standard C++ Library Extensions: a Tutorial and
    Reference." (www.petebecker.com/tr1book)
     
    Pete Becker, Apr 11, 2007
    #11
  12. Pete Becker wrote:
    > Pete Becker wrote:
    >> Victor Bazarov wrote:
    >>> Roland Pibinger wrote:
    >>>> On Wed, 11 Apr 2007 11:17:51 -0400, Pete Becker wrote:
    >>>>> remove_if doesn't actually remove things, it just reshuffles the
    >>>>> sequence so that the rejected elements are at the end.
    >>>> The Standard doesn't specify that 'rejected' elements can be found
    >>>> at the end of the sequence.
    >>>
    >>> The algorithm is called "in-place". What besided "reshuffles" can
    >>> that mean?

    >>
    >> Actually, he's right, although it's irrelevant to this particular
    >> discussion. remove and remove_if leave whatever junk they fell like
    >> at the end of the original sequence. Typically it's the elements
    >> that were there before, not necessarily the ones that were rejected.
    >> So for the example under discussion, the tail of the array would not
    >> hold all 1's unless they were there to begin with. Typically you'd
    >> see a vector holding, say, 1,3,1,5,7,1 turning into 3,5,7,5,7,1. The
    >> last three elements are the leftovers.
    >>

    >
    > Forgot to mention: those last two sentences refer to the problem under
    > discussion, i.e. removing 1's from the vector.
    >
    > Oh, and the "in-place" is in distinction to "copying", which leaves
    > the original sequence intact.


    So, I was wrong.

    To be entirely correct, instead of extracting the "left-overs" after
    'remove_if', I ought to use 'copy_if' along with 'erase'. Except there
    is no 'copy_if', is there?

    So, there is no decent way.

    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, Apr 11, 2007
    #12
  13. red floyd Guest

    Victor Bazarov wrote:
    > To be entirely correct, instead of extracting the "left-overs" after
    > 'remove_if', I ought to use 'copy_if' along with 'erase'. Except there
    > is no 'copy_if', is there?
    >


    You could use remove_copy_if with a negated predicate. remove_copy_if
    will copy a range, removing those that match the predicate. So if you
    negate the predicate, you will copy only those that do match the
    original predicate.

    Anyone know if C++0x is going to have copy_if?
     
    red floyd, Apr 11, 2007
    #13
  14. Pete Becker Guest

    Victor Bazarov wrote:
    >
    > To be entirely correct, instead of extracting the "left-overs" after
    > 'remove_if', I ought to use 'copy_if' along with 'erase'. Except there
    > is no 'copy_if', is there?
    >
    > So, there is no decent way.
    >


    No, what you had was basically right. remove or remove_if, followed by
    erase to kill off the leftovers. So remove(begin(), end(), 1) turns
    1,3,1,5,7,1 into 3,5,7,x,x,x (where the x's are unspecified, but most
    likely are 5,7,1) and returns an iterator pointing to the first x.
    erase(iterator, end()) removes the junk at the end.

    --

    -- Pete
    Roundhouse Consulting, Ltd. (www.versatilecoding.com)
    Author of "The Standard C++ Library Extensions: a Tutorial and
    Reference." (www.petebecker.com/tr1book)
     
    Pete Becker, Apr 12, 2007
    #14
  15. Pete Becker wrote:
    > Victor Bazarov wrote:
    >>
    >> To be entirely correct, instead of extracting the "left-overs" after
    >> 'remove_if', I ought to use 'copy_if' along with 'erase'. Except
    >> there is no 'copy_if', is there?
    >>
    >> So, there is no decent way.
    >>

    >
    > No, what you had was basically right. remove or remove_if, followed by
    > erase to kill off the leftovers. So remove(begin(), end(), 1) turns
    > 1,3,1,5,7,1 into 3,5,7,x,x,x (where the x's are unspecified, but most
    > likely are 5,7,1) and returns an iterator pointing to the first x.
    > erase(iterator, end()) removes the junk at the end.


    Right. I know. The OP also wanted to extract the removed elements
    into a separate vector. That's where 'copy_if' would come handy.

    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, Apr 12, 2007
    #15
  16. Pete Becker Guest

    Victor Bazarov wrote:
    > Pete Becker wrote:
    >> Victor Bazarov wrote:
    >>> To be entirely correct, instead of extracting the "left-overs" after
    >>> 'remove_if', I ought to use 'copy_if' along with 'erase'. Except
    >>> there is no 'copy_if', is there?
    >>>
    >>> So, there is no decent way.
    >>>

    >> No, what you had was basically right. remove or remove_if, followed by
    >> erase to kill off the leftovers. So remove(begin(), end(), 1) turns
    >> 1,3,1,5,7,1 into 3,5,7,x,x,x (where the x's are unspecified, but most
    >> likely are 5,7,1) and returns an iterator pointing to the first x.
    >> erase(iterator, end()) removes the junk at the end.

    >
    > Right. I know. The OP also wanted to extract the removed elements
    > into a separate vector. That's where 'copy_if' would come handy.
    >


    Okay, I see what you're saying.

    --

    -- Pete
    Roundhouse Consulting, Ltd. (www.versatilecoding.com)
    Author of "The Standard C++ Library Extensions: a Tutorial and
    Reference." (www.petebecker.com/tr1book)
     
    Pete Becker, Apr 12, 2007
    #16
  17. James Kanze Guest

    On Apr 11, 4:50 pm, "" <> wrote:
    > What is the typical way to loop through a vector while deleting
    > certain elements during the loop process? The code below works, but I
    > am wondering if there is a better solution.


    > vector<int> vTmp;
    > vTmp.push_back(1);
    > vTmp.push_back(2);
    > vTmp.push_back(1);
    > vTmp.push_back(2);
    > vTmp.push_back(1);
    > vTmp.push_back(1);


    > for(int x=0; x<vTmp.size(); x++)
    > {
    > if(vTmp[x]==1)
    > {
    > vTmp.erase(vTmp.begin()+x,vTmp.begin()+x+1);
    > x--; //to account for new size
    > }
    > }


    Others have pointed out the solution using remove or remove_if,
    which handles this specific case. More generally, if you're
    possibly doing a number of other things, or for some other
    reason prefer writing the loop yourself:

    std::vector<int>::iterator current = v.begin() ;
    while ( current != v.end() ) {
    // ...
    if ( shouldBeDeleted ) {
    current = v.erase( current ) ;
    } else {
    ++ current ;
    }
    }

    can be used. (Note that in the case of vector, this is likely
    to result in a lot more copying than using std::remove. If the
    container is a list, however, it's probably more efficient. And
    of course, unless the container is very big, and the types
    expensive to copy, it generally doesn't matter.)

    --
    James Kanze (GABI Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
     
    James Kanze, Apr 12, 2007
    #17
    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. da_rod_father
    Replies:
    3
    Views:
    6,765
    Hal Rosser
    Mar 18, 2006
  2. Replies:
    8
    Views:
    1,940
    Csaba
    Feb 18, 2006
  3. Replies:
    7
    Views:
    575
    Richard Herring
    Jun 13, 2006
  4. THTB
    Replies:
    0
    Views:
    197
  5. dkmd_nielsen
    Replies:
    5
    Views:
    158
    dkmd_nielsen
    Mar 8, 2007
Loading...

Share This Page