Thread: List Iterators, erase() -- help

  1. #1
    Registered User
    Join Date
    Aug 2010
    Location
    Rochester, NY
    Posts
    196

    List Iterators, erase() -- help

    Hey,

    I was wondering what happened if you erased an object from a list using an iterator, so I tried it, here's my code:

    Code:
    #include <list>
    #include <iostream>
    
    int main()
    {
        std::list<int> myList;
        for (int i = 0 ; i < 10 ; ++i)
            myList.push_back(i);
        
        std::list<int>::iterator iter;
        std::list<int>::iterator it2;
        it2 = myList.begin();
        it2++;
        it2++;
        it2++;
        for (iter = myList.begin() ; iter != myList.end() ; ++iter)
        {
            std::cout << (*iter) << std::endl;
            if ((*iter) == 5)
                myList.erase(it2);
        }
    
        for (iter = myList.begin() ; iter != myList.end() ; ++iter)
            std::cout << *iter << std::endl;
    
    }
    Here's where it gets weird, the part in blue, if that's it2, works fine, if it's "iter", under Solaris, it works fine, under cygwin (g++ 3.4.4) I get this:

    Code:
    $ ./a.exe
    0
    1
    2
    3
    4
    5
    13501152
    1628741068
    1628741060
          1 [main] a 2700 _cygtls::handle_exceptions: Error while dumping state (probably corrupted stack)
    Segmentation fault (core dumped)
    Now obviously the iterator is getting lost, which is why I'm getting some random value for where the 7th index SHOULD be...but my question is, why?

    This code shouldn't create any undefined behavior, should it? Is it just undefined behavior that Solaris is handling differently than Cygwin? Or is Cygwin at fault?

    I've never had issues with Cygwin, which is why I'm a bit concerned. If this is Cygwin's fault it definitely makes me want to try MinGW... Does anybody have any opinions on that, the major difference as I understand is that MinGW converts calls to the Win32 forms, as Cygwin uses its cyg<whatever>.dll to do the conversions, so MinGW doesn't rely on runtime call conversions?

    TIA!
    Last edited by Syndacate; 02-06-2011 at 12:13 AM.

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    The problem is that this line invalidates iter:
    Code:
    myList.erase(iter);
    Consequently, ++iter operates on an invalid iterator, resulting in undefined behaviour. To avoid this, write:
    Code:
    iter = myList.erase(iter);
    With myList.erase(it2) instead, it is it2 that is invalidated, thus ++iter is okay.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Assuming you want to remove any occurrence of 5 from the list, you should either use the "classical" erase-while-iterating pattern,

    Code:
    for (iter = myList.begin() ; iter != myList.end() ; )
        {
            std::cout << (*iter) << std::endl;
            if ((*iter) == 5)
                iter = myList.erase(iter);
            else
                ++iter;
        }
    or use the list's member function:

    Code:
    myList.remove(5);
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  4. #4
    Registered User
    Join Date
    Aug 2010
    Location
    Rochester, NY
    Posts
    196
    Quote Originally Posted by anon View Post
    Assuming you want to remove any occurrence of 5 from the list, you should either use the "classical" erase-while-iterating pattern,

    Code:
    for (iter = myList.begin() ; iter != myList.end() ; )
        {
            std::cout << (*iter) << std::endl;
            if ((*iter) == 5)
                iter = myList.erase(iter);
            else
                ++iter;
        }
    or use the list's member function:

    Code:
    myList.remove(5);
    Hrm, saw erase before I saw remove, but seeing as the issue is there, I would like to figure out the rationale behind it, not just a simpler way of doing it.

    Quote Originally Posted by laserlight View Post
    The problem is that this line invalidates iter:
    Code:
    myList.erase(iter);
    Consequently, ++iter operates on an invalid iterator, resulting in undefined behaviour. To avoid this, write:
    Code:
    iter = myList.erase(iter);
    With myList.erase(it2) instead, it is it2 that is invalidated, thus ++iter is okay.
    Well, yes and no.

    Yes, that makes complete sense...but it doesn't. I mean the concept of an invalid or dangling iterator is the same as that of a pointer, but that really shouldn't be what's going on.

    According to both gotapi.com and cplusplus.com it's supposed to return an iterator to the one after the last one you erased...one would think that that's the same iterator that was modified, but apparently not.

    So I guess in the end it's implementation dependent, as if you're returning the same instance, it has to be valid, but if you're dropping the parameter instance, then it doesn't. It appears cygwin is doing the latter, and Solaris the former. I kind of have to agree with the former method more..you shouldn't have the possibility of an invalid iterator from a function like that...but as I said, it's apparently implementation dependent, nothing in the STL spec, apparently about it. Though setting it equal to the return value should work..but it may not be what I want, going to go try that now..

  5. #5
    Registered User
    Join Date
    Aug 2010
    Location
    Rochester, NY
    Posts
    196
    Right, so that fixes it:

    Code:
    for (iter = myList.begin() ; iter != myList.end() ; ++iter)
    {
         std::cout << (*iter) << std::endl;
         if ((*iter) == 5)
              iter = myList.erase(iter);
    }
    Only problem is that since it returns the one AFTER, you get output like this:
    Code:
    $
    0
    1
    2
    3
    4
    5
    7
    8
    9
    0
    1
    2
    3
    4
    6
    7
    8
    9
    So 6 is skipped. So to balance it out with that of the for loop, you have to do this:

    Code:
    for (iter = myList.begin() ; iter != myList.end() ; ++iter)
    {
         std::cout << (*iter) << std::endl;
         if ((*iter) == 5)
         {
              iter = myList.erase(iter);
              iter--;
         }
    }
    To get desired results:
    Code:
    $
    0
    1
    2
    3
    4
    5
    6
    7
    8
    9
    0
    1
    2
    3
    4
    6
    7
    8
    9
    Arg. That's just annoying...

    EDIT:
    Or this:
    Code:
    for (iter = myList.begin() ; iter != myList.end() ; ++iter)
    {
         std::cout << (*iter) << std::endl;
         if ((*iter) == 5)
              iter = myList.erase(iter)--;
    }
    Bit less retarded I guess...but still pretty bad...
    Last edited by Syndacate; 02-09-2011 at 04:41 PM.

  6. #6
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Both those snippets have a big problem. If you happen to erase the first item in the container, decrementing the result (iterator to the new first item) will make the iterator go out of bounds ("previous" to myList.begin()).

    I've shown the classical way of doing this: only increment the iterator if you don't erase.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by Syndacate View Post
    Code:
    for (iter = myList.begin() ; iter != myList.end() ; ++iter)
    {
         std::cout << (*iter) << std::endl;
         if ((*iter) == 5)
         {
              iter = myList.erase(iter);
              iter--;
         }
    }
    Arg. That's just annoying...

    EDIT:
    Or this:
    Code:
    for (iter = myList.begin() ; iter != myList.end() ; ++iter)
    {
         std::cout << (*iter) << std::endl;
         if ((*iter) == 5)
              iter = myList.erase(iter)--;
    }
    Bit less retarded I guess...but still pretty bad...
    Both of those suggestions are broken, do not try to do that. You must simply remove any iterator incrementing from the last part of the for-loop expression (the ++iter) and only increment if not erasing.
    Otherwise:
    Code:
    iter = myList.erase(iter++);
    Last edited by iMalc; 02-09-2011 at 11:50 PM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  8. #8
    Registered User
    Join Date
    Aug 2010
    Location
    Rochester, NY
    Posts
    196
    Quote Originally Posted by anon View Post
    Both those snippets have a big problem. If you happen to erase the first item in the container, decrementing the result (iterator to the new first item) will make the iterator go out of bounds ("previous" to myList.begin()).

    I've shown the classical way of doing this: only increment the iterator if you don't erase.
    Yeah, that's a good point, they both will become invalid on the first element. The remove() function only lends itself to this particular case, I suppose the remove_if() function would be complimentary as handy for determining when something is to be erased.

    Quote Originally Posted by iMalc View Post
    Both of those suggestions are broken, do not try to do that. You must simply remove any iterator incrementing from the last part of the for-loop expression (the ++iter) and only increment if not erasing.
    Otherwise:
    Code:
    iter = myList.erase(iter++);
    Wouldn't that expression erase element 5, then increment the now possibly invalid iterator, then set the iterator to the element after (6) ? In essence, doing nothing? I'm pretty sure the postfix increment operator has higher precedence than the assignment operator.

    Though regardless, I get the point of what you're doing. I guess remove/remove_if is a better for this type of situation unless you know ahead of time a particular value or range to remove from the list.

    Thanks guys.

  9. #9
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Wouldn't that expression erase element 5, then increment the now possibly invalid iterator, then set the iterator to the element after (6) ? In essence, doing nothing? I'm pretty sure the postfix increment operator has higher precedence than the assignment operator.
    That increment is pointless, since the value assigned to the left-hand side is the result of the function call anyway.

    Perhaps this was meant.

    Code:
    list.erase(iter++);
    This not incrementing an invalid iterator has to do with sequence points: side-effects have to be evaluated before entering the function body.

    BTW, whether this is a right thing to do or not depends on the container. E.g don't try this with a vector.

    If you want to erase elements from the entire list, then remove erases elements with a particular value and remove_if erases elements for which a condition is true. You'll only need a manual loop for a task more complicated, and I don't think there's much new to invent about how that looks.
    Last edited by anon; 02-10-2011 at 06:53 AM.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  10. #10
    The Dragon Reborn
    Join Date
    Nov 2009
    Location
    Dublin, Ireland
    Posts
    629
    since this is going on..i don't still understand why I can't just increment the iterator after erasing it..i really get the point of the else

    if erase returns the element after the element to be deleted in question(in this case 5..so it should return the address that points to 6, right)..in the if statement i should be able to do..

    Code:
         while(iter!=list.end())
         {
             if(*iter==5)
            {
                 iter = list.erase(iter) ;
                 cout << *iter ;
            }
    
            iter++ ;
            cout << *iter ;
         }
    If I do that I get a seg fault...I don't get it..that should be perfectly safe..And I've been reading that a list is sequential in memory..i even printed it out myself..and the addresses using the STL list template are freaking sequential..so why do I get a access violation, when I try that?
    You ended that sentence with a preposition...Bastard!

  11. #11
    The larch
    Join Date
    May 2006
    Posts
    3,573
    You are potentially incrementing iter twice without checking.

    Once more:

    Code:
    for (iter = myList.begin() ; iter != myList.end() ; )
        {
            std::cout << (*iter) << std::endl;
            if ((*iter) == 5)
                iter = myList.erase(iter);
            else
                ++iter;
        }
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  12. #12
    The Dragon Reborn
    Join Date
    Nov 2009
    Location
    Dublin, Ireland
    Posts
    629
    Quote Originally Posted by anon View Post
    You are potentially incrementing iter twice without checking.

    Once more:

    Code:
    for (iter = myList.begin() ; iter != myList.end() ; )
        {
            std::cout << (*iter) << std::endl;
            if ((*iter) == 5)
                iter = myList.erase(iter);
            else
                ++iter;
        }
    Great explanation, ha!
    Look, I know how to do it the way you're doing...but I don't get "how I am incrementing it twice, without checking".
    You ended that sentence with a preposition...Bastard!

  13. #13
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Erase returns the iterator to the next item after the one that was erased. If there is no next item, then it is an iterator to the end of the container. You can't increment that again.

    And anyway, if you increment the iterator returned from erase, you'll just skip one item, because the returned iterator already points at the item you should check next.
    Last edited by anon; 02-10-2011 at 11:06 AM.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  14. #14
    -bleh-
    Join Date
    Aug 2010
    Location
    somewhere in this universe
    Posts
    463
    Quote Originally Posted by Eman View Post
    Great explanation, ha!
    Look, I know how to do it the way you're doing...but I don't get "how I am incrementing it twice, without checking".
    Erase() return the next iterator, so that is one increment, then you call operator++ that's the next increment. Notwithstanding if erase() return end(), you'll end up increment it outside of the range.

    EDIT: beaten to.
    Last edited by nimitzhunter; 02-10-2011 at 10:58 AM.
    "All that we see or seem
    Is but a dream within a dream." - Poe

  15. #15
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by anon View Post
    Perhaps this was meant.

    Code:
    list.erase(iter++);
    Yes indeed. Copy and paste error on my part.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Unknown memory leak with linked lists...
    By RaDeuX in forum C Programming
    Replies: 6
    Last Post: 12-07-2008, 04:09 AM
  2. instantiated from here: errors...
    By advocation in forum C++ Programming
    Replies: 5
    Last Post: 03-27-2005, 09:01 AM
  3. How can I traverse a huffman tree
    By carrja99 in forum C++ Programming
    Replies: 3
    Last Post: 04-28-2003, 05:46 PM
  4. List class
    By SilasP in forum C++ Programming
    Replies: 0
    Last Post: 02-10-2002, 05:20 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM