In C++, removing an object from a list

Question

I'm writing a program which is more or less like this :

#include <list>

list<MyClass> things;

class MyClass {
   // some stuff

   void remove() {
       things.remove_if(THING_IS_ME);
   }
};

What do I need to write instead of THING_IS_ME?

In other words, I'm using a global STL list as a collection of things. At some point, an object which is in the list recognises that it is redundant and wants to a) get itself removed from the list, and b) get itself destructed.

How do I do this?

I haven't written C++ for about 15 years and am a bit confused by this page here : http://www.cplusplus.com/reference/algorithm/remove_if/

What are these Predicates? Does C++ have higher-order functions now?

Answer 1

First, a simple hand-written loop:

for( list<MyClass>::iterator it = things.begin(); it != things.end(); /*  */ ) {
    if( qualifiesForDelete( *it ) ) {
        it = things.erase( it );
    }
    else {
        ++it;
    }
}

Second, using the the remove_if algorithm. remove_if being an algorithm, as opposed to a member function of list, can't actually delete any elements, rather it moves the elements-to-be-deleted towards the end of list. Subsequently erase has to be called. This is a very important idiom, erase-remove idiom, that must be learnt.

things.erase( 
    remove_if( things.begin(), things.end(), deletionPredicate ), 
    things.end() 
);

where deletionPredicate is a function or function-object that takes a single argument of type and returns bool. The elements for which true is returned are considered to be removed.

Answer 2

(Originally a set of comments, but rewritten as an answer after discovering what the OP actually wanted to do.)

You do realize that the STL containers store copies of things you insert, right? That means instances of MyClass better be comparable (e.g. via operator==) - you can't just compare the addresses as they will always be different.

If having copies of MyClass makes no sense, then you're probably better off with a pointer container.

That being said, the C++ language uses copy-semantics by default. The language requires that you make things like references explicit in the code. I highly recommend that you pick up a good C++ book or you will be tripped up by issues like this in the future.

Answer 3

The remove_if function takes three parameters: two iterators that define the range you're working on, and a predicate (test function that returns bool). The start iterator points to the first element you want to work on; the end iterator points to the element after the last element in the range.

In the example from the page you linked to, the predicate is the line of code that says

bool IsOdd (int i) { return ((i%2)==1); }

To make your code do what you want, you'd need to write something like this:

things.remove_if(things.begin(), things.end(), SomePredicateFunction);

and you'd define SomePredicateFunction like so (replacing true with an appropriate test):

bool SomePredicateFunction (MyClass c) { return true; }

Answer 4

Things have changed dramatically in C++ in the past 15 years. In July 1994 Alexander Stepanov's proposal of a library that incorporates his ideas of generic programming received the final approval from the ANSI/ISO committee. This library that we conveniently call today the STL subsequently became a standard C++ library. The story of the STL is about as fascinating as the ideas behind it, and it definitely is worth the read.

The std::remove_if() function that you found is just another reflection of this philosophy that became part of C++'s modern identity. In short, this is a generic function that will work on any container (sequence) of elements and with any(thing that acts like a) condition. To this effect, you must provide the function two things:

1. a couple of iterators that delimit the range of elements you wish to work on;
2. and a predicate that, when invoked on an element, returns true if the element is to be removed and false otherwise.

As it turns out, in this case the predicate you want is that of equality. And because it is such a common task to remove elements based on equality the standard also provides the std::remove() function, which assumes an implicit equality predicate. Of course, you must make sure that elements can compare:

bool operator==(const MyClass& a, const MyClass& b)
{
    // return true if the two are equal, and false otherwise.
}

We can then use our predicate to remove elements of type MyClass:

std::remove(things.begin(), things.end(), *this);  // if *this == elem

Recall that the standard function std::remove() works on any container, even ones that haven't been created yet. Because every kind of container has its own way of removing elements, this function can't really perform the removal without knowing implementation details of the container it works on. So instead, the std::remove() function swaps elements around such that the elements "removed" are at the end of the container. Then, it returns an iterator pointing at the first element of the consecutive elements "removed".

typedef std::list<MyClass>::iterator iter;
iter first_removed = std::remove(things.begin(), things.end(), *this);

Finally, we truly remove elements by calling the specific container's removal function, which works on a single position in the list or on a range of consecutive elements to remove:

things.erase(first_removed, things.end());

It is not uncommon to see this sort of code in a single line:

things.erase(std::remove(things.begin(), things.end(), *this),
             things.end());

This all may seem overwhelming and complicated, but it has a few advantages. For one thing, this design of the standard library supports dynamic programming. It also allows the standard library to offer containers with very slim interfaces, as well as few free functions that work on many different kinds of containers. It allows you to quickly create a container and instantly gain all the features of the standard library to work with it. Alternatively, it allows you to quickly write a generic function that instantly works with all standard containers -- those written already and those not written yet.