Removal Algorithms

In this lesson, we cover the four main C++ standard library algorithms for removing objects from our containers. The functions we will cover are: remove(), remove_if(), remove_copy(), and remove_copy_if().

• remove() searches our range for specific values, and removes any it finds.
• remove_if() passes the objects of our range to a predicate function. If that function returns true, the object is removed from the range.
• remove_copy() combines the copy() and remove() algorithms. It copies objects from a source range to a new location. However, if an object matches a specific value, it is not copied.
• remove_copy_if() combines the copy() and remove_if() algorithms. It passes every object in our source range to a predicate function. If that function returns true, our object is copied to a destination range. Otherwise, it isn’t copied.

We also explain why the remove algorithms don’t necessarily erase items from the container, and how to address that using the remove-erase idiom.

All the algorithms in this section are available within the <algorithm> header:

1#include <algorithm>

std::ranges::remove()

The most basic use of the std::ranges::remove() algorithm involves two arguments:

• The range we want the algorithm to run on
• The value we want to remove from the range

In the following example, we request the removal of any 3s from our Source range:

1std::vector Source{1, 2, 3, 4, 5, 6};
2std::ranges::remove(Source, 3);

Each object in our collection is compared to 3 using the equality operator ==. If that operator returns true, the object is removed.

For reasons we’ll cover later in this lesson, the removal algorithms are not able to modify the size of our container. Instead, all of the objects that were not removed are clustered at the start of our container, potentially with surplus elements at the end.

Note the additional 6 at the end of our container after running the remove() algorithm:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Source{1, 2, 3, 4, 5, 6};
7
8  std::ranges::remove(Source, 3);
9
10  std::cout << "Objects in Source: ";
11  for (auto Num : Source) {
12    std::cout << Num << ", ";
13  }
14}

1Objects in Source: 1, 2, 4, 5, 6, 6,

We explain why remove() works this way, and how to erase the surplus elements in the next section. For now, let's finish our exploration of std::ranges::remove()

The amount of surplus objects we have on the right of our container is equal to the number of elements we removed. In the above example, we removed 1 object, so we have only one surplus object at the end.

Elements are moved left based on move semantics, and the surplus elements at the end of the container are in the moved-from state. We define what move semantics, and the moved-from state are in a dedicated lesson:

Move Semantics

Learn how we can improve the performance of our types using move constructors, move assignment operators and std::move()

Return Type

std::ranges::remove() returns a subrange that contains all the surplus elements on the right of the container. Below, we use this returned subrange for some follow-up operations:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Source{1, 2, 3, 4, 5, 6};
7
8  auto Surplus{
9      std::ranges::remove(Source, 3)};
10
11  std::cout << "Source:  ";
12  for (auto Num : Source) {
13    std::cout << Num << ", ";
14  }
15
16  std::cout << "\nSurplus: ";
17  for (auto Num : Surplus) {
18    std::cout << Num << ", ";
19  }
20
21  std::cout << "\nQuantity Removed: "
22    << Surplus.size();
23
24  std::cout << "\nObjects to Keep: ";
25  for (auto Num : std::ranges::subrange{
26    Source.begin(), Surplus.begin()}) {
27    std::cout << Num << ", ";
28  }
29}

1Source:  1, 2, 4, 5, 6, 6,
2Surplus: 6,
3Quantity Removed: 1
4Objects to Keep: 1, 2, 4, 5, 6,

Creating Views using std::ranges::subrange

This lesson introduces std::ranges::subrange, allowing us to create non-owning ranges that view some underlying container

The Remove-Erase Idiom

Let's cover why the removal algorithms leave surplus elements at the end of the counter. Iterators provide a standardized way to traverse through containers, and access objects within containers. However, they are much more limited in what they can do to the container itself.

Specifically, they cannot erase objects from a container. How we erase objects from a container (and therefore, resize the container) depends on the type of container it is. It’s not something that is in the purview of ranges or iterators.

The ability to erase something from a container is generally provided as a method on that container type.

For example, the erase() method on std::vector lets us pass an iterator pair, denoting the start and end of the subrange we want to erase. Conveniently, as we saw above, this is exactly what the std::ranges::remove() algorithm returns. Below, we use this to erase the surplus elements from our std::vector container:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Source{1, 2, 3, 3, 3, 4, 5};
7
8  auto Subrange{
9    std::ranges::remove(Source, 3)};
10
11  Source.erase(Subrange.begin(), Subrange.end());
12
13  std::cout << "Objects in Source: ";
14  for (auto Num : Source) {
15    std::cout << Num << ", ";
16  }
17}

