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 (§ 23.3.5.5):

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
elements.


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:

display_elements()
list[0] = 1
list[1] = 2
list[2] = 3
list[3] = 4


display_elements()
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:



Output:

display_elements()
list[0] = 1
list[1] = 2
list[2] = 3
list[3] = 4


display_elements()
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:

No comments: