C++ Replace, Remove, and Erase Algorithms

In this lesson, we cover all 8 of the main C++ standard library algorithms for replacing and removing objects from our containers. The functions we will cover are: replace, replace_if, replace_copy, replace_copy_if, remove, remove_if, remove_copy, and remove_copy_if.

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>
2

std::ranges::replace

The replace algorithm has 3 parameters:

1. The range we want to run the algorithm on
2. The object we want to replace
3. The object we want to replace it with

For each object in our range, an equality check using the == operator is performed with the second argument. If the equality check returns true, the object we provide as the third argument is copied into that position in the container, thereby overwriting and replacing the original element.

Below, we replace all objects that are equal to 3 with a 0:

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  std::ranges::replace(Source, 3, 0);
9
10  std::cout << "Objects in Source: ";
11  for (auto Num : Source) {
12    std::cout << Num;
13  }
14}
15

1Objects in Source: 1200045
2

std::ranges::replace returns a past-the-end iterator for the input range:

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 Result{
9      std::ranges::replace(Source, 3, 0)};
10
11  std::cout << "Objects in Source: ";
12  for (auto Num : Source) {
13    std::cout << Num;
14  }
15  std::cout << "\nLast Element in Range: "
16            << *(Result - 1);
17}
18

1Objects in Source: 1200045
2Last Element in Range: 5
3

Using Iterator-Based Algorithms

In this lesson, we focus on algorithms that use the C++20 ranges functionality. If preferred, any algorithm in this lesson can be replaced with an alternative that works directly with iterators. These can be accessed by excluding the ranges component of the namespace, and passing out input as a pair of iterators, instead of a range.

Below, we rewrite our previous example to use std::replace instead of std::ranges::replace:

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  std::replace(Source.begin(), Source.end(), 3,
9               0);
10
11  std::cout << "Objects in Source: ";
12  for (auto Num : Source) {
13    std::cout << Num;
14  }
15}
16

1Objects in Source: 1200045
2

std::ranges::replace_if

The replace_if algorithm works similarly to replace, except the second argument is a predicate rather than an object to perform an equality check on.

Each object in the range is passed to the predicate function. If the predicate returns true, the object is replaced with what we provide as the third parameter.

Similar to replace, the replace_if function returns a past-the-end iterator for the input range.

Below, we replace all even numbers with 0:

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{std::ranges::replace_if(
11      Source, isEven, 0)};
12
13  std::cout << "Objects in Source: ";
14  for (auto Num : Source) {
15    std::cout << Num;
16  }
17  std::cout << "\nLast Element in Range: "
18            << *(Result - 1);
19}
20

1Objects in Source: 103050
2Last Element in Range: 0
3

std::ranges::replace_if has an optional fourth argument. This is for a projection function that will be applied to the element before they are passed to the predicate. We cover projection functions in more detail here:

Projections and Algorithms

Learn how to use projections with standard library algorithms in C++

Below, we project our number to a day of the week, and then replace the number with a 0 if the corresponding day begins with S:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector<std::string> Days{
7      "Monday",   "Tuesday", "Wednesday",
8      "Thursday", "Friday",  "Saturday",
9      "Sunday"};
10  std::vector Source{0, 1, 2, 3, 4, 5, 6};
11
12  auto Projector{
13      [&Days](int x) { return Days[x]; }};
14
15  auto Predicate{[](const std::string& d) {
16    return d.starts_with('S');
17  }};
18
19  auto Result{std::ranges::replace_if(
20      Source, Predicate, 0, Projector)};
21
22  std::cout << "Objects in Source: ";
23  for (auto Num : Source) {
24    std::cout << Num;
25  }
26  std::cout << "\nLast Element in Range: "
27            << *(Result - 1);
28}
29

1Objects in Source: 0123400
2Last Element in Range: 0
3

std::ranges::replace_copy

The replace_copy algorithm has 4 arguments:

1. A range containing objects we want to copy
2. An iterator for the start of where we want the objects to be copied to
3. An object we want to replace
4. The object we want to replace it with

The algorithm will copy objects from the source to the destination. But, for each object, it will perform an equality check (using the == operator) against what we provided as the third argument. If the equality check returns true, the algorithm will instead copy what we provided as the fourth argument.

Below, we copy a range of numbers, but if the object is == to 3, we replace it with 0 in the destination:

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

1Objects in Source: 0123456
2Objects in Destination: 0120456
3

The std::ranges::replace_copy algorithm returns a std::ranges::in_out_result, which is aliased as std::ranges::replace_copy_result. It is a struct with two properties:

