replace
, replace_if
, replace_copy
, replace_copy_if
, remove
, remove_if
, remove_copy
, and remove_copy_if
.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:
#include <algorithm>
std::ranges::replace
The replace
algorithm has 3Â parameters:
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::ranges::replace(Source, 3, 0);
std::cout << "Objects in Source: ";
for (auto Num : Source) {
std::cout << Num;
}
}
Objects in Source: 1200045
std::ranges::replace
returns a past-the-end iterator for the input range:
#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 << "\nLast Element in Range: "
<< *(Result - 1);
}
Objects in Source: 1200045
Last Element in Range: 5
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
:
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector Source{1, 2, 3, 3, 3, 4, 5};
std::replace(Source.begin(), Source.end(), 3,
0);
std::cout << "Objects in Source: ";
for (auto Num : Source) {
std::cout << Num;
}
}
Objects in Source: 1200045
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
:
#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 Result{std::ranges::replace_if(
Source, isEven, 0)};
std::cout << "Objects in Source: ";
for (auto Num : Source) {
std::cout << Num;
}
std::cout << "\nLast Element in Range: "
<< *(Result - 1);
}
Objects in Source: 103050
Last Element in Range: 0
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:
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
:
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<std::string> Days{
"Monday", "Tuesday", "Wednesday",
"Thursday", "Friday", "Saturday",
"Sunday"};
std::vector Source{0, 1, 2, 3, 4, 5, 6};
auto Projector{
[&Days](int x) { return Days[x]; }};
auto Predicate{[](const std::string& d) {
return d.starts_with('S');
}};
auto Result{std::ranges::replace_if(
Source, Predicate, 0, Projector)};
std::cout << "Objects in Source: ";
for (auto Num : Source) {
std::cout << Num;
}
std::cout << "\nLast Element in Range: "
<< *(Result - 1);
}
Objects in Source: 0123400
Last Element in Range: 0
std::ranges::replace_copy
The replace_copy
algorithm has 4Â arguments:
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: 0123456
Objects in Destination: 0120456
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 rangeout
: a past-the-end iterator for the destination rangeThis return value may or may not be useful, depending on whether we need to perform any 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: 0123456
Objects in Destination: 0120456
The last object in the source is: 6
The last object in the destination is: 6
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
:
#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 Projector{
[](int x) { return std::abs(x); }};
std::ranges::replace_copy(Source,
Destination.begin(),
3, 0, Projector);
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: 0, -2, -1, 0, 1, 2, 0,
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:
#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: 0123456
Objects in Destination: 0103050
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 rangeout
: a past-the-end iterator for the destination rangeThe type is aliased to std::ranges::replace_copy_if_result
. Here is an example of it in use:
#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: 0123456
Objects in Destination: 0103050
The last object in the source is: 6
The last object in the destination is: 0
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
:
#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,
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 3
s:
std::vector Source{1, 2, 3, 4, 5, 6};
std::ranges::remove(Source, 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:
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector Source{1, 2, 3, 4, 5, 6};
std::ranges::remove(Source, 3);
std::cout << "Objects in Source: ";
for (auto Num : Source) {
std::cout << Num;
}
}
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
Objects in Source: 124566
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:
std::ranges::remove
returns a subrange, that contains all the surplus elements on the right of the container.
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector Source{1, 2, 3, 4, 5, 6};
auto ObjectsToErase{
std::ranges::remove(Source, 3)};
std::ranges::subrange ObjectsToKeep{
Source.begin(), ObjectsToErase.begin()};
std::cout << "Objects to Keep: ";
for (auto Num : ObjectsToKeep) {
std::cout << Num;
}
std::cout << "\nObjects to Erase: ";
for (auto Num : ObjectsToErase) {
std::cout << Num;
}
}
Objects to Keep: 12456
Objects to Erase: 6
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:
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector Source{1, 2, 3, 3, 3, 4, 5};
auto [start,
end]{std::ranges::remove(Source, 3)};
Source.erase(start, end);
std::cout << "Objects in Source: ";
for (auto Num : Source) {
std::cout << Num;
}
}
Objects in Source: 1245
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.
#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::remove_if(Source, isEven);
std::cout << "Objects in Source: ";
for (auto Num : Source) {
std::cout << Num;
}
}
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:
Objects in Source: 135456
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:
#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 Result{
std::ranges::remove_if(Source, isEven)};
std::cout << "Objects in Source: ";
for (auto Num : Source) {
std::cout << Num;
}
std::cout << "\nObjects to Erase: ";
for (auto Num : Result) {
std::cout << Num;
}
}
Objects in Source: 135456
Objects to Erase: 456
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:
#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 [begin, end]{
std::ranges::remove_if(Source, isEven)};
Source.erase(begin, end);
std::cout << "Objects in Source: ";
for (auto Num : Source) {
std::cout << Num;
}
}
Objects in Source: 135
std::ranges::remove_copy
In its typical usage, the std::ranges::remove_copy
algorithm has three arguments:
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
:
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector Source{1, 2, 3, 4, 5, 6};
std::vector Destination{0, 0, 0, 0, 0, 0};
std::ranges::remove_copy(
Source, Destination.begin(), 3);
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: 123456
Objects in Destination: 124560
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 rangeout
- a past-the-end iterator for the elements that were copied to the destination rangeThis 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:
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector Source{1, 2, 3, 4, 5, 6};
std::vector Destination{0, 0, 0, 0, 0, 0};
auto [in, out]{std::ranges::remove_copy(
Source, Destination.begin(), 3)};
std::cout << "The source had "
<< std::distance(Source.begin(), in)
<< " elements.\n";
std::cout << std::distance(
Destination.begin(), out)
<< " elements were copied.";
Destination.erase(out, Destination.end());
std::cout << "\nObjects in Destination: ";
for (auto Num : Destination) {
std::cout << Num;
}
}
The source had 6 elements.
5 elements were copied.
Objects in Destination: 12456
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
:
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector Source{-3, -2, -1, 0, 1, 2, 3};
std::vector Destination{0, 0, 0, 0, 0, 0, 0};
auto Projector{
[](int x) { return std::abs(x); }};
auto [in, out]{std::ranges::remove_copy(
Source, Destination.begin(), 3,
Projector)};
Destination.erase(out, Destination.end());
std::cout << "\nObjects in Destination: ";
for (auto Num : Destination) {
std::cout << Num << ", ";
}
}
Objects in Destination: -2, -1, 0, 1, 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
:
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector Source{-3, -2, -1, 0, 1, 2, 3};
std::vector Destination{0, 0, 0, 0, 0, 0, 0};
auto Predicate{[](int x) { return x >= 2; }};
std::ranges::remove_copy_if(
Source, Destination.begin(), Predicate);
std::cout << "\nObjects 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, -1, 0, 1, 0, 0,
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 rangeout
- a past-the-end iterator for the elements that were copied to the destination rangeThis 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:
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector Source{-3, -2, -1, 0, 1, 2, 3};
std::vector Destination{0, 0, 0, 0, 0, 0, 0};
auto Predicate{[](int x) { return x >= 2; }};
auto [in, out]{std::ranges::remove_copy_if(
Source, Destination.begin(), Predicate)};
std::cout << "The source had "
<< std::distance(Source.begin(), in)
<< " elements.\n";
std::cout << std::distance(
Destination.begin(), out)
<< " elements were copied.";
Destination.erase(out, Destination.end());
std::cout << "\nObjects in Destination: ";
for (auto Num : Destination) {
std::cout << Num << ", ";
}
}
The source had 7 elements.
5 elements were copied.
Objects in Destination: -3, -2, -1, 0, 1,
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
:
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector Source{-3, -2, -1, 0, 1, 2, 3};
std::vector Destination{0, 0, 0, 0, 0, 0, 0};
auto Predicate{[](int x) { return x >= 2; }};
auto Projector{
[](int x) { return std::abs(x); }};
auto [in, out]{std::ranges::remove_copy_if(
Source, Destination.begin(), Predicate,
Projector)};
Destination.erase(out, Destination.end());
std::cout << "Objects in Destination: ";
for (auto Num : Destination) {
std::cout << Num << ", ";
}
}
Objects in Destination: -1, 0, 1,
Comprehensive course covering advanced concepts, and how to use them on large-scale projects.