C++ Copying Algorithms

In this lesson, we cover the most essential copying algorithms. We’ll cover the seven main algorithms for copying objects from one container to another: copy, copy_backward, rotate_copy, reverse_copy, copy_if, copy_n and unique_copy.

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

1#include <algorithm>
2

What it means for an object to be copied is defined by the copy semantics of its type. We cover copy semantics in more detail here:

Copy Semantics, Elision, and RVO

Learn how to implement copy semantics in C++, and take advantage of copy elision and return value optimization (RVO)

std::ranges::copy

The standard copy algorithm will copy every element from a source range to a new destination. The destination where elements will be copied to is defined by passing an iterator as the second argument.

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Source{1, 2, 3};
7  std::vector Destination{0, 0, 0, 0, 0, 0};
8
9  std::ranges::copy(Source, Destination.begin());
10
11  for (auto i : Destination) {
12    std::cout << i;
13  }
14}
15

1123000
2

We do not need to copy to the beginning of the container. We can provide an iterator that points anywhere:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Source{1, 2, 3};
7  std::vector Destination{0, 0, 0, 0, 0, 0};
8
9  std::ranges::copy(Source,
10                    Destination.begin() + 2);
11
12  for (auto i : Destination) {
13    std::cout << i;
14  }
15}
16

1001230
2

We are responsible for ensuring that the location the destination iterator points to has enough space to receive our copies.

The type returned from std::ranges::copy is a std::ranges::in_out_result which is commonly aliased to types like std::ranges::copy_result. This type has two fields:

• in: A past-the-end iterator for our input range
• out: A past-the-end iterator for the last element copied to our output range

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Source{1, 2, 3};
7  std::vector Destination{0, 0, 0, 0, 0, 0};
8
9  std::ranges::copy_result Result{
10      std::ranges::copy(Source,
11                        Destination.begin())};
12
13  int64_t InputSize{
14      std::distance(Source.begin(), Result.in)};
15
16  std::cout << "The input size was " << InputSize;
17
18  int64_t OutputPosition{std::distance(
19      Destination.begin(), Result.out - 1)};
20
21  std::cout << "\nThe last element copied is at "
22               "position "
23            << OutputPosition
24            << " in the destination";
25
26  std::cout << "\nIts value is "
27            << Destination[OutputPosition];
28}
29

1The input size was 3
2The last element copied is at position 2 in the destination
3Its value is 3
4

The std::ranges::in_out_result type supports structured binding for easier use:

1auto [in, out]{std::ranges::copy(
2      Source, Destination.begin())};
3

Iterator-Based Algorithms

In this lesson, we’re focusing on the versions of these algorithms that work with ranges, a C++20 feature.

Alternative versions of these algorithms work directly with iterators, rather than ranges.

These alternative functions are also in the <algorithm> library and can be used by excluding the ranges namespace from our identifier.

Below, we rewrite the first example to use std::copy instead of std::ranges::copy. Instead of passing the source as a range, we pass two iterators, representing the first and last element to copy:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Source{1, 2, 3};
7  std::vector Destination{0, 0, 0, 0, 0, 0};
8
9  std::copy(Source.begin(), Source.end(),
10            Destination.begin());
11
12  for (auto i : Destination) {
13    std::cout << i;
14  }
15}
16

1123000
2

std::ranges::copy_n

The std::ranges::copy_n algorithm copies a limited number of objects from a source range to a destination range. The function has 3 parameters:

• An iterator pointing to the beginning of the source range
• An integer, representing how many objects to copy
• An iterator pointing to the start of the destination range, where objects are to be 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  std::ranges::copy_n(Source.begin(), 4,
10                      Destination.begin());
11
12  for (auto i : Destination) {
13    std::cout << i;
14  }
15}
16

1123400
2

The std::ranges::copy_n algorithm returns a std::ranges::copy_n_result, which is an alias for std::ranges::in_out_result. This is a struct with two properties:

• in - a past-the-end iterator for the last element copied within the source range
• out - a past-the-end iterator for the last element copied within the destination range

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::copy_n(
10      Source.begin(), 4, Destination.begin())};
11
12  std::cout << "Values in Destination: ";
13  for (auto& Num : Destination) {
14    std::cout << Num;
15  }
16
17  std::cout
18      << "\nThe input iterator is at position "
19      << std::distance(Source.begin(), in);
20
21  std::cout << "\nThe output iterator is at "
22               "position "
23            << std::distance(
24                   Destination.begin(), out);
25
26  std::cout << "\nThe last element copied was "
27            << *(out - 1);
28}
29

1Values in Destination: 123400
2The input iterator is at position 4
3The output iterator is at position 4
4The last element copied was 4
5

std::ranges::copy_if

The std::ranges::copy_if algorithm works similarly to std::ranges::copy, but it accepts a predicate function as the third argument. Each object in the source range will be passed to the predicate, and it will be copied only if that predicate call returns true.

