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().
This lesson is part of the course:

Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

Free, Unlimited Access
Abstract art representing computer programming
Ryan McCombe
Ryan McCombe
Updated

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:

#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:

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
  std::vector Source{1, 2, 3, 3, 3, 4, 5};

  std::cout << "Original: ";
  for (auto Num : Source) {
    std::cout << Num << ", ";
  }

  std::ranges::replace(Source, 3, 0);

  std::cout << "\nAfter Replacement: ";
  for (auto Num : Source) {
    std::cout << Num << ", ";
  }
}
Original: 1, 2, 3, 3, 3, 4, 5, 
After 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.

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

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
  std::vector Source{1, 2, 3, 3, 3, 4, 5};

  auto Result{
      std::ranges::replace(Source, 3, 0)};

  std::cout << "Objects in Source: ";
  for (auto Num : Source) {
    std::cout << Num << ", ";
  }
  
  std::cout << "\nSize of range: "
    << std::distance(Source.begin(), Result);

  std::cout << "\nLast Element in Range: "
    << *(Result - 1);
}
Objects in Source: 1, 2, 0, 0, 0, 4, 5,
Size of range: 7
Last 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:

#include <algorithm>
#include <iostream>
#include <vector>

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

  auto isEven{[](int x) { return x % 2 == 0; }};

  std::ranges::replace_if(Source, isEven, 0);

  std::cout << "Objects in Source: ";
  for (auto Num : Source) {
    std::cout << Num << ", ";
  }
}
Objects 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:

#include <algorithm>
#include <iostream>
#include <vector>

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

  auto isEven{[](int x) { return x % 2 == 0; }};

  auto End{std::ranges::replace_if(
      Source, isEven, 0)};

  std::cout << "Objects in Source: ";
  for (auto Num : Source) {
    std::cout << Num << ", ";
  }
  std::cout << "\nSource Size: "
    << std::distance(Source.begin(), End);
  std::cout << "\nLast Element in Range: "
    << *(End - 1);
}
Objects in Source: 1, 0, 3, 0, 5, 0,
Source Size: 6
Last 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:

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:

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
  std::vector Source{0, 1, 2, 3, 4, 5, 6};
  std::vector<int> Destination;
  Destination.resize(Source.size());

  std::ranges::replace_copy(
      Source, Destination.begin(), 3, 0);

  std::cout << "Objects in Source: ";
  for (auto Num : Source) {
    std::cout << Num << ", ";
  }

  std::cout << "\nObjects in Destination: ";
  for (auto Num : Destination) {
    std::cout << Num << ", ";
  }
}
Objects in Source: 0, 1, 2, 3, 4, 5, 6, 
Objects 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:

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
  std::vector Source{0, 1, 2, 3, 4, 5, 6};
  std::vector<int> Destination;
  Destination.resize(Source.size());

  auto [in, out]{std::ranges::replace_copy(
      Source, Destination.begin(), 3, 0)};

  std::cout << "Objects in Source: ";
  for (auto Num : Source) {
    std::cout << Num << ", ";
  }

  std::cout << "\nObjects in Destination: ";
  for (auto Num : Destination) {
    std::cout << Num << ", ";
  }

  std::cout
      << "\nThe last object in the source is: "
      << *(in - 1);
  std::cout << "\nThe last object in the "
               "destination is: "
            << *(out - 1);
}
Objects in Source: 0, 1, 2, 3, 4, 5, 6, 
Objects in Destination: 0, 1, 2, 0, 4, 5, 6, 
The last object in the source is: 6
The last object in the destination is: 6

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:

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
  std::vector Source{0, 1, 2, 3, 4, 5, 6};
  std::vector<int> Destination;
  Destination.resize(Source.size());

  auto isEven{[](int x) { return x % 2 == 0; }};

  std::ranges::replace_copy_if(
      Source, Destination.begin(), isEven, 0);

  std::cout << "Objects in Source: ";
  for (auto Num : Source) {
    std::cout << Num << ", ";
  }

  std::cout << "\nObjects in Destination: ";
  for (auto Num : Destination) {
    std::cout << Num << ", ";
  }
}
Objects in Source: 0, 1, 2, 3, 4, 5, 6, 
Objects 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:

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
  std::vector Source{0, 1, 2, 3, 4, 5, 6};
  std::vector<int> Destination;
  Destination.resize(Source.size());

  auto isEven{[](int x) { return x % 2 == 0; }};

  auto [in, out]{std::ranges::replace_copy_if(
      Source, Destination.begin(), isEven, 0)};

  std::cout << "Objects in Source: ";
  for (auto Num : Source) {
    std::cout << Num << ", ";
  }

  std::cout << "\nObjects in Destination: ";
  for (auto Num : Destination) {
    std::cout << Num << ", ";
  }

  std::cout
      << "\nThe last object in the source is: "
      << *(in - 1);
  std::cout << "\nThe last object in the "
               "destination is: "
            << *(out - 1);
}
Objects in Source: 0, 1, 2, 3, 4, 5, 6, 
Objects in Destination: 0, 1, 0, 3, 0, 5, 0, 
The last object in the source is: 6
The 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.

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:

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
  std::vector Source{-3, -2, -1, 0, 1, 2, 3};

  auto Projector{
      [](int x) { return std::abs(x); }};

  std::ranges::replace(Source, 3, 0, Projector);

  std::cout << "Objects in Source: ";
  for (auto Num : Source) {
    std::cout << Num << ", ";
  }
}
Objects 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:

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
  std::vector Source{-3, -2, -1, 0, 1, 2, 3};
  std::vector<int> Destination;
  Destination.resize(Source.size());

  auto toAbs{[](int x) { return std::abs(x); }};
  auto lessThanTwo{[](int x) { return x < 2; }};

  std::ranges::replace_copy_if(
      Source, Destination.begin(), lessThanTwo,
      0, toAbs);

  std::cout << "Objects in Source: ";
  for (auto Num : Source) {
    std::cout << Num << ", ";
  }

  std::cout << "\nObjects in Destination: ";
  for (auto Num : Destination) {
    std::cout << Num << ", ";
  }
}
Objects in Source: -3, -2, -1, 0, 1, 2, 3,
Objects 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)":

#include <algorithm>
#include <iostream>
#include <vector>

class Player {
 public:
   std::string GetName() {
     return Name;
   }

   std::string Name{"(None)"};
};

int main() {
  std::vector<Player> Players;
  Players.emplace_back("Anna");
  Players.emplace_back("Robert");
  Players.emplace_back("Anna");

  std::vector<Player> Destination;
  Destination.resize(Players.size());

  std::ranges::replace_copy(
    Players, Destination.begin(), "Anna",
    Player{}, &Player::GetName);

  std::cout << "Objects in Source: ";
  for (auto P : Players) {
    std::cout << P.GetName() << ", ";
  }

  std::cout << "\nObjects in Destination: ";
  for (auto P : Destination) {
    std::cout << P.GetName() << ", ";
  }
}
Objects in Source: Anna, Robert, Anna,
Objects 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:

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
  std::vector Source{0, 0, 0, 0, 0, 0};

  std::cout << "Original: ";
  for (auto Num : Source) {
    std::cout << Num << ", ";
  }

  std::ranges::replace(
    Source.begin() + 1, Source.end() - 1, 0, 1);

  std::cout << "\nAfter Replacement: ";
  for (auto Num : Source) {
    std::cout << Num << ", ";
  }
}
Original: 0, 0, 0, 0, 0, 0,
After 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():

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
  std::vector Source{0, 0, 0, 0, 0, 0};

  std::cout << "Original: ";
  for (auto Num : Source) {
    std::cout << Num << ", ";
  }

  std::replace( Source.begin() + 1,
    Source.end() - 1, 0, 1);

  std::cout << "\nAfter Replacement: ";
  for (auto Num : Source) {
    std::cout << Num << ", ";
  }
}
Original: 0, 0, 0, 0, 0, 0,
After 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.

Was this lesson useful?

Next Lesson

Partition Algorithms

An introduction to partitions, and the C++ standard library algorithms that create them
Abstract art representing computer programming
Ryan McCombe
Ryan McCombe
Updated
Lesson Contents

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().

A computer programmer
This lesson is part of the course:

Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

Free, Unlimited Access
Standard Library Algorithms
A computer programmer
This lesson is part of the course:

Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

Free, unlimited access

This course includes:

  • 124 Lessons
  • 550+ Code Samples
  • 96% Positive Reviews
  • Regularly Updated
  • Help and FAQ
Next Lesson

Partition Algorithms

An introduction to partitions, and the C++ standard library algorithms that create them
Abstract art representing computer programming
Contact|Privacy Policy|Terms of Use
Copyright © 2024 - All Rights Reserved