Replacement Algorithms

In this lesson, we cover all four of the main C++ standard library algorithms for replacing objects within our containers. The functions we will cover are:

• replace() searches our range for specific values and replaces those objects with different values.
• replace_if() searches our range for values that satisfy a predicate and replaces those objects with different values.
• replace_copy() combines the copy() and replace() algorithms. It copies objects to a new location. If an object matches a specific value, we copy a different object instead.
• replace_copy_if() combines the copy() and replace_if() algorithms. It copies objects from one location to another. If an object satisfies a predicate function, we copy a different object instead.

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

1#include <algorithm>

std::ranges::replace()

The replace() algorithm searches through our container for specific objects. It replaces any matching objects with a different object. The basic usage of the algorithm has three parameters:

1. The range we want to run the algorithm on.
2. The objects we want to replace.
3. The object we want to replace them 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::cout << "Original: ";
9  for (auto Num : Source) {
10    std::cout << Num << ", ";
11  }
12
13  std::ranges::replace(Source, 3, 0);
14
15  std::cout << "\nAfter Replacement: ";
16  for (auto Num : Source) {
17    std::cout << Num << ", ";
18  }
19}

1Original: 1, 2, 3, 3, 3, 4, 5, 
2After Replacement: 1, 2, 0, 0, 0, 4, 5,

Return Value

The std::ranges::replace() function returns an iterator pointing to where the sentinel of our range was found. In the examples in this section, this is equivalent to Source.end(). However, when using ranges that are terminated by more dynamic sentinels, this return value is more useful.

Defining Ranges using Sentinels

An alternative way of defining ranges, and why we sometimes need to use them

Below, we use this return value for some follow-up operations:

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  
16  std::cout << "\nSize of range: "
17    << std::distance(Source.begin(), Result);
18
19  std::cout << "\nLast Element in Range: "
20    << *(Result - 1);
21}

1Objects in Source: 1, 2, 0, 0, 0, 4, 5,
2Size of range: 7
3Last Element in Range: 5

std::ranges::replace_if()

The replace_if() algorithm works similarly to replace(), except the elements to replace are determined by a predicate function, rather than an equality check. The basic usage of the algorithm involves three arguments:

1. The range to act upon
2. The predicate function that determines whether an object should be replaced
3. The object to replace those elements with

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.

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

1Objects in Source: 1, 0, 3, 0, 5, 0,

Return Type

Like replace(), the replace_if() function returns an iterator for our input range, pointing at where the sentinel was found. Below, we use this 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 isEven{[](int x) { return x % 2 == 0; }};
9
10  auto End{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 << "\nSource Size: "
18    << std::distance(Source.begin(), End);
19  std::cout << "\nLast Element in Range: "
20    << *(End - 1);
21}

1Objects in Source: 1, 0, 3, 0, 5, 0,
2Source Size: 6
3Last Element in Range: 0

std::ranges::replace_copy()

The replace_copy() algorithm combines the copy() algorithm with the replace() algorithm.

Specifically, objects will be copied from a source range to a destination. However, an equality check is performed before copying an object to determine if that object matches some value we provide.

If it does, we copy a different object instead, which we provide as an argument. The net effect of this is that objects are copied from the source to the destination. The source objects are left unmodified, but the destination object is left in a state as if we had run the replace() algorithm on it, after copying everything across.

We covered the copy() algorithm in detail in the previous section:

Copying Algorithms

An introduction to the 7 copying algorithms in the C++ standard library: copy(), copy_n(), copy_if(), copy_backward(), reverse_copy(), rotate_copy(), and unique_copy().

The most basic usage of the replace_copy() algorithm has 4 arguments:

1. A source range containing objects we want to copy
2. A destination iterator for the start of where we want the objects to be copied to
3. The value we want to replace within the destination
4. The value 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}

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

Return Type

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: an iterator for the input range, pointing at where the sentinel was found. In our previous example, this will be equivalent to Source.end()
• out: an iterator for the destination location, pointing beyond the last element that was copied

Below, we use structured binding to access the values of this returned object, and then use them for some example 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}

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

Structured Binding

