STL std::map erase

Discussion in 'C++' started by Pieter Thysebaert, May 13, 2004.

  1. Hello,

    I've got a question conerning erasing key-value pairs from a std::map while
    iterating over it.

    According to the STL docs, erasing an element in a map invalidates all
    iterators pointing to that element

    so

    for (map<...>::iterator i = mymap.begin(); i != mymap.end(); i++) {
    if (test(i)) {
    mymap.erase(i);
    mymap.insert(newelement);
    }
    }

    looks like bad practice, and it does crash when it gets executed, at least
    on one machine i've run such code on.

    So my question is, how do I conveniently erase the "current" element in a
    map on the fly while I'm iterating over it? (I admit that this sounds as
    weird in English as it sounds in C++)?

    Thanx,

    Pieter
     
    Pieter Thysebaert, May 13, 2004
    #1
    1. Advertising

  2. Pieter Thysebaert wrote:
    >
    > Hello,
    >
    > I've got a question conerning erasing key-value pairs from a std::map while
    > iterating over it.
    >
    > According to the STL docs, erasing an element in a map invalidates all
    > iterators pointing to that element
    >
    > so
    >
    > for (map<...>::iterator i = mymap.begin(); i != mymap.end(); i++) {
    > if (test(i)) {
    > mymap.erase(i);
    > mymap.insert(newelement);
    > }
    > }
    >
    > looks like bad practice, and it does crash when it gets executed, at least
    > on one machine i've run such code on.
    >
    > So my question is, how do I conveniently erase the "current" element in a
    > map on the fly while I'm iterating over it? (I admit that this sounds as
    > weird in English as it sounds in C++)?


    So what is the real problem?
    The problem is, that after erasing the element with iterator i, you need
    that iterator again, for the increment, to get at the next map element.
    As you know this is not valid. So a possible solution is: get your hands
    at an iterator for the next element, *before* you do the erase.

    --
    Karl Heinz Buchegger
     
    Karl Heinz Buchegger, May 13, 2004
    #2
    1. Advertising

  3. "Pieter Thysebaert" <> wrote in
    message news:c8010s$a5l$...
    >
    >
    > Hello,
    >
    > I've got a question conerning erasing key-value pairs from a std::map

    while
    > iterating over it.
    >
    > According to the STL docs, erasing an element in a map invalidates all
    > iterators pointing to that element
    >
    > so
    >
    > for (map<...>::iterator i = mymap.begin(); i != mymap.end(); i++) {
    > if (test(i)) {
    > mymap.erase(i);
    > mymap.insert(newelement);
    > }
    > }
    >
    > looks like bad practice, and it does crash when it gets executed, at least
    > on one machine i've run such code on.
    >
    > So my question is, how do I conveniently erase the "current" element in a
    > map on the fly while I'm iterating over it? (I admit that this sounds as
    > weird in English as it sounds in C++)?


    for (map<...>::iterator i = mymap.begin(); i != mymap.end(); ) {
    if (test(i)) {
    mymap.erase(i++);
    mymap.insert(newelement);
    } else {
    ++i;
    }
    }

    Understanding this code requires a proper understanding of how 'i++' works.

    john
     
    John Harrison, May 13, 2004
    #3
  4. Pieter Thysebaert

    Howard Guest

    "John Harrison" <> wrote in message
    news:2ghjh6F2s3b7U1@uni-> >
    > > So my question is, how do I conveniently erase the "current" element in

    a
    > > map on the fly while I'm iterating over it? (I admit that this sounds as
    > > weird in English as it sounds in C++)?

    >
    > for (map<...>::iterator i = mymap.begin(); i != mymap.end(); ) {
    > if (test(i)) {
    > mymap.erase(i++);
    > mymap.insert(newelement);
    > } else {
    > ++i;
    > }
    > }
    >
    > Understanding this code requires a proper understanding of how 'i++'

    works.

    Ok...so how about an explanation?

    I don't see how this is any different. When the call to erase finishes, all
    iterators pointing to that element are no longer valid. And isn't an
    implementation allowed to wait until the erase call returns, and then
    perform that increment? In that case, i cannot be incremented because it is
    invalid already, right? For such an implementation, incrementing i in the
    function parameter ought to be the same as incrementing it in the for
    statement, as far as I can see.

    Can't an implementation create identical code for both these cases?...

    foo(i++);

    vs.

    f(i);
    i++;

    I could see that the implementation might not be *required* to make those
    the same, but would it not be *allowed* to make them the same?

    What am I missing here?

    -Howard
     
    Howard, May 13, 2004
    #4
  5. "Howard" <> wrote in message
    news:7cNoc.51315$...
    >
    > "John Harrison" <> wrote in message
    > news:2ghjh6F2s3b7U1@uni-> >
    > > > So my question is, how do I conveniently erase the "current" element

    in
    > a
    > > > map on the fly while I'm iterating over it? (I admit that this sounds

    as
    > > > weird in English as it sounds in C++)?

    > >
    > > for (map<...>::iterator i = mymap.begin(); i != mymap.end(); ) {
    > > if (test(i)) {
    > > mymap.erase(i++);
    > > mymap.insert(newelement);
    > > } else {
    > > ++i;
    > > }
    > > }
    > >
    > > Understanding this code requires a proper understanding of how 'i++'

    > works.
    >
    > Ok...so how about an explanation?
    >
    > I don't see how this is any different. When the call to erase finishes,

    all
    > iterators pointing to that element are no longer valid. And isn't an
    > implementation allowed to wait until the erase call returns, and then
    > perform that increment?


    No, that's exactly the point. i++ is a function call, and that function must
    happen before the call to erase. The function call returns the 'old' value
    of the iterator (that gets passed to erase), and increments the iterator to
    its 'new' value as a side effect. All this must happen before erase is
    called.

    john
     
    John Harrison, May 13, 2004
    #5
  6. Pieter Thysebaert

    Howard Guest

    "John Harrison" <> wrote in message
    news:...
    >
    > "Howard" <> wrote in message
    > news:7cNoc.51315$...
    > >
    > > "John Harrison" <> wrote in message
    > > news:2ghjh6F2s3b7U1@uni-> >
    > > > > So my question is, how do I conveniently erase the "current" element

    > in
    > > a
    > > > > map on the fly while I'm iterating over it? (I admit that this

    sounds
    > as
    > > > > weird in English as it sounds in C++)?
    > > >
    > > > for (map<...>::iterator i = mymap.begin(); i != mymap.end(); ) {
    > > > if (test(i)) {
    > > > mymap.erase(i++);
    > > > mymap.insert(newelement);
    > > > } else {
    > > > ++i;
    > > > }
    > > > }
    > > >
    > > > Understanding this code requires a proper understanding of how 'i++'

    > > works.
    > >
    > > Ok...so how about an explanation?
    > >
    > > I don't see how this is any different. When the call to erase finishes,

    > all
    > > iterators pointing to that element are no longer valid. And isn't an
    > > implementation allowed to wait until the erase call returns, and then
    > > perform that increment?

    >
    > No, that's exactly the point. i++ is a function call, and that function

    must
    > happen before the call to erase. The function call returns the 'old' value
    > of the iterator (that gets passed to erase), and increments the iterator

    to
    > its 'new' value as a side effect. All this must happen before erase is
    > called.
    >
    > john


    Ahah! I understand now. Somehow I keep forgetting that ++ is actually a
    function call (operator ++()). Thanks for the explanation.

    -Howard



    >
    >
     
    Howard, May 13, 2004
    #6
  7. John Harrison wrote:
    >
    >
    > No, that's exactly the point. i++ is a function call, and that function must
    > happen before the call to erase.


    Ahm.
    Thats the wrong explanation.
    The correct explanation is:
    There is a sequence point immediatly after all arguments
    to functions have been evaluated and just before the
    function gets called.

    So the compiler has no other choice: If there are side
    effects during the evaluation of arguments, those side
    effects have to be completed before the function gets
    called.

    That i++ in case of iterators is implemented as a function is
    an implementation detail.

    --
    Karl Heinz Buchegger
     
    Karl Heinz Buchegger, May 13, 2004
    #7
  8. Howard wrote:
    >
    >
    > Ahah! I understand now. Somehow I keep forgetting that ++ is actually a
    > function call (operator ++()).


    It doens't matter.
    Even if it were not, the increment has to happen before the
    function actually gets called.


    --
    Karl Heinz Buchegger
     
    Karl Heinz Buchegger, May 13, 2004
    #8
  9. "Karl Heinz Buchegger" <> wrote in message
    news:...
    > John Harrison wrote:
    > >
    > >
    > > No, that's exactly the point. i++ is a function call, and that function

    must
    > > happen before the call to erase.

    >
    > Ahm.
    > Thats the wrong explanation.
    > The correct explanation is:
    > There is a sequence point immediatly after all arguments
    > to functions have been evaluated and just before the
    > function gets called.
    >
    > So the compiler has no other choice: If there are side
    > effects during the evaluation of arguments, those side
    > effects have to be completed before the function gets
    > called.
    >
    > That i++ in case of iterators is implemented as a function is
    > an implementation detail.
    >



    I wasn't completely sure if the same rules applied to ++ on a built in type,
    fairly sure but not completely sure. So I tried to avoid saying 'its because
    its a function call' and just gave a descriptive answer.

    Thanks for the clarification.

    john
     
    John Harrison, May 13, 2004
    #9
  10. John Harrison wrote:
    >
    > "Karl Heinz Buchegger" <> wrote in message
    > news:...
    > > John Harrison wrote:
    > > >
    > > >
    > > > No, that's exactly the point. i++ is a function call, and that function

    > must
    > > > happen before the call to erase.

    > >
    > > Ahm.
    > > Thats the wrong explanation.
    > > The correct explanation is:
    > > There is a sequence point immediatly after all arguments
    > > to functions have been evaluated and just before the
    > > function gets called.
    > >
    > > So the compiler has no other choice: If there are side
    > > effects during the evaluation of arguments, those side
    > > effects have to be completed before the function gets
    > > called.
    > >
    > > That i++ in case of iterators is implemented as a function is
    > > an implementation detail.
    > >

    >
    > I wasn't completely sure if the same rules applied to ++ on a built in type,


    The ++ has nothing to do with it other then generating a side effect.

    --
    Karl Heinz Buchegger
     
    Karl Heinz Buchegger, May 13, 2004
    #10
  11. Pieter Thysebaert

    Howard Guest

    "Karl Heinz Buchegger" <> wrote in message
    news:...
    > John Harrison wrote:
    > >
    > > "Karl Heinz Buchegger" <> wrote in message
    > > news:...
    > > > John Harrison wrote:
    > > > >
    > > > >
    > > > > No, that's exactly the point. i++ is a function call, and that

    function
    > > must
    > > > > happen before the call to erase.
    > > >
    > > > Ahm.
    > > > Thats the wrong explanation.
    > > > The correct explanation is:
    > > > There is a sequence point immediatly after all arguments
    > > > to functions have been evaluated and just before the
    > > > function gets called.
    > > >
    > > > So the compiler has no other choice: If there are side
    > > > effects during the evaluation of arguments, those side
    > > > effects have to be completed before the function gets
    > > > called.
    > > >
    > > > That i++ in case of iterators is implemented as a function is
    > > > an implementation detail.
    > > >

    > >
    > > I wasn't completely sure if the same rules applied to ++ on a built in

    type,
    >
    > The ++ has nothing to do with it other then generating a side effect.
    >
    > --
    > Karl Heinz Buchegger
    >



    So even if i were an int, it would still have to be incremented prior to
    calling the function? That sure seems counter-intuitive to the notion of
    "post-increment". Makes sense though, I guess.

    Also, I guess that means that what is actually passed to the function is a
    *copy* of the original iterator, since the original already has to point to
    the next item, right?

    This is very enlightening. It seems that I always have more to learn with
    this language. Thanks...

    -Howard
     
    Howard, May 13, 2004
    #11
  12. Howard wrote:
    > ...
    > So even if i were an int, it would still have to be incremented prior to
    > calling the function?


    Yes.

    > That sure seems counter-intuitive to the notion of
    > "post-increment". Makes sense though, I guess.


    The function will still receive the original value of 'i'. That's why it
    is called "post-increment".

    > Also, I guess that means that what is actually passed to the function is a
    > *copy* of the original iterator, since the original already has to point to
    > the next item, right?


    Since this function receives its parameter "by value" - yes, it actually
    receives a copy of the original iterator.

    --
    Best regards,
    Andrey Tarasevich
     
    Andrey Tarasevich, May 13, 2004
    #12
  13. Pieter Thysebaert

    Howard Guest

    "Andrey Tarasevich" <> wrote in message
    news:...
    > Howard wrote:
    > > ...
    > > So even if i were an int, it would still have to be incremented prior to
    > > calling the function?

    >
    > Yes.
    >
    > > That sure seems counter-intuitive to the notion of
    > > "post-increment". Makes sense though, I guess.

    >
    > The function will still receive the original value of 'i'. That's why it
    > is called "post-increment".
    >
    > > Also, I guess that means that what is actually passed to the function is

    a
    > > *copy* of the original iterator, since the original already has to point

    to
    > > the next item, right?

    >
    > Since this function receives its parameter "by value" - yes, it actually
    > receives a copy of the original iterator.
    >


    Ok...but then, what if you were to pass the iterator *by reference* to some
    function instead? What value would the function then get, (considering the
    previously stated rule that the increment side-effect has to be completed
    prior to the calling of the function)? Would a temporary (un-incremented)
    copy be created, passed by reference, and then that copy destroyed after the
    return of the function? (That seems to be the only way to maintain the
    concept of post-increment without violating the side-effect rule.)

    -Howard
     
    Howard, May 13, 2004
    #13
  14. Howard wrote:

    >> Since this function receives its parameter "by value" - yes, it actually
    >> receives a copy of the original iterator.

    >
    > Ok...but then, what if you were to pass the iterator *by reference* to
    > some
    > function instead? What value would the function then get, (considering
    > the previously stated rule that the increment side-effect has to be
    > completed
    > prior to the calling of the function)? Would a temporary (un-incremented)
    > copy be created, passed by reference, and then that copy destroyed after
    > the
    > return of the function? (That seems to be the only way to maintain the
    > concept of post-increment without violating the side-effect rule.)


    That depends on how the iterator implements the pre and post ++ operators.
    Habitually the post version returns a copy of the old value.

    --
    Salu2
     
    =?ISO-8859-15?Q?Juli=E1n?= Albo, May 13, 2004
    #14
  15. Pieter Thysebaert wrote:
    >
    > Hello,


    > According to the STL docs, erasing an element in a map invalidates all
    > iterators pointing to that element
    >
    > so
    >
    > for (map<...>::iterator i = mymap.begin(); i != mymap.end(); i++) {
    > if (test(i)) {
    > mymap.erase(i);
    > mymap.insert(newelement);
    > }
    > }


    Why not the following?

    for (map<...>::iterator i = mymap.begin(); i != mymap.end(); i++) {
    if (test(i)) {
    i = mymap.erase(i);
    }
    }
     
    joey tribbiani, May 13, 2004
    #15
  16. Pieter Thysebaert

    Pete Becker Guest

    joey tribbiani wrote:
    >
    > Why not the following?
    >
    > for (map<...>::iterator i = mymap.begin(); i != mymap.end(); i++) {
    > if (test(i)) {
    > i = mymap.erase(i);
    > }
    > }


    Because map::erase returns void according to the standard. Our
    implementation returns an iterator, just like vector::erase. The next
    version of the standard will probably make that change official.

    --

    Pete Becker
    Dinkumware, Ltd. (http://www.dinkumware.com)
     
    Pete Becker, May 13, 2004
    #16
  17. Pieter Thysebaert

    Jeff Flinn Guest

    "Pete Becker" <> wrote in message
    news:...
    > joey tribbiani wrote:
    > >
    > > Why not the following?
    > >
    > > for (map<...>::iterator i = mymap.begin(); i != mymap.end(); i++) {
    > > if (test(i)) {
    > > i = mymap.erase(i);
    > > }
    > > }

    >
    > Because map::erase returns void according to the standard. Our
    > implementation returns an iterator, just like vector::erase. The next
    > version of the standard will probably make that change official.


    Even with this extension/future std, the above is incorrect. 'i' will be
    effectively incremented twice for each true 'test(i)'. 'i++' needs to be
    moved from the for statement to an else clause.

    Jeff F
     
    Jeff Flinn, May 13, 2004
    #17
  18. Pete Becker wrote:

    > joey tribbiani wrote:
    >
    >>Why not the following?
    >>
    >>for (map<...>::iterator i = mymap.begin(); i != mymap.end(); i++) {
    >> if (test(i)) {
    >> i = mymap.erase(i);
    >> }
    >>}

    >
    >
    > Because map::erase returns void according to the standard. Our
    > implementation returns an iterator, just like vector::erase. The next
    > version of the standard will probably make that change official.
    >

    Oh, thanks, i didn't know - always thought you are the standard
    (actually, never really thought about it)
     
    joey tribbiani, May 13, 2004
    #18
  19. Pieter Thysebaert

    Howard Guest

    "Pete Becker" <> wrote in message
    news:...
    > joey tribbiani wrote:
    > >
    > > Why not the following?
    > >
    > > for (map<...>::iterator i = mymap.begin(); i != mymap.end(); i++) {
    > > if (test(i)) {
    > > i = mymap.erase(i);
    > > }
    > > }

    >
    > Because map::erase returns void according to the standard. Our
    > implementation returns an iterator, just like vector::erase. The next
    > version of the standard will probably make that change official.
    >


    Even if it *did* return an iterator, the above code would only work if it
    returned an iterator to the *previous* item, because the for loop is going
    to increment i every time. The implementation I'm using returns an iterator
    to the *next* item (or to end(), if there are none beyond the given item).
    In that case, it would have to be writtien:

    for (map<...>::iterator i = mymap.begin(); i != mymap.end(); )
    {
    if (test(i))
    i = mymap.erase(i);
    else
    i++;
    }

    -Howard
     
    Howard, May 13, 2004
    #19
  20. Pieter Thysebaert

    Pete Becker Guest

    Jeff Flinn wrote:
    >
    > "Pete Becker" <> wrote in message
    > news:...
    > > joey tribbiani wrote:
    > > >
    > > > Why not the following?
    > > >
    > > > for (map<...>::iterator i = mymap.begin(); i != mymap.end(); i++) {
    > > > if (test(i)) {
    > > > i = mymap.erase(i);
    > > > }
    > > > }

    > >
    > > Because map::erase returns void according to the standard. Our
    > > implementation returns an iterator, just like vector::erase. The next
    > > version of the standard will probably make that change official.

    >
    > Even with this extension/future std, the above is incorrect. 'i' will be
    > effectively incremented twice for each true 'test(i)'. 'i++' needs to be
    > moved from the for statement to an else clause.
    >


    So tell the person who posted it.

    --

    Pete Becker
    Dinkumware, Ltd. (http://www.dinkumware.com)
     
    Pete Becker, May 13, 2004
    #20
    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. Angus Leeming
    Replies:
    5
    Views:
    2,928
    Howard Hinnant
    Feb 4, 2004
  2. Gernot Frisch

    std::map - erase+continue

    Gernot Frisch, Mar 7, 2005, in forum: C++
    Replies:
    17
    Views:
    2,909
    Andre Kostur
    Mar 9, 2005
  3. Marcin Kaliciñski

    Return value of std::map::erase()

    Marcin Kaliciñski, Mar 10, 2005, in forum: C++
    Replies:
    1
    Views:
    487
    Chris Jefferson
    Mar 10, 2005
  4. erase vs. erase

    , Mar 25, 2006, in forum: C++
    Replies:
    7
    Views:
    369
    Pete Becker
    Mar 30, 2006
  5. Replies:
    8
    Views:
    636
Loading...

Share This Page