Deleting items from std::map in a loop

Discussion in 'C++' started by NFish, Nov 6, 2003.

  1. NFish

    NFish Guest

    Tim Conkling wrote:

    > Ok, so if I want to selectively delete items from a sequence like a
    > deque or vector from a for loop, I have to do something like this:
    >
    > for(iter = list.begin(); iter != list.end(); ++iter)
    > {
    > if(shouldDelete(*iter))
    > {
    > iter = list.erase(iter);
    > --iter;
    > }
    > }
    >
    > I'm trying to accomplish the same sort of thing in a map traversal.
    > Map's implementation of erase() doesn't return an iterator. How do I
    > accomplish what I'm trying to do?
    >
    > Thanks,
    > Tim
    >


    How about remove_if() ?
     
    NFish, Nov 6, 2003
    #1
    1. Advertising

  2. NFish

    Tim Conkling Guest

    Ok, so if I want to selectively delete items from a sequence like a
    deque or vector from a for loop, I have to do something like this:

    for(iter = list.begin(); iter != list.end(); ++iter)
    {
    if(shouldDelete(*iter))
    {
    iter = list.erase(iter);
    --iter;
    }
    }

    I'm trying to accomplish the same sort of thing in a map traversal.
    Map's implementation of erase() doesn't return an iterator. How do I
    accomplish what I'm trying to do?

    Thanks,
    Tim
     
    Tim Conkling, Nov 6, 2003
    #2
    1. Advertising

  3. Tim Conkling wrote in news:bocpuq$ji2$:

    > Ok, so if I want to selectively delete items from a sequence like a
    > deque or vector from a for loop, I have to do something like this:
    >
    > for(iter = list.begin(); iter != list.end(); ++iter)
    > {
    > if(shouldDelete(*iter))
    > {
    > iter = list.erase(iter);
    > --iter;
    > }
    > }
    >
    > I'm trying to accomplish the same sort of thing in a map traversal.
    > Map's implementation of erase() doesn't return an iterator. How do I
    > accomplish what I'm trying to do?
    >


    cont_type::iterator iter = cont.begin(), lim = cont.end();
    while ( iter != lim )
    {
    if( shouldDelete(*iter))
    {
    list.erase( iter++ );
    }
    else ++iter;
    }

    It should work for any container, even ones where you can't
    do --cont.end().

    Rob.
    --
    http://www.victim-prime.dsl.pipex.com/
     
    Rob Williscroft, Nov 6, 2003
    #3
  4. NFish

    tom_usenet Guest

    On Thu, 06 Nov 2003 06:44:55 GMT, NFish <> wrote:

    >Tim Conkling wrote:
    >
    >> Ok, so if I want to selectively delete items from a sequence like a
    >> deque or vector from a for loop, I have to do something like this:
    >>
    >> for(iter = list.begin(); iter != list.end(); ++iter)
    >> {
    >> if(shouldDelete(*iter))
    >> {
    >> iter = list.erase(iter);
    >> --iter;
    >> }
    >> }
    >>
    >> I'm trying to accomplish the same sort of thing in a map traversal.
    >> Map's implementation of erase() doesn't return an iterator. How do I
    >> accomplish what I'm trying to do?
    >>
    >> Thanks,
    >> Tim
    >>

    >
    >How about remove_if() ?


    Mutating algorithms don't work on set or map, that have const value
    types.

    Tom
     
    tom_usenet, Nov 6, 2003
    #4
  5. "Tim Conkling" <> wrote in message
    news:bocpuq$ji2$...
    | Ok, so if I want to selectively delete items from a sequence like a
    | deque or vector from a for loop, I have to do something like this:
    |
    | for(iter = list.begin(); iter != list.end(); ++iter)
    | {
    | if(shouldDelete(*iter))
    | {
    | iter = list.erase(iter);
    | --iter;
    | }
    | }

    Yes, but for std::deque and std::vector at least, it would be
    much more efficient to use the std::remove_if algorithm:
    list.erase( remove_if( list.begin(), list.end(), &shouldDelete )
    , list.end() );

    | I'm trying to accomplish the same sort of thing in a map traversal.
    | Map's implementation of erase() doesn't return an iterator. How do I
    | accomplish what I'm trying to do?

    For information, see:
    http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-closed.html#130
    So this is a debated issue. Note that some implementations of
    map::erase do return an interator. But it is quite easy to
    work around this limitation: just use the postfix ++ operator.

    The following will do:

    for(iter = map.begin() ; iter != map.end() ; )
    {
    if(shouldDelete(*iter))
    map.erase( iter++ );
    else
    ++iter;
    }

    The map.erase( iter++ ) line is equivalent to:
    {
    IterType kill = iter;
    ++iter;
    map.erase(kill);
    }
    (the 1-line form works because the postfix++ operator
    modifies the iter variable and returns its previous
    value *prior* to the call of the erase function ).

    I hope this helps,
    Ivan
    --
    http://ivan.vecerina.com
     
    Ivan Vecerina, Nov 6, 2003
    #5
  6. In article <boe0h1$hc0$>,
    "Ivan Vecerina" <> wrote:

    > For information, see:
    > http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-closed.html#130
    > So this is a debated issue. Note that some implementations of
    > map::erase do return an interator.


    Fwiw, lwg #130 has now been reopened. See especially the note:

    > A future standard may wish to reconsider this issue.


    "The future is now" is the current feeling in the lwg.

    -Howard
     
    Howard Hinnant, Nov 6, 2003
    #6
  7. Tim Conkling wrote:

    > Ok, so if I want to selectively delete items from a sequence like a
    > deque or vector from a for loop, I have to do something like this:
    >
    > for(iter = list.begin(); iter != list.end(); ++iter)
    > {
    > if(shouldDelete(*iter))
    > {
    > iter = list.erase(iter);
    > --iter;
    > }
    > }


    Now, think what's going to happen if 'shouldDelete' returns 'true' for
    the very first element of the sequence...

    The better way to do it would be

    for(iter = list.begin(); iter != list.end();)
    if(shouldDelete(*iter))
    iter = list.erase(iter);
    else
    ++iter;

    or simply

    list.erase(std::remove_if(list.begin(), list.end(), shouldDelete),
    list_end());

    These two techniques are also applicable to 'std::vector'.

    > I'm trying to accomplish the same sort of thing in a map traversal.
    > Map's implementation of erase() doesn't return an iterator. How do I
    > accomplish what I'm trying to do?


    The truth is that 'erase' in associative containers doesn't invalidate
    any iterators except those that point to elements being erased (that's
    also true for 'sid::list'). For this reason, you don't really need
    'map::erase' to return an iterator. Just do this

    for(iter = map.begin(); iter != map.end();)
    if(shouldDelete(*iter))
    map.erase(iter++);
    else
    ++iter;

    This will also work for 'std::list', but won't work for 'std::vector'.

    --
    Best regards,
    Andrey Tarasevich
     
    Andrey Tarasevich, Nov 7, 2003
    #7
    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. Peter Jansson
    Replies:
    5
    Views:
    6,359
    Ivan Vecerina
    Mar 17, 2005
  2. Replies:
    1
    Views:
    436
    red floyd
    Dec 21, 2008
  3. Thomas J. Gritzan
    Replies:
    6
    Views:
    1,034
    James Kanze
    Dec 22, 2008
  4. James Kanze
    Replies:
    0
    Views:
    2,034
    James Kanze
    Dec 21, 2008
  5. Isaac Won
    Replies:
    9
    Views:
    407
    Ulrich Eckhardt
    Mar 4, 2013
Loading...

Share This Page