vector.erase() ?

Discussion in 'C++' started by BCC, Jan 21, 2004.

  1. BCC

    BCC Guest

    I have the following code, where good_list is a vector of CUnits:

    int high_cutoff = 10;
    vector<CUnit>::iterator it;
    for (it = good_list.end(); it != good_list.begin(); --it) {
    CUnit* ccu = it;
    if (ccu->GetCutoff() >= high_cutoff) {
    good_list.erase(it);
    }
    }

    Doesn't give any errors, but also does not seem to be removing the element
    correctly from good_list.

    There something wrong with the above code?

    Thanks
     
    BCC, Jan 21, 2004
    #1
    1. Advertising

  2. BCC wrote:

    > I have the following code, where good_list is a vector of CUnits:
    >
    > int high_cutoff = 10;
    > vector<CUnit>::iterator it;
    > for (it = good_list.end(); it != good_list.begin(); --it) {


    Note that good_list.end() is an iterator that you can't do much with.
    Dereferencing it is an error. If you really need to go backwards, you
    probably want to use reverse iterators instead.

    > CUnit* ccu = it;


    This may be an invalid conversion. An implementation may or may not
    implement vector iterators as plain pointers. There's not really any
    reason to need a pointer when you've already got an iterator. Just use
    the iterator.

    > if (ccu->GetCutoff() >= high_cutoff) {


    One problem is that ccu isn't valid the first time through.

    > good_list.erase(it);


    'it' is no longer valid after this. I don't know if you are allowed to
    apply -- to it. I don't think this is your problem, but you should
    probably do something like this:

    for (/* init */; /* cond */; /* EMPTY! */)
    if (/* condition */)
    it = good_list.erase(it);
    else
    ++it;

    I'm using ++ instead of --, figuring that you'll want to use reverse
    iterators.

    > }
    > }
    >
    > Doesn't give any errors, but also does not seem to be removing the element
    > correctly from good_list.
    >
    > There something wrong with the above code?


    Yup.

    Here's the entire replacement I'd recommend (untested):

    int high_cutoff = 10;
    vector<CUnit>::reverse_iterator it;
    for (it = good_list.rbegin(); it != good_list.rend(); ) {
    if (it->GetCutoff() >= high_cutoff) {
    it = good_list.erase(it);
    }
    else {
    ++it;
    }
    }

    -Kevin
    --
    My email address is valid, but changes periodically.
    To contact me please use the address from a recent posting.
     
    Kevin Goodsell, Jan 21, 2004
    #2
    1. Advertising

  3. BCC

    BCC Guest

    >
    > Here's the entire replacement I'd recommend (untested):
    >
    > int high_cutoff = 10;
    > vector<CUnit>::reverse_iterator it;
    > for (it = good_list.rbegin(); it != good_list.rend(); ) {
    > if (it->GetCutoff() >= high_cutoff) {
    > it = good_list.erase(it);
    > }
    > else {
    > ++it;
    > }
    > }
    >


    Makes sense.... but one problem is that erase() returns an iterator, not a
    reverse_iterator...

    Ill see if I can iron it out, thanks!
    B
     
    BCC, Jan 21, 2004
    #3
  4. BCC wrote:

    >>Here's the entire replacement I'd recommend (untested):
    >>
    >>int high_cutoff = 10;
    >>vector<CUnit>::reverse_iterator it;
    >>for (it = good_list.rbegin(); it != good_list.rend(); ) {
    >> if (it->GetCutoff() >= high_cutoff) {
    >> it = good_list.erase(it);
    >> }
    >> else {
    >> ++it;
    >> }
    >>}
    >>

    >
    >
    > Makes sense.... but one problem is that erase() returns an iterator, not a
    > reverse_iterator...


    Oh, yeah...

    Well, that was kind of dumb, actually. You don't even *want* the
    iterator returned by erase of you are going backward. Make them forward
    iterators instead - there's no obvious reason to go backward.

    On the other hand, if there *is* a reason that you need to go backward,
    which just isn't apparent to me, then you can do something like this:

    vector<CUnit>::reverse_iterator tmp = it;
    ++tmp;
    good_list.erase(it);
    it = tmp;

    inside the 'if' block.

    Another alternative is to use algorithms. std::remove_if should work, I
    think. But remember that it doesn't really remove anything, it just
    shuffles the "removed" elements to the end for you to erase().

    -Kevin
    --
    My email address is valid, but changes periodically.
    To contact me please use the address from a recent posting.
     
    Kevin Goodsell, Jan 21, 2004
    #4
  5. BCC

    David Fisher Guest

    "Kevin Goodsell" <> wrote:

    > On the other hand, if there *is* a reason that you need to go backward,
    > which just isn't apparent to me, then you can do something like this:
    >
    > vector<CUnit>::reverse_iterator tmp = it;
    > ++tmp;
    > good_list.erase(it);
    > it = tmp;
    >
    > inside the 'if' block.


    You can also say:

    good_list.erase(it++);

    This is safe because the variable "it" is incremented while it is still
    valid; see:

    http://mail.worldforge.org/pipermail/protocols/2001-December/000168.html

    (code near the bottom of the page)

    David F
     
    David Fisher, Jan 21, 2004
    #5
  6. David Fisher wrote:

    > "Kevin Goodsell" <> wrote:
    >
    >
    >>On the other hand, if there *is* a reason that you need to go backward,
    >>which just isn't apparent to me, then you can do something like this:
    >>
    >>vector<CUnit>::reverse_iterator tmp = it;
    >>++tmp;
    >>good_list.erase(it);
    >>it = tmp;
    >>
    >>inside the 'if' block.

    >
    >
    > You can also say:
    >
    > good_list.erase(it++);


    Yeah, if they are reverse iterators. That whole going backwards thing
    got me confused. This method doesn't work if 'it' is a regular (not
    reverse) iterator though, because the erase would invalidate the new
    value of 'it'.

    >
    > This is safe because the variable "it" is incremented while it is still
    > valid; see:
    >
    > http://mail.worldforge.org/pipermail/protocols/2001-December/000168.html
    >
    > (code near the bottom of the page)
    >


    That is a bit different because the container is a std::list. In that
    case, no iterators are invalidated by the erase, so the method you
    showed should be safe whether it's a reverse iterator or not.

    -Kevin
    --
    My email address is valid, but changes periodically.
    To contact me please use the address from a recent posting.
     
    Kevin Goodsell, Jan 21, 2004
    #6
  7. BCC

    David Fisher Guest

    "Kevin Goodsell" <> wrote:

    > David Fisher wrote:
    >> You can also say:
    >>
    >> good_list.erase(it++);

    >
    > Yeah, if they are reverse iterators. That whole going backwards thing
    > got me confused. This method doesn't work if 'it' is a regular (not
    > reverse) iterator though, because the erase would invalidate the new
    > value of 'it'.


    It works in either direction - post increment operators do something like
    this:

    temp = (the next value after x);
    someFunction(x);
    x = temp;

    The increment is not applied to the invalidated iterator, it is applied to
    the original value. It does not do this:

    someFunction(x);
    x = (the next value after x);

    If you write your own post increment operator, you need to return a value
    and not a reference to "this", because of these semantics.

    David F
     
    David Fisher, Jan 21, 2004
    #7
  8. David Fisher wrote:

    > "Kevin Goodsell" <> wrote:
    >
    >
    >>David Fisher wrote:
    >>
    >>>You can also say:
    >>>
    >>>good_list.erase(it++);

    >>
    >>Yeah, if they are reverse iterators. That whole going backwards thing
    >>got me confused. This method doesn't work if 'it' is a regular (not
    >>reverse) iterator though, because the erase would invalidate the new
    >>value of 'it'.

    >
    >
    > It works in either direction - post increment operators do something like
    > this:


    I think you misunderstand. The container in question is a vector.
    erase() on a vector invalidates all iterators to elements that follow
    the erased element(s).

    >
    > temp = (the next value after x);
    > someFunction(x);


    In the specific case we are talking about (where someFunction is the
    vector erase() function, or calls that function), temp becomes invalid
    here...

    > x = temp;


    ....and therefore this is a problem. Maybe. I'm not actually sure what
    the restrictions on invalidated iterators are.

    -Kevin
    --
    My email address is valid, but changes periodically.
    To contact me please use the address from a recent posting.
     
    Kevin Goodsell, Jan 21, 2004
    #8
  9. BCC

    David Fisher Guest

    "Kevin Goodsell" <> wrote:
    > I think you misunderstand. The container in question is a vector.
    > erase() on a vector invalidates all iterators to elements that follow
    > the erased element(s).
    >
    > >
    > > temp = (the next value after x);
    > > someFunction(x);

    >
    > In the specific case we are talking about (where someFunction is the
    > vector erase() function, or calls that function), temp becomes invalid
    > here...
    >
    > > x = temp;

    >
    > ...and therefore this is a problem. Maybe. I'm not actually sure what
    > the restrictions on invalidated iterators are.


    Sorry, I was focusing on the wrong thing (the iterator rather than the
    container) - I think you're probably right.

    David F
     
    David Fisher, Jan 21, 2004
    #9
  10. BCC

    Duane Hebert Guest

    > ...and therefore this is a problem. Maybe. I'm not actually sure what
    > the restrictions on invalidated iterators are.



    This is more of a question than a suggestion but given that it's a vector
    and the reallocation happening on an erase() call, would this be any less
    efficient:

    int high_cutoff = 10;
    vector<CUnit> temp;
    size_t VSize = CUnit.size();
    temp.reserver(VSize());
    for(size_t i = 0; i < VSize; ++i) {
    if(CUnit.GetCutoff() < high_cutoff) temp.push_back(CUnit;
    }
    if(!temp.empty()) CUnit.swap(temp);
     
    Duane Hebert, Jan 23, 2004
    #10
  11. BCC

    ntg

    Joined:
    Jun 17, 2008
    Messages:
    1
    using reverse iterators

    I think this should do the trick in an efficient way...
    its even using the faster ++it....

    int high_cutoff = 10;
    vector<CUnit>::reverse_iterator it;
    for (it = good_list.rbegin(); it != good_list.rend(); ) {
    if (it->GetCutoff() >= high_cutoff) {
    it = good_list.erase(it.base()-1);
    }
    else {
    ++it;
    }
    }

    any thoughts?
     
    ntg, Jun 17, 2008
    #11
    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. mosfet

    STL vector and erase : HELP

    mosfet, Nov 14, 2003, in forum: C++
    Replies:
    2
    Views:
    606
    Ivan Vecerina
    Nov 14, 2003
  2. kaede
    Replies:
    1
    Views:
    427
    Thore Karlsen
    Nov 23, 2003
  3. Replies:
    8
    Views:
    1,932
    Csaba
    Feb 18, 2006
  4. erase vs. erase

    , Mar 25, 2006, in forum: C++
    Replies:
    7
    Views:
    369
    Pete Becker
    Mar 30, 2006
  5. Anil
    Replies:
    5
    Views:
    441
    Jim Langston
    Dec 18, 2007
Loading...

Share This Page