Thread: Removing from a list

  1. #1
    Registered User
    Join Date
    Jul 2007
    Posts
    186

    Thumbs up Removing from a list

    I'm iterating over a list and I want to remove certain elements from the list but because the list is resizable I'm not quite sure how to do it. In java I would think to use a list iterator. Here's my basic code:
    Code:
    for(list<Obj*>::iterator it = myQueue.begin();it!=myQueue.end();it++)
    {
    		if(some condition)
                    {
                          myQueue.erase(it);
                          it--;
                    }
    }
    But the list resizes so if I remove the last element then it will never equal to myQueue.end(). The thing I don't understand is, does myQueue.end point to the last element in the list? I've seen this type of loop used a lot to iterate over a loop but it looks like it will always miss the last element because of the != case, unless the for condition is evaluated at the end.

  2. #2
    and the hat of sweating
    Join Date
    Aug 2007
    Location
    Toronto, ON
    Posts
    3,545
    Code:
    myQueue.erase(it);
    should be:
    Code:
    it = myQueue.erase(it);
    See: Chapter 84. Prefer algorithm calls to handwritten loops
    Last edited by cpjust; 02-02-2009 at 08:36 PM.
    "I am probably the laziest programmer on the planet, a fact with which anyone who has ever seen my code will agree." - esbo, 11/15/2008

    "the internet is a scary place to be thats why i dont use it much." - billet, 03/17/2010

  3. #3
    Registered User
    Join Date
    Jul 2007
    Posts
    186
    Should I take out the it--?

  4. #4
    and the hat of sweating
    Join Date
    Aug 2007
    Location
    Toronto, ON
    Posts
    3,545
    Quote Originally Posted by jcafaro10 View Post
    Should I take out the it--?
    Since erase() returns an iterator to the element after the one that was erased, I think you'll need it in there, otherwise you'll be skipping over some elements without checking if they match your condition.
    "I am probably the laziest programmer on the planet, a fact with which anyone who has ever seen my code will agree." - esbo, 11/15/2008

    "the internet is a scary place to be thats why i dont use it much." - billet, 03/17/2010

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    The idomatic form of erasing certain elements whilst iterating through a container is:
    Code:
    for (ContainerType::iterator it = container.begin(); it!=container.end(); )
    {
    	if (condition)
    		it = container.erase(it);
    	else
    		++it;
    }
    Note the empty part of the for loop between the last semicolon and the close bracket. Use this loop form every time and you wont have any trouble.

    There are other options such as the erase/remove_if method that allow you to do the whole thing in one line too.
    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. Replies: 6
    Last Post: 03-02-2005, 02:45 AM
  2. Linked List
    By jpipitone in forum C Programming
    Replies: 4
    Last Post: 03-30-2003, 09:27 PM
  3. List class
    By SilasP in forum C++ Programming
    Replies: 0
    Last Post: 02-10-2002, 05:20 PM
  4. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM