How to Remove Elements from a Sequence Container in C++

Published September 14, 2018 - 22 Comments

remove sequence vector remove_if C++

As part of the STL Learning Resource, we’re tackling today the STL algorithms that remove elements from a collection.

Removing an element from a C++ collection can’t be that complicated, can it?

Well, how can I put it… It has a rich complexity, let’s say.

Ok, maybe it’s a little complicated.

We will cover this topic in a series of four articles:

How to Remove Elements from a Sequence Container (vector, string, deque, list)
How to Remove Pointers from a Vector in C++ (co-written with Gaurav Sehgal)
How to Remove Elements from an Associative Container (maps and sets)
How to Remove Duplicates from an Associative Container

Indeed, the approach to remove elements is very different between sequence and associative containers.

In the sequence containers, vector and string are the most commonly used. But we will cover deque and list for comprehensiveness, even if it doesn’t mean that you should use them in general.

There are at least 4 ways to specify what values to remove from any container:

Removing the elements at a given position (or between two given positions),
Removing the elements equal to a certain value,
Removing the elements satisfying a certain predicate,
Removing the duplicates.

Let’s see how to implement those 4 injunctions on STL sequence containers.

Removing the elements at a given position

This is the easiest way. If c is a sequence container, we can remove the element at the position (iterator) position by calling:

c.erase(position);

And to remove the element in the subrange formed by the iterators first and last, we can call:

c.erase(first, last);

Like all the ranges represented by iterators in the STL, first is included and last is not included in the subrange. last points to the “past-the-end” element, like the end iterator of a container.

Note that for vector and string, all iterators pointing to elements at and after the one removed are invalidated. Indeed, all those elements have been shifted up by the call to erase.

For deque it’s a little more subtle: quoting cppreference.com, all iterators and references are invalidated, unless the erased elements are at the end or the beginning of the container, in which case only the iterators and references to the erased elements are invalidated.

This was easy, this was warm-up. Stretch out a little and let’s move on.

Removing the elements equal to a certain value

vector, deque, string

These containers don’t have a method to remove a value, so we need to use the algorithm std::remove. This algorithm takes a range and a value to remove, and shifts up all the elements that are to be kept.

For instance, calling std::remove on this range of ints and with the value 42 has the following behaviour:

remove

Note that the values of the elements left at the end of the range are unspecified. Although some implementations can leave the elements that initially were at the end of the collection, this can’t be relied on.

A bit like std::move doesn’t move and std::forward doesn’t forward (see Effective Modern C++ item 23), std::remove doesn’t remove. How nice is that?

Indeed, bearing in mind that, in the design of the STL, algorithms interact only with iterators, and not directly with the container, the container is not aware of the effect of the algorithm. For instance its size has not been reduced.

In order to effectively remove elements from the collection, we need to use the erase method that we saw in the first section of the article. For this, it is important to note that std::remove returns an iterator pointing to the “past-the-end” element of the range of the elements that should not be removed.

Said differently, the elements to remove are in the range defined by the iterator returned by std::remove and the end of the collection.

Therefore, to effectively remove values from a vector, deque or string we need to write:

v.erase(std::remove(begin(v), end(v), 42), end(v));

Wrapping the idiom

That is a C++ idiom, that you have to know if you come across it in code.

But frankly, don’t you find this is a lot of code to express such a simple thing? Wouldn’t you prefer to write something like:

v.remove(42);

v.erase(42);

But we can’t add a method to vector. However, we can write a free function with a simple interface that takes a vector and removes some of its elements!

template<typename T>
void erase(std::vector<T>& vector, T const& value)
{
    vector.erase(std::remove(begin(vector), end(vector), value), end(vector));
}

And while we’re at it, we can add to it some overloads that operate on a deque and on a string:

template<typename T>
void erase(std::deque<T>& deque, T const& value)
{
    deque.erase(std::remove(begin(deque), end(deque), value), end(deque));
}

void erase(std::string& string, char letter)
{
    string.erase(std::remove(begin(string), end(string), letter), end(string));
}

I do recommend to implement those helper functions, in particular for vector that is the most commonly used. This will make you avoid the entanglement of iterators that comes with the standard idiom.

There even has been a proposal for the C++ standard, by Stephan T. Lavavej, to add this sort of generic function. It hasn’t made it in C++17, but I suppose it still has chance to make it in a later standard.

list

Just for the sake of comprehensiveness, let’s mention that to remove an element from a list, there is a method called remove:

l.remove(42);

Indeed, since it does not offer random-access iterators, using the algorithm std::remove on a list would make list even slower than it already is.

Removing the elements that satisfy a predicate

We’ve seen how to remove from a sequence container all the elements that were equal to a certain value, such as 42.

How can we remove the elements that satisfy a predicate p?

It’s exactly the same thing, except that you need to use remove_if instead of remove.

So you just need to replace:

remove by remove_if
and 42 by p

in the previous section. Including the suggestion to write a free function erase_if to avoid the hord of iterators, and that list has a remove_if method.

So let’s apply the Don’t Repeat Yourself principle to this article and not write more about remove_if. Instead, let’s move on to the last section: removing duplicates.

Removing duplicates from a sequence container

The STL algorithm to remove duplicate is std::unique.

But beware! std::unique only removes adjacent duplicates, and not duplicates in the collection as a whole. It has a linear complexity.

Other than this, unique is very similar to remove. It only squashes up the elements of the collection without having access to the container itself. So we need to call erase on the container to effectively remove the duplicates:

vector.erase(std::unique(begin(v), end(v)), end(v));

And, like for remove, a convenience function is… convenient:

template<typename T>
void unique(std::vector<T>& vector)
{
    vector.erase(std::unique(begin(vector), end(vector)), end(vector));
}

template<typename T>
void unique(std::deque<T>& deque)
{
    deque.erase(std::unique(begin(deque), end(deque)), end(deque));
}

void unique(std::string& string)
{
    string.erase(std::unique(begin(string), end(string)), end(string));
}

And similarly to remove, std::list has a unique method.

That’s it for removing elements from a sequence container in C++.

Next up in our series about removing elements from a collection: removing pointers from a vector!