Below, we use std::ranges::copy_if to copy only the even numbers from the source range:

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<int> Destination;
8  Destination.resize(Source.size());
9
10  auto isEven{
11      [](const int& x) { return x % 2 == 0; }};
12
13  std::ranges::copy_if(
14      Source, Destination.begin(), isEven);
15
16  std::cout << "     Source: ";
17  for (auto i : Source) {
18    std::cout << i;
19  }
20
21  std::cout << "\nDestination: ";
22  for (auto i : Destination) {
23    std::cout << i;
24  }
25}
26

1Source:      123456
2Destination: 246000
3

The type returned from std::ranges::copy_if is a std::ranges::in_out_result which is aliased as std::ranges::copy_if_result. This type has two fields:

• in: A past-the-end iterator for our input range
• out: A past-the-end iterator for the last element copied to our output range

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<int> Destination;
8  Destination.resize(Source.size());
9
10  auto isEven{
11      [](const int& x) { return x % 2 == 0; }};
12
13  auto [in, out]{std::ranges::copy_if(
14      Source, Destination.begin(), isEven)};
15
16  std::cout << "     Source: ";
17  for (auto i : Source) {
18    std::cout << i;
19  }
20
21  std::cout << "\nDestination: ";
22  for (auto i : Destination) {
23    std::cout << i;
24  }
25
26  std::cout << "\nThe input had "
27            << std::distance(Source.begin(), in)
28            << " objects\n";
29
30  std::cout << "The output iterator is at "
31               "position "
32            << std::distance(
33                   Destination.begin(), out);
34
35  std::cout << "\nThe last element copied was "
36            << *(out - 1);
37}
38

1Source:      123456
2Destination: 246000
3The input had 6 objects
4The output iterator is at position 3
5The last element copied was 6
6

The std::ranges::copy_if algorithm additionally accepts an optional 4th argument, for a projection function. We copy projection in more detail in a dedicated lesson:

Projections and Algorithms

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

Below, we project our source integer to a day of the week. If the corresponding day of the week starts with “T”, we copy the integer:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Days{"Monday",    "Tuesday",
7                   "Wednesday", "Thursday",
8                   "Friday",    "Saturday",
9                   "Sunday"};
10  std::vector Source{0, 1, 2, 3, 4, 5, 6};
11  std::vector<int> Destination;
12  Destination.resize(Source.size());
13
14  auto startsWithT{[](const std::string& x) {
15    return x.starts_with("T");
16  }};
17
18  auto toDay{[&Days](const int& x) {
19    return Days[x];
20  }};
21
22  std::ranges::copy_if(Source,
23                       Destination.begin(),
24                       startsWithT, toDay);
25
26  std::cout << "     Source: ";
27  for (auto i : Source) {
28    std::cout << i;
29  }
30
31  std::cout << "\nDestination: ";
32  for (auto i : Destination) {
33    std::cout << i;
34  }
35}
36

1Source:      0123456
2Destination: 1300000
3

std::ranges::copy_backward

The copy_backward algorithm accepts a source input range, and an iterator pointing at where we want the copies to end.

Elements from the source are copied in reverse order, with the destination iterator also moving in reverse order. The effect of this is that the relative order of the source elements is maintained within the destination:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Source{1, 2, 3};
7  std::vector Destination{0, 0, 0, 0, 0, 0};
8
9  std::ranges::copy_backward(Source,
10                             Destination.end());
11
12  for (auto i : Destination) {
13    std::cout << i;
14  }
15}
16

1000123
2

Similar to copy, the copy_backward algorithm returns a std::ranges::in_out_result, with the same properties:

• in - A past-the-end iterator for the input range
• out - An iterator for the destination range, pointing to the last element moved.

The fact elements are copied from right to left does have an implication for the out iterator though. The last element copied will be the leftmost element, so the out iterator will point at that element within the destination range:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Source{1, 2, 3};
7  std::vector Destination{0, 0, 0, 0, 0};
8
9  auto [in, out]{std::ranges::copy_backward(
10      Source, Destination.end())};
11
12  std::cout << "Values in Destination: ";
13  for (auto& Num : Destination) {
14    std::cout << Num;
15  }
16
17  std::cout << "\nThe input had "
18            << std::distance(Source.begin(), in)
19            << " objects\n";
20
21  std::cout << "The output iterator is at "
22               "position "
23            << std::distance(
24                   Destination.begin(), out);
25
26  std::cout << "\nThe last element copied was "
27            << *out;
28}
29

1Values in Destination: 00123
2The input had 3 objects
3The output iterator is at position 2
4The last element copied was 1
5

std::ranges::reverse_copy

The reverse_copy algorithm accepts an input range and a destination iterator. The input range is copied from right to left, whilst the destination iterator moves forward. The effect of this is that the source elements are copied into the destination in reverse order:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Source{1, 2, 3};
7  std::vector Destination{0, 0, 0, 0, 0, 0};
8
9  std::ranges::reverse_copy(
10      Source, Destination.begin());
11
12  for (auto i : Destination) {
13    std::cout << i;
14  }
15}
16

