C++ std::remove_if with lambda explained

Kent - October 10, 2015

The programmer has the responsibility to remove or resize the elements from the actual container. The only exception is when remove and remove_if are members of a container, which is the case of std::list remove_if.

Warning: Thinking that std::remove and std::remove_if will actually remove elements from a container is wrong. Both methods will move and/or copy elements around within the container, but it will never remove elements or resize the container.

The C++ methods std::remove_if and std::remove live in the header . Both methods are stable, meaning the internal order of equal elements are preserved.

std::remove_if lambda

After the stern warning in the introduction, here is how to use C++ std remove_if with lambda for predicate. Let’s start with the most elementary and simple example case.

With a vector of ints, we can inspect the vector before and after the two steps.

// Vector with numbers, initialized with an initializer list
std::vector<int> numbers{ 1,1,2,3,4,5,6 };

At this step, the contents of the vector looks like this.

<td>
  1
</td>

<td>
  1
</td>

<td>
  2
</td>

<td>
  3
</td>

<td>
  4
</td>

<td>
  5
</td>

<td>
  6
</td>
Original vector

Then we decide we want to filter out some values, say any value less than 3 must be removed. For this we can use std::remove_if. It will do what you asked for, except you must combine it with an explicit erase of the container. Why will be explained later.

The lambda expression looks like this. It has the same argument as the vector value type (int).

// Lambda for removing numbers less than 3
auto removeNumbers = [&](int number) -> bool
{
    return number < 3;
};

Call std::remove_if with the lambda as predicate.

// Call std::remove_if and obtain iterator
auto iterator = std::remove_if(numbers.begin(), numbers.end(), removeNumbers);

After remove_if, the vector will look like this.

<td>
  <span style="color: #ff0000;">1</span>
</td>

<td>
  <span style="color: #ff0000;">1</span>
</td>

<td>
  <span style="color: #ff0000;">2</span>
</td>

<td>
  <span style="color: #008000;">3</span>
</td>

<td>
  <span style="color: #008000;">4</span>
</td>

<td>
  <span style="color: #008000;">5</span>
</td>

<td>
  <span style="color: #008000;">6</span>
</td>
<td>
  <span style="color: #008000;">3</span>
</td>

<td>
  <span style="color: #008000;">4</span>
</td>

<td>
  <span style="color: #008000;">5</span>
</td>

<td>
  <span style="color: #008000;">6</span>
</td>

<td>
  <span style="color: #999999;">4</span>
</td>

<td>
  <span style="color: #999999;">5</span>
</td>

<td>
  <span style="color: #999999;">6</span>
</td>
Original vector
After remove_if

Red numbers are removed, green are kept, while gray numbers are surplus.

To remove the elements, we will have to call erase on the vector.

numbers.erase(iterator, numbers.end());

The arguments for erase is a range of elements to be removed.

<td>
  <span style="color: #ff0000;">1</span>
</td>

<td>
  <span style="color: #ff0000;">1</span>
</td>

<td>
  <span style="color: #ff0000;">2</span>
</td>

<td>
  <span style="color: #008000;">3</span>
</td>

<td>
  <span style="color: #008000;">4</span>
</td>

<td>
  <span style="color: #008000;">5</span>
</td>

<td>
  <span style="color: #008000;">6</span>
</td>
<td>
  <span style="color: #008000;">3</span>
</td>

<td>
  <span style="color: #008000;">4</span>
</td>

<td>
  <span style="color: #008000;">5</span>
</td>

<td>
  <span style="color: #008000;">6</span>
</td>

<td>
  <span style="color: #999999;">4</span>
</td>

<td>
  <span style="color: #999999;">5</span>
</td>

<td>
  <span style="color: #999999;">6</span>
</td>
<td>
  <span style="color: #008000;">3</span>
</td>

<td>
  <span style="color: #008000;">4</span>
</td>

<td>
  <span style="color: #008000;">5</span>
</td>

<td>
  <span style="color: #008000;">6</span>
</td>

<td>
</td>

<td>
</td>

<td>
</td>
Original vector
After remove_if
After erase

Here is a graphical presentation of the vector.

std_remove_if

Why remove_if can’t delete from the container

The simple answer: It’s not possible.

The longer answer: The arguments for std::remove_if doesn’t include the container type. It only includes an iterator range and a predicate (or value in the case of std::remove). The method itself doesn’t know about the underlying storage. If and only if remove_if were limited to vector or list, then it would have been possible to actually remove elements. But that is not the case.

It’s possible to create iterators from a regular array, and it’s not possible to resize an array without reallocating memory, thus copying (or moving) elements from the old array to the new array.

That’s why std::remove and std::remove_if doesn’t actually remove elements, it only moves elements to be kept.

One other thing to remember is that removed elements will be destroyed. After remove_if, there may or may not be usable data in the area after the iterator returned by the method.

Practical use for remove_if

The most practical use for remove and remove_if is to remove elements from a range.

With some collections counting millions of elements, it’s not feasible to remove one element at a time. With a logical deleted tag, it’s possible to remove all elements with linear complexity, also known as O(n).

The rationale of using std::remove_if is simple. If you’re deleting 10000 elements from a vector containing 1 million elements, you will, in the worst case scenario, move or copy most elements 10000 times. With 1 million elements, it will be close to 10 billion copies or moves.

Here is one example. Widget is an example struct for some user supplied type.