1Objects in Source: 1, 2, 4, 5,

The std::ranges::subrange type supports structured binding, giving us easier access to the iterator and sentinel. Therefore, the previous example can be rewritten like this:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Source{1, 2, 3, 3, 3, 4, 5};
7
8  auto [begin, end]{
9    std::ranges::remove(Source, 3)};
10
11  Source.erase(begin, end);
12
13  std::cout << "Objects in Source: ";
14  for (auto Num : Source) {
15    std::cout << Num << ", ";
16  }
17}

Other containers, including standard library linked lists, also have erase() methods that work similarly. This pattern of moving the elements we want to keep to the left of a container, and then truncating it, is so common, it has its own name: the remove-erase idiom.

std::ranges::remove_if()

The remove_if() algorithm works similarly to remove() but our second argument is a predicate function, rather than an object to run an equality check against. If the predicate returns true for an object, that object will be removed from the input range.

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Source{1, 2, 3, 4, 5, 6};
7
8  auto isEven{[](int x) { return x % 2 == 0; }};
9
10  std::ranges::remove_if(Source, isEven);
11
12  std::cout << "Objects in Source: ";
13  for (auto Num : Source) {
14    std::cout << Num << ", ";
15  }
16}

Similar to remove() the remove_if() algorithm will not erase anything. Rather, it will ensure the objects we want to keep are at the beginning of the container. In the previous example, we want to keep the odd numbers, ie 1, 3, and 5, so those are now at the left edge of our source:

1Objects in Source: 1, 3, 5, 4, 5, 6,

Return Type

The remove_if() algorithm returns a subrange within our original container. The subrange will be on the right side of our container and will contain the part we want to erase. In this example, the elements to erase are the last three:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Source{1, 2, 3, 4, 5, 6};
7
8  auto isEven{[](int x) { return x % 2 == 0; }};
9
10  auto Result{
11      std::ranges::remove_if(Source, isEven)};
12
13  std::cout << "Objects in Source: ";
14  for (auto Num : Source) {
15    std::cout << Num << ", ";
16  }
17
18  std::cout << "\nObjects to Erase:  ";
19  for (auto Num : Result) {
20    std::cout << Num << ", ";
21  }
22}

1Objects in Source: 1, 3, 5, 4, 5, 6, 
2Objects to Erase:  4, 5, 6,

We can then use container-specific algorithms to do that erasing. For example, if our original container was a std::vector, we can use the erase() method of that class:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Source{1, 2, 3, 4, 5, 6};
7
8  auto isEven{[](int x) { return x % 2 == 0; }};
9
10  auto [begin, end]{
11      std::ranges::remove_if(Source, isEven)};
12
13  Source.erase(begin, end);
14
15  std::cout << "Objects in Source: ";
16  for (auto Num : Source) {
17    std::cout << Num << ", ";
18  }
19}

1Objects in Source: 1, 3, 5,

std::ranges::remove_copy()

The remove_copy() algorithm is a combination of the copy() and remove() algorithms. Objects are copied from one location to another, however, objects that pass an equality check with a value we provide are not copied. In its typical usage, the std::ranges::remove_copy() algorithm has three arguments:

1. The source range
2. An iterator to the beginning of the destination range
3. An object to compare against

Below, we copy objects that are not equal to 3 - in other words, we copy only the objects where Object == 3 return false:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Source{1, 2, 3, 4, 5, 6};
7  std::vector Destination{0, 0, 0, 0, 0, 0};
8
9  std::ranges::remove_copy(
10      Source, Destination.begin(), 3);
11
12  std::cout << "Objects in Source: ";
13  for (auto Num : Source) {
14    std::cout << Num << ", ";
15  }
16
17  std::cout << "\nObjects in Destination: ";
18  for (auto Num : Destination) {
19    std::cout << Num << ", ";
20  }
21}

1Objects in Source: 1, 2, 3, 4, 5, 6, 
2Objects in Destination: 1, 2, 4, 5, 6, 0,

Return Type

The algorithm will return a std::in_out_result, aliased as std::remove_copy_result. This is a struct with two properties:

• in - an iterator for our source range, pointing to where the sentinel was found. In the above example, this will be equivalent to Source.end()
• out - an iterator for our destination location, pointing beyond the last element that was copied.