• in: a past-the-end iterator for the input range
• out: a past-the-end iterator for the destination range

This return value may or may not be useful, depending on whether we need to perform any follow-up operations:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Source{0, 1, 2, 3, 4, 5, 6};
7  std::vector<int> Destination;
8  Destination.resize(Source.size());
9
10  auto [in, out]{std::ranges::replace_copy(
11      Source, Destination.begin(), 3, 0)};
12
13  std::cout << "Objects in Source: ";
14  for (auto Num : Source) {
15    std::cout << Num;
16  }
17
18  std::cout << "\nObjects in Destination: ";
19  for (auto Num : Destination) {
20    std::cout << Num;
21  }
22
23  std::cout
24      << "\nThe last object in the source is: "
25      << *(in - 1);
26  std::cout << "\nThe last object in the "
27               "destination is: "
28            << *(out - 1);
29}
30

1Objects in Source: 0123456
2Objects in Destination: 0120456
3The last object in the source is: 6
4The last object in the destination is: 6
5

std::ranges::replace_copy has an optional 5th parameter, to which we can pass a projection function. The objects in our input range are passed through the projection function before they are compared to the replacement target.

Below, we use the function to project the objects to their absolute value. Therefore, the algorithm replaces both 3 and -3:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Source{
7      -3, -2, -1, 0, 1, 2, 3,
8  };
9  std::vector<int> Destination;
10  Destination.resize(Source.size());
11
12  auto Projector{
13      [](int x) { return std::abs(x); }};
14
15  std::ranges::replace_copy(Source,
16                            Destination.begin(),
17                            3, 0, Projector);
18
19  std::cout << "Objects in Source: ";
20  for (auto Num : Source) {
21    std::cout << Num << ", ";
22  }
23
24  std::cout << "\nObjects in Destination: ";
25  for (auto Num : Destination) {
26    std::cout << Num << ", ";
27  }
28}
29

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

std::ranges::replace_copy_if

replace_copy_if works in the same way as replace_copy, except the third argument is a predicate function, rather than an object for comparison.

Below, we copy elements from our Source to Destination but, if the element is even, we copy 0 instead:

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

1Objects in Source: 0123456
2Objects in Destination: 0103050
3

Similar to std::ranges::replace_copy, the return value is a std::ranges::in_out_result, where:

• in: a past-the-end iterator for the input range
• out: a past-the-end iterator for the destination range

The type is aliased to std::ranges::replace_copy_if_result. Here is an example of it in use:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Source{0, 1, 2, 3, 4, 5, 6};
7  std::vector<int> Destination;
8  Destination.resize(Source.size());
9
10  auto isEven{[](int x) { return x % 2 == 0; }};
11
12  auto [in, out]{std::ranges::replace_copy_if(
13      Source, Destination.begin(), isEven, 0)};
14
15  std::cout << "Objects in Source: ";
16  for (auto Num : Source) {
17    std::cout << Num;
18  }
19
20  std::cout << "\nObjects in Destination: ";
21  for (auto Num : Destination) {
22    std::cout << Num;
23  }
24
25  std::cout
26      << "\nThe last object in the source is: "
27      << *(in - 1);
28  std::cout << "\nThe last object in the "
29               "destination is: "
30            << *(out - 1);
31}
32

1Objects in Source: 0123456
2Objects in Destination: 0103050
3The last object in the source is: 6
4The last object in the destination is: 0
5

std::ranges::replace_copy_if has an optional 5 parameter, which we can pass a projection function to. Below, we combine a projection and predicate function to replace an object if its absolute value is less than 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<int> Destination;
8  Destination.resize(Source.size());
9
10  auto toAbs{[](int x) { return std::abs(x); }};
11  auto lessThanTwo{[](int x) { return x < 2; }};
12
13  std::ranges::replace_copy_if(
14      Source, Destination.begin(), lessThanTwo,
15      0, toAbs);
16
17  std::cout << "Objects in Source: ";
18  for (auto Num : Source) {
19    std::cout << Num << ", ";
20  }
21
22  std::cout << "\nObjects in Destination: ";
23  for (auto Num : Destination) {
24    std::cout << Num << ", ";
25  }
26}
27

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

std::ranges::remove

The std::ranges::remove algorithm doesn’t work how most people would predict. We pass it a value that we would like to “remove” from our collection. In the following example, we request the removal of any 3s:

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

If the object is equal (based on the == operator) to the argument we pass in, the objects to the right of that element get moved left, thereby overwriting it:

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}
15