struct Widget
{
    std::string name;   // Widget name
    bool deleted;       // Should be deleted
};

Fill a vector with Widget data.

// Store them in a container
std::vector<Widget>	widgets;
widgets.emplace_back(Widget{ "W1", true });
widgets.emplace_back(Widget{ "W2", true });
widgets.emplace_back(Widget{ "W3", false });
widgets.emplace_back(Widget{ "W4", true });
widgets.emplace_back(Widget{ "W5", false });
widgets.emplace_back(Widget{ "W6", true });
widgets.emplace_back(Widget{ "W7", true });
widgets.emplace_back(Widget{ "W8", false });

The data will look like this in the vector.

<td>
  <span style="color: #ff0000;">&#8216;W1&#8217;=true</span>
</td>

<td>
  <span style="color: #ff0000;">&#8216;W2&#8217;=true</span>
</td>

<td>
  <span style="color: #339966;">&#8216;W3&#8217;=false</span>
</td>

<td>
  <span style="color: #ff0000;">&#8216;W4&#8217;=true</span>
</td>

<td>
  <span style="color: #339966;">&#8216;W5&#8217;=false</span>
</td>

<td>
  <span style="color: #ff0000;">&#8216;W6&#8217;=true</span>
</td>

<td>
  <span style="color: #ff0000;">&#8216;W7&#8217;=true</span>
</td>

<td>
  <span style="color: #339966;">&#8216;W8&#8217;=false</span>
</td>
Original

After std::remove_if, the vector will still have the same size, but notice how the move operator have actually moved the string names from the end of the vector to the beginning of the vector. This is most apparent with W5 and W8. The corresponding value after is an empty string.

<td>
  <span style="color: #ff0000;">&#8216;W1&#8217;=true</span>
</td>

<td>
  <span style="color: #ff0000;">&#8216;W2&#8217;=true</span>
</td>

<td>
  <span style="color: #339966;">&#8216;W3&#8217;=false</span>
</td>

<td>
  <span style="color: #ff0000;">&#8216;W4&#8217;=true</span>
</td>

<td>
  <span style="color: #339966;">&#8216;W5&#8217;=false</span>
</td>

<td>
  <span style="color: #ff0000;">&#8216;W6&#8217;=true</span>
</td>

<td>
  <span style="color: #ff0000;">&#8216;W7&#8217;=true</span>
</td>

<td>
  <span style="color: #339966;">&#8216;W8&#8217;=false</span>
</td>
<td>
  <span style="color: #339966;">&#8216;W3&#8217;=false</span>
</td>

<td>
  <span style="color: #339966;">&#8216;W5&#8217;=false</span>
</td>

<td>
  <span style="color: #339966;">&#8216;W8&#8217;=false</span>
</td>

<td>
  <span style="color: #ff0000;">&#8216;W4&#8217;=true</span>
</td>

<td>
  <span style="color: #ff0000;">&#8221;=false</span>
</td>

<td>
  <span style="color: #ff0000;">&#8216;W6&#8217;=true</span>
</td>

<td>
  <span style="color: #ff0000;">&#8216;W7&#8217;=true</span>
</td>

<td>
  <span style="color: #ff0000;">&#8221;=false</span>
</td>
Original
After remove_if

After erase, the vector have been resized to contain only non-deleted elements.

<td>
  <span style="color: #ff0000;">&#8216;W1&#8217;=true</span>
</td>

<td>
  <span style="color: #ff0000;">&#8216;W2&#8217;=true</span>
</td>

<td>
  <span style="color: #339966;">&#8216;W3&#8217;=false</span>
</td>

<td>
  <span style="color: #ff0000;">&#8216;W4&#8217;=true</span>
</td>

<td>
  <span style="color: #339966;">&#8216;W5&#8217;=false</span>
</td>

<td>
  <span style="color: #ff0000;">&#8216;W6&#8217;=true</span>
</td>

<td>
  <span style="color: #ff0000;">&#8216;W7&#8217;=true</span>
</td>

<td>
  <span style="color: #339966;">&#8216;W8&#8217;=false</span>
</td>
<td>
  <span style="color: #339966;">&#8216;W3&#8217;=false</span>
</td>

<td>
  <span style="color: #339966;">&#8216;W5&#8217;=false</span>
</td>

<td>
  <span style="color: #339966;">&#8216;W8&#8217;=false</span>
</td>

<td>
  <span style="color: #808080;">&#8216;W4&#8217;=true</span>
</td>

<td>
  <span style="color: #808080;">&#8221;=false</span>
</td>

<td>
  <span style="color: #808080;">&#8216;W6&#8217;=true</span>
</td>

<td>
  <span style="color: #808080;">&#8216;W7&#8217;=true</span>
</td>

<td>
  <span style="color: #808080;">&#8221;=false</span>
</td>
<td>
  <span style="color: #339966;">&#8216;W3&#8217;=false</span>
</td>

<td>
  <span style="color: #339966;">&#8216;W5&#8217;=false</span>
</td>

<td>
  <span style="color: #339966;">&#8216;W8&#8217;=false</span>
</td>

<td>
</td>

<td>
</td>

<td>
</td>

<td>
</td>

<td>
</td>
Original
After remove_if
After erase

See Also

Comments

Any comments? Create a new discussion on GitHub.
There used to be an inline comment form here, but it was removed.