STL list erase items

Question

Possible Duplicate:
Can you remove elements from a std::list while iterating through it?

I want to erase items from the list while iterating over. I have done this before, but somehow this simple example fails me. thnx for the help in advance!

#include<iostream>
#include<list>
using namespace std;

void main()
{
    list<int> x;
    for ( int i =0;i<10; i++)
        x.push_back(i);

    for( list<int>::iterator k = x.begin(); k != x.end();k++)
        cout<<*k<<" ";

    cout<<endl;

    for( list<int>::iterator k = x.begin(); k != x.end();k++)
    {
        if ((*k)%2)
        {
            x.erase(k);
        }
    }

    cout<<endl;
    getchar();
}

Jerry Coffin · Answer 1 · 2010-10-06T00:19:04.590

8

Just FWIW, what you're talking about can also be done with (for one example) std::list::remove_if:

template <class T>
class odd { 
    bool operator()(T const &value) { 
        return value % 2 != 0;
    }

};

// ...
x.remove_if(odd);

With C++ 0x and/or Boost lambda, you can do this without defining even separately, which is quite convenient for trivial conditions like this. In theory you could also define this in place with a combination of std::bind1st, std::bind2nd, std::equal and std::modulus -- but (IMO) the result would be sufficiently difficult to decipher that it would be inadvisable.

Note that std::list::remove_if (unlike std::remove_if) actually erases the items you ask to have removed, whereas std::remove_if normally needs to be combined with a call to erase to actually erase the removed items.

edited Oct 06 '10 at 00:19

answered Oct 05 '10 at 18:50

Jerry Coffin

476,176
80
629
1,111

Dude! Didn't know about Boost Lambda..that's freaking sweet. Really gotta learn STL & Boost better...would have made my C++ days so much easier. Back then I was so against using external libraries... haha. This is what happens when they teach you how to write collection classes in school but neglect to say "yeah...but don't actually write these EVER in practice" – mpen Oct 06 '10 at 00:52
@Mark: I'm not sure I'd say *never* write your own collection classes (there are a few things like ring buffers that aren't included by default), but I *would* say 1) only do it if necessary, and 2) make sure they're "Collections" as the C++ standard defines the terms, so you can use them with standard algorithms, iterators, etc. – Jerry Coffin Oct 06 '10 at 01:13
Well..that's what I meant. Don't write em if they already exist ;) There are actually plenty of cases where you need specialized collections unfortunately. – mpen Oct 06 '10 at 01:35
@Mark: Yup -- I agree on both points (though I'm not so sure about it being unfortunate that there are uses for specialized collections). – Jerry Coffin Oct 06 '10 at 02:02
It's not unfortunate that there are *uses*, it's unfortunate that we have to write them ourselves from time to time :) – mpen Oct 06 '10 at 04:29

score 5 · Accepted Answer · answered Oct 05 '10 at 18:39

5

erase returns the element after the erased element: http://www.cplusplus.com/reference/stl/vector/erase/

So try something like this:

for( list<int>::iterator k = x.begin(); k != x.end();)
  if( (*k)%2 )        
    k=x.erase(k);
  else
    ++k;

answered Oct 05 '10 at 18:39

Blindy

65,249
10
91
131

2 minor nits a) k++ is better that ++k (as a habit). Particularly with complicated types (as per Scott Myers). b) I always comment why I left out the increment on the for – pm100 Oct 05 '10 at 18:48
@pm100 "k++ is better that ++k (as a habit)" - I think this is really coder preference unless you're dealing with side effect issues. But on a line by itself, either ++k or k++ is fine. I actually prefer the first way. – dcp Oct 05 '10 at 18:51
1

@dcp: for iterators in particular it can actually have perf implications because postfix version effectively has to do a copy of the iterator, and some iterators are "fat" enough that compilers cannot fully optimize that away after inlining. In this particular case it's very doubtful it would happen, but as pm100 says, as a _habit_, with iterators it's a good one. – Pavel Minaev Oct 05 '10 at 18:59
2

@pm100: k++ is never better than ++k, the best you can hope for is that the compiler fixes your broken code to be as if you wrote ++k (which it does because people don't bother to understand what each of those means). Besides, you say "increment k", not "k increment". – Blindy Oct 05 '10 at 19:15
Writing this `for` loop is convenient but the iterator handling is so subtle. I would prefer calling `remove_if` instead, like in Jerry's answer. That will also be most efficient and sidestep issues like `++k` versus `k++`. – Frank Oct 05 '10 at 19:23
You are 100% correct (++k vs k++) - sorry ++K is always either as good as or better than k++ – pm100 Oct 05 '10 at 21:19
@user60628: Agreed, unless you need to do any sort of extra processing besides just deleting a few items. This can save you from going over the list twice or more times. – Blindy Oct 05 '10 at 22:42

Blastfurnace · Answer 3 · 2010-10-06T00:56:28.887

3

Instead of writing yet another for(;;) loop to iterate over a STL container, the whole thing can usually be done quicker with STL algorithms and lambda expressions.

Your example code can be rewritten as:

list<int> x;

int i = 0;
generate_n(back_inserter(x), 10, [&i](){ return i++; });

copy(x.begin(), x.end(), ostream_iterator<int>(cout, " "));
cout << endl;

x.remove_if([](int n){ return n%2==0; });

edited Oct 06 '10 at 00:56

answered Oct 06 '10 at 00:46

Blastfurnace

18,411
56
55
70

score 0 · Answer 4 · answered Oct 05 '10 at 18:37

0

Your iterator is invalid when you do so. Do

k = x.erase(k);

answered Oct 05 '10 at 18:37

Benoit

76,634
23
210
236

1

There is the issue of double increment in this case. the above solves it. – Egon Oct 05 '10 at 18:42
You're absolutely right, thanks – Benoit Oct 05 '10 at 18:42

STL list erase items

4 Answers4

Linked