Below, we use this return value for some logging operations, and to trim our destination container to only contain the elements that were copied:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Source{1, 2, 3, 4, 5, 6};
7  std::vector Destination{0, 0, 0, 0, 0, 0};
8
9  auto [in, out]{std::ranges::remove_copy(
10      Source, Destination.begin(), 3)};
11
12  std::cout << "The source had "
13            << std::distance(Source.begin(), in)
14            << " elements.\n";
15
16  std::cout << std::distance(
17                   Destination.begin(), out)
18            << " elements were copied.";
19
20  Destination.erase(out, Destination.end());
21
22  std::cout << "\nObjects in Destination: ";
23  for (auto Num : Destination) {
24    std::cout << Num << ", ";
25  }
26}

1The source had 6 elements.
25 elements were copied.
3Objects in Destination: 1, 2, 4, 5, 6,

std::ranges::remove_copy_if()

The remove_copy_if() algorithm works in the same way as remove_copy() - the only difference is that rather than using an equality check to determine which objects are excluded from the copy, we instead use a predicate function.

The basic usage of the algorithm requires three arguments:

1. The source range
2. An iterator to the beginning of the destination range
3. A predicate function to determine which objects to exclude

Each object in our source range will be passed to our predicate function. If that function returns false, the object will be copied to the destination location. If it returns true, the object will be excluded, effectively removing it from the destination location.

Below, we use remove_copy_if() to copy objects to a destination, unless they are greater than or equal to 2:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Source{-3, -2, -1, 0, 1, 2, 3};
7  std::vector Destination{0, 0, 0, 0, 0, 0, 0};
8
9  auto Predicate{[](int x) { return x >= 2; }};
10
11  std::ranges::remove_copy_if(
12      Source, Destination.begin(), Predicate);
13
14  std::cout << "\nObjects in Source: ";
15  for (auto Num : Source) {
16    std::cout << Num << ", ";
17  }
18
19  std::cout << "\nObjects in Destination: ";
20  for (auto Num : Destination) {
21    std::cout << Num << ", ";
22  }
23}

1Objects in Source: -3, -2, -1, 0, 1, 2, 3,
2Objects in Destination: -3, -2, -1, 0, 1, 0, 0,

Return Type

Similar to remove_copy(), the remove_copy_if() algorithm will return a std::in_out_result, aliased to std::remove_copy_if_result. This is a struct with two properties:

• in - an iterator for the input range, pointing to where the sentinel was found. In the previous example, this will be equivalent to Source.end()
• out - an iterator for the destination location, pointing beyond the last element that was copied

This return value may or may not be useful, depending on our needs. Typically, when we do need to use it, we’ll use structured binding to access the two properties directly.

In this example, we show how it can be used with std::distance() to get some information about our input range, and the number of objects that were copied. We then use it to trim our destination container to only contain the elements that were copied:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Source{-3, -2, -1, 0, 1, 2, 3};
7  std::vector Destination{0, 0, 0, 0, 0, 0, 0};
8
9  auto Predicate{[](int x) { return x >= 2; }};
10
11  auto [in, out]{std::ranges::remove_copy_if(
12      Source, Destination.begin(), Predicate)};
13
14  std::cout << "The source had "
15            << std::distance(Source.begin(), in)
16            << " elements.\n";
17
18  std::cout << std::distance(
19                   Destination.begin(), out)
20            << " elements were copied.";
21
22  Destination.erase(out, Destination.end());
23
24  std::cout << "\nObjects in Destination: ";
25  for (auto Num : Destination) {
26    std::cout << Num << ", ";
27  }
28}

1The source had 7 elements.
25 elements were copied.
3Objects in Destination: -3, -2, -1, 0, 1,

Projection

As with most range-based algorithms, every function we covered in this lesson has an overload that accepts a projection function.

Projection Functions

Learn to use projection functions to apply range-based algorithms on derived data

In the following example, we provide a projection function to remove() that projects objects in our input range to their absolute value. As a result, both the -2 and 2 are projected to 2. Both of these projections pass an equality check with the second argument we provide, and therefore both the -2 and the 2 are removed:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Source{-3, -2, -1, 0, 1, 2, 3};
7
8  auto Projector{[](int x) {
9    return std::abs(x); }};
10
11  auto Subrange{
12    std::ranges::remove(Source, 2, Projector)};
13
14  std::cout << "Objects in Destination: ";
15  for (auto Num : std::ranges::subrange{
16    Source.begin(), Subrange.begin()}) {
17    std::cout << Num << ", ";
18  }
19}