1321000
2

The reverse_copy algorithm returns a struct with the type std::ranges::in_out_result. This type is aliased to std::ranges::reverse_copy_result. The output has two properties:

• in - A past-the-end iterator for the input range
• out - A past-the-end iterator for the copied input range, within the destination range

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Source{1, 2, 3};
7  std::vector Destination{0, 0, 0, 0, 0, 0};
8
9  auto [in, out] = std::ranges::reverse_copy(
10      Source, Destination.begin());
11
12  for (auto i : Destination) {
13    std::cout << i;
14  }
15
16  std::cout << "\nThe input had "
17            << std::distance(Source.begin(), in)
18            << " objects\n";
19
20  std::cout << "The output iterator is at "
21               "position "
22            << std::distance(
23                   Destination.begin(), out);
24
25  std::cout << "\nThe last element copied was "
26            << *(out - 1);
27}
28

1321000
2The input had 3 objects
3The output iterator is at position 3
4The last element copied was 1
5

std::ranges::rotate_copy

We can think of rotation as shifting everything left or right within a container. Objects that fall off the edge are rotated around to the opposite edge. For example, imagine we had this container:

1{1, 2, 3, 4, 5, 6}
2

Rotating the container by 1 step to the right would result in this:

1{6, 1, 2, 3, 4, 5}
2

Everything moved one step to the right. The 6 had no room to move right, so it rotated around to the start.

The rotate_copy algorithm combines a rotation and a copy. Elements from a source container are copied to a destination container, in a rotated order. The algorithm has three arguments:

• The source range where the objects are to be copied from
• An iterator pointing at the first object we want to copy - ie, this argument controls the amount of rotation
• An iterator pointing at where we should start copying objects to

Below, we tell rotate_copy we want the first object copied to be Source.end() - 1, which is the 6. Therefore, relative to the Source, the Destination receives the copies rotated by one position to the right:

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::rotate_copy(Source,
10                           Source.end() - 1,
11                           Destination.begin());
12
13  std::cout << "     Source: ";
14  for (auto i : Source) {
15    std::cout << i;
16  }
17
18  std::cout << "\nDestination: ";
19  for (auto i : Destination) {
20    std::cout << i;
21  }
22}
23

1     Source: 123456
2Destination: 612345
3

The rotate_copy algorithm returns a struct with the type std::ranges::in_out_result. This type is aliased to std::ranges::rotate_copy_result. The output has two properties:

• in - A past-the-end iterator for the input range
• out - A past-the-end iterator for the copied input range, within the destination range

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,
8                          0, 0, 0, 0};
9
10  auto [in, out]{std::ranges::rotate_copy(
11      Source, Source.end() - 1,
12      Destination.begin())};
13
14  for (auto i : Destination) {
15    std::cout << i;
16  }
17
18  std::cout << "\nThe input had "
19            << std::distance(Source.begin(), in)
20            << " objects\n";
21
22  std::cout << "The output iterator is at "
23               "position "
24            << std::distance(
25                   Destination.begin(), out);
26
27  std::cout << "\nThe last element copied was "
28            << *(out - 1);
29}
30

161234500
2The input had 6 objects
3The output iterator is at position 6
4The last element copied was 5
5

std::ranges::unique_copy

The unique_copy algorithm has a fairly niche use. It works similarly to std::ranges::copy, but will not copy any object that passed an equality check with the previous object.

For example, copying 1, 2, 2, 1 will yield 1, 2, 1. The second 2 is skipped as it was equal to the previous object in the original range. Only the first object in each group of equal objects will be copied. As such, copying 1, 2, 2, 2, 1 will also yield 1, 2, 1.

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

1Source:      11212222
2Destination: 12120000
3

The unique_copy algorithm returns a struct with the type std::ranges::in_out_result. This type is aliased to std::ranges::unique_copy_result. The output has two properties:

• in - A past-the-end iterator for the input range
• out - A past-the-end iterator for the copied input range, within the destination range

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Source{1, 1, 2, 1, 2, 2, 2, 2};
7  std::vector<int> Destination;
8  Destination.resize(Source.size());
9
10  auto [in, out]{std::ranges::unique_copy(
11      Source, Destination.begin())};
12
13  std::cout << "     Source: ";
14  for (auto i : Source) {
15    std::cout << i;
16  }
17
18  std::cout << "\nDestination: ";
19  for (auto i : Destination) {
20    std::cout << i;
21  }
22
23  std::cout << "\nThe input had "
24            << std::distance(Source.begin(), in)
25            << " objects\n";
26
27  std::cout << "The output iterator is at "
28               "position "
29            << std::distance(
30                   Destination.begin(), out);
31
32  std::cout << "\nThe last element copied was "
33            << *(out - 1);
34}
35

1     Source: 11212222
2Destination: 12120000
3The input had 8 objects
4The output iterator is at position 4
5The last element copied was 2
6