The effect of this approach is that we may have surplus elements on the right of our container. Note the additional 6 in the output of the previous example

1Objects in Source: 124566
2

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 movement 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, std::move and rvalues

Learn how to implement move semantics in C++, the difference between lvalues and rvalues, and what std::move really does.

std::ranges::remove returns a subrange, that contains all the surplus elements on the right of the container.

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 ObjectsToErase{
9      std::ranges::remove(Source, 3)};
10
11  std::ranges::subrange ObjectsToKeep{
12      Source.begin(), ObjectsToErase.begin()};
13
14  std::cout << "Objects to Keep:  ";
15  for (auto Num : ObjectsToKeep) {
16    std::cout << Num;
17  }
18
19  std::cout << "\nObjects to Erase: ";
20  for (auto Num : ObjectsToErase) {
21    std::cout << Num;
22  }
23}
24

1Objects to Keep:  12456
2Objects to Erase: 6
3

The Remove-Erase Idiom

It’s likely surprising and a little annoying that remove leaves surplus elements at the end of our container. This is a limitation of generalized, iterator-based algorithms.

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.

The specific problem here is that they cannot erase objects from containers. Erasing something from a container means changing the size of the container, and that’s not something that can typically be generalized. How we resize a container really depends on the type of container it is.

Fortunately, the standard library containers generally come with methods that can help us here. Usually, those methods are called erase.

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, this is exactly what std::ranges::remove returns:

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 [start,
9        end]{std::ranges::remove(Source, 3)};
10
11  Source.erase(start, end);
12
13  std::cout << "Objects in Source: ";
14  for (auto Num : Source) {
15    std::cout << Num;
16  }
17}
18

1Objects in Source: 1245
2

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.

The approach may seem like an indirect and inefficient way to remove items, but this tends not to be the case. Deleting an object from a container involves resizing the container and potentially moving a lot of other objects to a new position. Moreover, when we’re using an algorithm like std::ranges::remove, we’re probably removing multiple objects.

For most types of containers, deleting multiple objects scattered through the collection is an expensive operation. This is particularly true for resizable arrays, such as std::vector, which tend to be the container type we’re using most often.

As such, unless there’s a specific reason to do otherwise, the remove-erase idiom is generally an effective approach.

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}
17

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: 135456
2

The remove_if algorithm returns a subrange of our original container. The subrange will be 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}
23

1Objects in Source: 135456
2Objects to Erase:  456
3

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}
20

1Objects in Source: 135
2

std::ranges::remove_copy

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

The algorithm copies objects from the source range to the destination range but omits any elements that pass an equality check with the comparison object.

Below, we copy objects that are not equal to 3 - in other words, where Object == 3 will 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}
22

1Objects in Source: 123456
2Objects in Destination: 124560
3

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

• in - a past-the-end iterator for the source range
• out - a past-the-end iterator for the elements that were copied to the destination range

This return value may or may not be useful, depending on our specific needs. Below, we use it 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}
27

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

remove_copy has an optional 4th argument, which we can use for a projection function. Below, we adapt the previous example to include a function that projects objects to their absolute value before they are compared. As such, the algorithm removes both -3 and 3:

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 Projector{
10      [](int x) { return std::abs(x); }};
11
12  auto [in, out]{std::ranges::remove_copy(
13      Source, Destination.begin(), 3,
14      Projector)};
15
16  Destination.erase(out, Destination.end());
17
18  std::cout << "\nObjects in Destination: ";
19  for (auto Num : Destination) {
20    std::cout << Num << ", ";
21  }
22}
23

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

std::ranges::remove_copy_if

The remove_copy_if algorithm works in the same way as remove_copy - the only difference is the 3rd argument is a predicate function, rather than a comparison object.

Objects will be omitted from the destination if the predicate returns true when passed that object.

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}
24

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

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 - a past the end iterator for the source range
• out - a past-the-end iterator for the elements that were copied to the destination range

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, and then 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}
29

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

The std::ranges::remove_copy_if algorithm has an optional 4th parameter, which we can use to pass a projection function to. Below, we update our previous example to use both a predicate and projection function. The projector projects objects to their absolute value, and the predicate returns true if that projection is >= 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  auto Projector{
11      [](int x) { return std::abs(x); }};
12
13  auto [in, out]{std::ranges::remove_copy_if(
14      Source, Destination.begin(), Predicate,
15      Projector)};
16
17  Destination.erase(out, Destination.end());
18
19  std::cout << "Objects in Destination: ";
20  for (auto Num : Destination) {
21    std::cout << Num << ", ";
22  }
23}
24

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