This lesson introduces Structured Binding, a handy tool for quickly unpacking simple data structures

std::ranges::replace_copy_if()

replace_copy_if() works in the same way as replace_copy(), with the exception being that whether a value should be replaced in the destination is determined by a predicate function, rather than an equality check. The basic usage involves four arguments:

1. A source range containing objects we want to copy
2. A destination iterator for the start of where we want the objects to be copied to
3. The predicate function that determines if an object should be replaced
4. The value we want to replace it with

Each value in the input range is provided to the predicate function. If the predicate function returns false, the value is copied to the destination range. If the predicate function returns true, the value we provide as the fourth argument is copied to the destination range.

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}

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

Return Type

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

• in: an iterator for the input range, pointing to where the sentinel was found. In the previous example, this is equivalent to Source.begin()
• out: an iterator for the destination location, pointing beyond the last element was copied

The type is aliased to std::ranges::replace_copy_if_result. In the following example, we use this for some 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 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}

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

Projection

Like with many range-based algorithms, every function we covered in this section supports projection. If we provide a projection function, the objects in our source container will be passed to this function.

The return value of this function is used for any equality or predicate checks to determine which objects should be replaced.

Projection Functions

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

Example One

Below, we use a projection function with replace(), which projects values to their absolute value. Therefore, the algorithm finds the projection of both 3 and -3 to be equal to the second argument to replace(), that is 3. As a result, it therefore replaces both of them with the value we provide as the 3rd argument, 0:

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{
9      [](int x) { return std::abs(x); }};
10
11  std::ranges::replace(Source, 3, 0, Projector);
12
13  std::cout << "Objects in Source: ";
14  for (auto Num : Source) {
15    std::cout << Num << ", ";
16  }
17}

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

Example Two

In this example, we use the same absolute value projection function with std::ranges::replace_copy_if(). This causes the predicate function to receive these projections. The -3 and -2 values get projected to 3 and 2 respectively.

Neither of these projections is less than 2, so our predicate function returns false, causing them not to be replaced:

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}

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

Example Three

In this example, we use a member function as our projector within a replace_copy() algorithm. We project Player objects to their Name field, and then replace any objects where the projection equals "Anna" with a default constructed Player, which will have a Name of "(None)":

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

1Objects in Source: Anna, Robert, Anna,
2Objects in Destination: (None), Robert, (None),

Using Iterator-Sentinel Pairs

As with most range-based algorithms, all the functions in this section allow us to our range as an iterator-sentinel pair, rather than as a single argument. Below, we use this technique with the replace() algorithm to exclude the first and last object of a collection from being replaced:

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

1Original: 0, 0, 0, 0, 0, 0,
2After Replacement: 0, 1, 1, 1, 1, 0,

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 identifier, 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{0, 0, 0, 0, 0, 0};
7
8  std::cout << "Original: ";
9  for (auto Num : Source) {
10    std::cout << Num << ", ";
11  }
12
13  std::replace( Source.begin() + 1,
14    Source.end() - 1, 0, 1);
15
16  std::cout << "\nAfter Replacement: ";
17  for (auto Num : Source) {
18    std::cout << Num << ", ";
19  }
20}

1Original: 0, 0, 0, 0, 0, 0,
2After Replacement: 0, 1, 1, 1, 1, 0,

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

Summary

In this lesson, we explored the C++ standard library algorithms designed for replacing elements within containers. We learned:

• The functions replace(), replace_if(), replace_copy(), and replace_copy_if() allow for element replacement within containers.
• replace() and replace_if() modify the container in-place, while replace_copy() and replace_copy_if() create modified copies of the data.
• The replace() and replace_copy() algorithms use an equality check through the == operator to determine which objects to replace.
• The replace_if() and replace_copy_if() algorithms use a predicate function to determine which objects to replace.
• Projection functions can be used with these algorithms to operate on transformed elements.
• Iterator-sentinel pairs can specify subranges for more targeted operations, allowing replacements to be more precisely controlled.
• The differences between range-based algorithms and their iterator-based counterparts.

Next Lesson

Partition Algorithms

An introduction to partitions, and the C++ standard library algorithms that create them

ContinueView Course