1Objects in Destination: -3, -1, 0, 1, 3,

In this more complex example, we use the remove_copy_if() algorithm with a member function as our projector. This function projects our Player objects to their level. This level is then received by our predicate function, which returns true if the Level is less than 15

The net effect of this is that any Player below level 15 is not copied to the destination:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5class Player {
6 public:
7  int GetLevel() { return Level; }
8  std::string GetName() { return Name; }
9
10  std::string Name{"(None)"};
11  int Level;
12};
13
14int main() {
15  std::vector<Player> Players;
16  Players.emplace_back("Roderick", 10);
17  Players.emplace_back("Anna", 20);
18  Players.emplace_back("Robert", 30);
19
20  std::vector<Player> Destination;
21  Destination.resize(Players.size());
22
23  auto[in, out]{std::ranges::remove_copy_if(
24    Players,
25    Destination.begin(),
26    [](int Level) { return Level < 15; },
27    &Player::GetLevel
28  )};
29
30  Destination.erase(out, Destination.end());
31
32  std::cout << "Copied: ";
33  for (Player& P : Destination) {
34    std::cout << P.GetName() << " (Level "
35      << P.GetLevel() << "), ";
36  }
37}

1Copied: Anna (Level 20), Robert (Level 30),

Using Iterator-Sentinel Pairs

As usual, the range-based removal algorithms covered in this lesson allow us to define our input ranges as iterator-sentinel pairs, rather than a single argument.

Below, we use this technique to remove all the 0s in our container, excluding the first and last elements:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Source{0, 1, 0, 1, 0};
7
8  auto Removed{std::ranges::remove(
9    Source.begin() + 1, Source.end() - 1, 0)};
10
11  Source.erase(Removed.begin(), Removed.end());
12
13  std::cout << "Removed " << Removed.size()
14            << " object(s)";
15
16  std::cout << "\nObjects remaining: ";
17  for (auto Num : Source) {
18    std::cout << Num << ", ";
19  }
20}

1Removed 1 object(s)
2Objects remaining: 0, 1, 1, 0,

Iterator-Based Algorithms

The algorithms in this lesson use the range concepts, introduced in C++20. In earlier specifications, we have variations of these algorithms that work directly with iterators. These are available by excluding the ranges namespace from the identifier.

For example, instead of using std::ranges::remove(), we could use std::remove()

Compared to the range-based counterparts, the older iterator variations of these algorithms have a few disadvantages:

• We must provide our collections as two arguments - we don’t have the option of simply providing a container directly
• The end of our input be provided as an iterator, while the range-based variations use the more flexible sentinel concept
• The iterator-based algorithms do not support projection functions

Additionally, the std::remove() and std::remove_if() algorithms return an iterator pointing beyond the last element of our new range. Everything from that iterator to the end of the input represents surplus objects that we can erase.

This return type is less friendly than the range-based counterparts, which represent the surplus elements as a subrange. Below, we rewrite the previous example to use std::remove() rather than std::ranges::remove():

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Source{0, 1, 0, 1, 0};
7
8  auto End{std::remove(
9    Source.begin() + 1, Source.end() - 1, 0)};
10
11  ptrdiff_t RemovedCount {
12    std::distance(End, Source.end() - 1)};
13
14  std::cout << "Removed "
15    << RemovedCount << " object(s)";
16
17  Source.erase(End, End + RemovedCount);
18
19  std::cout << "\nObjects remaining: ";
20  for (auto Num : Source) {
21    std::cout << Num << ", ";
22  }
23}

1Removed 1 object(s)
2Objects remaining: 0, 1, 1, 0,

Summary

In this lesson, we explored the removal algorithms provided by the C++ standard library. We covered:

• The remove(), remove_if(), remove_copy(), and remove_copy_if() algorithms.
• Understanding that removal algorithms do not erase elements from containers but rather rearrange them such that the elements to remove are at the end
• The concept of the remove-erase idiom, where removing and erasing objects are typically two separate operations.
• How to use the return values of removal algorithms to perform further operations, such as erasing the "removed" elements.
• The distinction between range-based removal algorithms introduced in C++20 and their older iterator-based counterparts.
• Introduction to projection functions and how they can be used with removal algorithms to enhance flexibility.

Next Lesson

Replacement Algorithms

An overview of the key C++ standard library algorithms for replacing objects in our containers. We cover replace(), replace_if(), replace_copy(), and replace_copy_if().

ContinueView Course