Thursday, 3 May 2012

Removing STL list elements whilst iterating through it

I have already written about the traps and solutions when we try to remove elements from vectors and maps whilst iterating through them. Today I want to cover the same topic regarding lists.

Let us assume we have a list containing integers and we want to remove all elements that are odd numbers. If not aware of std::list::remove() side effects, the first thing we would try could be the following:

When run, this program removes element with the value 1 but the next time it tries to dereference iterator it crashes with the message:

Microsoft Visual Studio
Unhandled exception at 0x00d5c7a2 in Test.exe: 0xC0000005: Access violation reading location 0xfeeefef6.

The most often source of errors when working with STL containers are invalid iterators. Before calling some function on some STL container, we need to make sure we understand how it affects container's iterators. The latest draft of the new C++ standard (C++11) says (§

void remove(const T& value);
template void remove_if(Predicate pred);

Effects: Erases all the elements in the list referred by a list iterator i for which the following conditions
hold: *i == value, pred(*i) != false. Invalidates only the iterators and references to the erased

Throws: Nothing unless an exception is thrown by *i == value or pred(*i) != false.

This explains what happened in our program: remove() invalidated iterator and all subsequent operations on iterator (incrementing, dereferencing) yielded undefined behaviour (crash in our case).

A simple solution to this is to save iterator's value before removing an element, increment it and then remove element on the saved (previous) iterator value. In the next iteration iterator will be pointing to the next element after the removed one:

This time program works as expected and yields the following output:

list[0] = 1
list[1] = 2
list[2] = 3
list[3] = 4

list[0] = 2
list[1] = 4

Instead of using temporary variable to store previous value of the iterator, we can use post-increment operator (this works as function arguments are fully evaluated before a function is called):

Another function that removes an element (or a range of elements) from a list is std::list::erase(). Instead of the element value, an iterator is passes as its argument. Similar to list::remove(), it invalidates the iterator of the erased element.

This yields debug assertion error:

Microsoft Visual C++ Debug Library
Debug Assertion Failed!

Program: C:\test\Tests.exe
File: c:\program files\microsoft visual studio 10.0\vc\include\list
Line: 227

Expression: list iterator not incrementable

For information on how your program can cause an assertion
failure, see the Visual C++ documentation on asserts.

(Press Retry to debug the application)
Abort Retry Ignore

Applying the same fix like before solves the problem:

If we want to remove from a list all elements that match certain criteria, the best way to achieve that is not to fiddle with iterators and loops but to use std::list::remove_if(). This function uses unary predicate to check the criteria for the current element. In our case the predicate returns true if the value is odd number:


list[0] = 1
list[1] = 2
list[2] = 3
list[3] = 4

list[0] = 2
list[1] = 4

NOTE: The signature of the predicate does not need to have const &, but the function must not modify the objects passed to it.

To make the code even smaller, we can move the code from a predicate to a lambda expression:

1 comment:

micheal pan said...

BE SMART AND BECOME RICH IN LESS THAN 3DAYS....It all depends on how fast 
you can be to get the new PROGRAMMED blank ATM card that is capable of
hacking into any ATM machine,anywhere in the world. I got to know about 
this BLANK ATM CARD when I was searching for job online about a month 
ago..It has really changed my life for good and now I can say I'm rich and 
I can never be poor again. The least money I get in a day with it is about 
$50,000.(fifty thousand USD) Every now and then I keeping pumping money 
into my account. Though is illegal,there is no risk of being caught 
,because it has been programmed in such a way that it is not traceable,it 
also has a technique that makes it impossible for the CCTVs to detect 
you..For details on how to get yours today, email the hackers on : ( ). Tell your 
loved once too, and start to live large. That's the simple testimony of how 
my life changed for good...Love you all ...the email address again is ;