C++ Movement Algorithms

In this lesson, we cover the most important movement algorithms. We’ll cover the two main algorithms for moving objects between containers: move and move_backward.

We’ll also introduce 5 algorithms for moving elements around within their existing container: rotate, reverse, shuffle, shift_left and shift_right.

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

1#include <algorithm>
2

std::ranges::move

The std::ranges::move algorithm moves the objects from a source range into a destination range. We provide the source, and an iterator for the destination, denoting where we want the moved objects to be inserted:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Source{1, 2, 3};
7
8  std::vector Destination{0, 0, 0};
9
10  std::ranges::move(Source,
11                    Destination.begin());
12
13  std::cout << "Values in Destination:\n";
14  for (auto& Num : Destination) {
15    std::cout << Num;
16  }
17}
18

1Values in Destination:
2123
3

The std::ranges::move function returns a std::ranges::in_out_result, which is aliased to std::ranges::move_result. This is a struct with two properties:

• in - A past-the-end iterator for the input range
• out - A past-the-end iterator for the final source element, within the destination range

Depending on our requirements, this return value may be useful for some follow-up operations:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Source{1, 2, 3};
7
8  std::vector Destination{0, 0, 0, 0, 0};
9
10  auto [in, out]{std::ranges::move(
11      Source, Destination.begin() + 1)};
12
13  std::cout << "Values in Destination:\n";
14  for (auto& Num : Destination) {
15    std::cout << Num;
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

1Values in Destination:
201230
3The input had 3 objects
4The output iterator is at position 4
5

The std::ranges::move algorithm calls the movement assignment operator on each object. Therefore, what it means for an object to be “moved” is determined by that function within the object’s type.

Below, we define a custom type that contains a string, the minimal necessary constructors, and a movement assignment operator. Our operator copies the original object’s string to the new object, and then appends “Moved” to the original string:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5class Character {
6 public:
7  std::string Name;
8
9  Character() = default;
10  Character(std::string n) : Name(n) {}
11  Character(const Character& Original) =
12      default;
13
14  Character& operator=(
15      Character&& Original) noexcept {
16    if (&Original != this) {
17      Name = Original.Name;
18      Original.Name += " (Moved)";
19    }
20
21    return *this;
22  }
23};
24
25int main() {
26  using namespace std::string_literals;
27  std::vector<Character> Source{
28      "Legolas"s, "Gimli"s, "Gandalf"s};
29
30  std::vector<Character> Destination{
31      Source.size()};
32
33  std::ranges::move(Source,
34                    Destination.begin());
35
36  std::cout << "Characters in Source:\n";
37  for (auto& Character : Source) {
38    std::cout << Character.Name << "\n";
39  }
40
41  std::cout << "\nCharacters in Destination:\n";
42  for (auto& Character : Destination) {
43    std::cout << Character.Name << "\n";
44  }
45}
46

1Characters in Source:
2Legolas (Moved)
3Gimli (Moved)
4Gandalf (Moved)
5
6Characters in Destination:
7Legolas
8Gimli
9Gandalf
10

If the class code in the above example is unclear, our lesson on move semantics is likely to help:

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.

Iterator-Based Algorithms

In this lesson, we focus on the version fo these algorithms that work with C++20 ranges.

The std::ranges::move algorithm, and every other algorithm in this lesson, have an alternative variant that works directly with iterators instead of ranges. Rather than passing our source as a single range, we pass an iterator for where it begins, and an iterator for where it ends.

These functions are accessible by excluding the ranges namespace from our identifier.

Below, we rewrite the previous example to use std::move instead of std::ranges::move:

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

1Values in Destination: 123
2

std::ranges::move_backward

The std::ranges::move_backward algorithm works similarly to std::ranges::move, but we provide an iterator for where we want the input range to end in the destination.

The elements are then moved from right to left in the input range, to right to left in the destination range. This does not reverse the elements - we’ll cover the reverse algorithm later in this lesson.

With move_backward, the source elements maintain their relative order in 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  std::ranges::move_backward(Source,
10                             Destination.end());
11
12  std::cout << "Values in Destination: ";
13  for (auto& Num : Destination) {
14    std::cout << Num;
15  }
16}
17

1Values in Destination: 00123
2

The std::ranges::move_backward algorithm returns a std::ranges::in_out_result, which has the following properties:

• in - A past-the-end iterator for the input range
• out - An iterator for the destination range, pointing to the last element moved. Given elements are moved from right to left, this will correspond to the leftmost element in the input range.

Depending on our requirements, these values may be useful for follow-up operations after we’ve completed the move:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Source{1, 2, 3};
7
8  std::vector Destination{0, 0, 0, 0, 0};
9
10  auto [in, out]{std::ranges::move_backward(
11      Source, Destination.end())};
12
13  std::cout << "Values in Destination: ";
14  for (auto& Num : Destination) {
15    std::cout << Num;
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 moved was "
28            << *out;
29}
30

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

std::ranges:rotate

Sometimes, the things we’re trying to model in our containers are cyclic structures. Take, for example, the days of the week:

1std::vector Days{"Mon", "Tue", "Wed", "Thu",
2                 "Fri", "Sat", "Sun"};
3

The last day in our container is Sunday - nothing comes after it. But, in the real world, what comes after Sunday is another Monday. So, to model this cycle, we can imagine our container wrapped around a cylinder, such that the start and end of our containers are connected. Sunday is next to Monday, forming an endless cycle.

With this in mind, we can begin to imagine what it means to rotate a container. If we rotate our days of the week by one position to the right, every element moves one step right, with Sunday wrapping around to now be the first element in our container.

1std::vector Days{"Sun", "Mon", "Tue", "Wed",
2                 "Thu", "Fri", "Sat"};
3

The algorithm that does this for us is called std::ranges::rotate. It accepts two arguments - the range we want to rotate, and an iterator pointing at what will become the new first element in the range.

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Days{"Mon", "Tue", "Wed", "Thu",
7                   "Fri", "Sat", "Sun"};
8
9  std::ranges::rotate(Days, Days.end() - 1);
10
11  for (auto& Day : Days) {
12    std::cout << Day << ", ";
13  }
14}
15

1Sun, Mon, Tue, Wed, Thu, Fri, Sat,
2

std::ranges::rotate returns a subrange view of the original range. The subrange begins at the original starting element from before the rotation (which is Mon, in this example) and ends at the end of the container.

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Days{"Mon", "Tue", "Wed", "Thu",
7                   "Fri", "Sat", "Sun"};
8
9  auto Subrange{std::ranges::rotate(
10      Days, Days.end() - 1)};
11
12  for (auto& Day : Days) {
13    std::cout << Day << ", ";
14  }
15
16  std::cout << "Subrange has "
17            << Subrange.size() << " elements ("
18            << Subrange.front() << " - "
19            << Subrange.back() << ")";
20}
21

1Sun, Mon, Tue, Wed, Thu, Fri, Sat,
2Subrange has 6 elements (Mon - Sat)
3

std::ranges::reverse

The std::ranges::reverse algorithm will reverse the order of the elements in a collection, in place:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Numbers{1, 2, 3, 4, 5};
7
8  std::ranges::reverse(Numbers);
9
10  std::cout << "Numbers: ";
11  for (auto& Num : Numbers) {
12    std::cout << Num;
13  }
14}
15

1Numbers: 54321
2

The reverse algorithm achieves this by swapping elements in symmetrical positions about the center. For example, it swaps the first and the last, then the second and second-from-last, and so on.

Because of this, our type needs to be copyable or movable both by the = operator and constructor. Swapping will prefer to move semantics where available, but will copy if movement semantics aren’t implemented.

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5struct MyStruct {
6  int Value;
7
8  MyStruct(int x) : Value{x} {};
9
10  // Copy constructor
11  MyStruct(const MyStruct& Source) = default;
12
13  // Move constructor
14  MyStruct(const MyStruct&& Source)
15      : Value{Source.Value} {};
16
17  // Move operator
18  MyStruct& operator=(const MyStruct&& Source) {
19    Value = Source.Value;
20    return *this;
21  }
22};
23
24int main() {
25  std::vector Numbers{MyStruct{1}, MyStruct{2},
26                      MyStruct{3}};
27
28  std::ranges::reverse(Numbers);
29
30  std::cout << "Numbers: ";
31  for (auto& Num : Numbers) {
32    std::cout << Num.Value;
33  }
34}
35

1Numbers: 321
2

std::ranges::shuffle

The std::ranges::shuffle algorithm reorders objects in a container into a random order.

To use this algorithm, we need to provide a random number generator (RNG).

We covered randomness and RNG in a dedicated lesson:

Using Randomness in C++

Explore how we can add randomness to our program, so the outcome isn't always the same

The shuffle algorithm has two arguments - the container to shuffle, and the RNG engine to use:

1#include <algorithm>
2#include <iostream>
3#include <random>
4#include <vector>
5
6int main() {
7  std::vector Range{1, 2, 3, 4, 5, 6};
8
9  std::random_device Device;
10  std::mt19937 Generator{Device()};
11
12  std::ranges::shuffle(Range, Generator);
13
14  std::cout << "Shuffled Numbers: ";
15  for (auto& Num : Range) {
16    std::cout << Num;
17  }
18}
19

1Shuffled Numbers: 613542
2

The shuffle algorithm is based on swapping elements, so has the same requirements and properties as std::ranges::reverse, covered earlier.

std::ranges::shift_left (C++23)

Note: std::ranges::shift_left is a recent addition to the language, and is not yet available on all compilers.

The std::ranges::shift_left algorithm moves all the elements in a range to the left by a specific number of steps, defined by the second argument:

1// Move everything left by two steps
2std::ranges::shift_left(Range, 2);
3

When we shift a range left by 2 steps, as in the previous example, the first 2 elements of the range are overwritten, and the last 2 elements are left in their “moved-from” state:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Range{1, 2, 3, 4, 5, 6};
7
8  std::ranges::shift_left(Range, 2);
9
10  std::cout << "Numbers: ";
11  for (auto& Num : Range) {
12    std::cout << Num;
13  }
14}
15

For integers, the moved-from state continues to contain their previous values, so our range continues to end with 5 and 6 in the previous example:

1Numbers: 345656
2

Below, we’ve defined a custom type that implements move semantics such that a moved-from object has a value of 0:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5struct MyStruct {
6  int Value;
7
8  MyStruct(int x) : Value{x} {};
9
10  MyStruct(const MyStruct& Source) = default;
11
12  MyStruct& operator=(
13      MyStruct&& Source) noexcept {
14    Value = Source.Value;
15    Source.Value = 0;
16    return *this;
17  }
18};
19
20int main() {
21  std::vector Range{MyStruct{1}, MyStruct{2},
22                    MyStruct{3}, MyStruct{4},
23                    MyStruct{5}, MyStruct{6}};
24
25  std::ranges::shift_left(Range, 1);
26  std::cout << "Numbers: ";
27  for (auto& Num : Range) {
28    std::cout << Num.Value;
29  }
30}
31

1Numbers: 345600
2

The std::ranges::shift_left algorithm returns a subrange view that excludes the moved-from elements, which will be on the right edge of the container:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Range{1, 2, 3, 4, 5, 6};
7
8  auto Subrange{
9      std::ranges::shift_left(Range, 2)};
10
11  std::cout << "Original Range: ";
12  for (auto& Num : Range) {
13    std::cout << Num;
14  }
15
16  std::cout << "\nReturned Subrange: ";
17  for (auto& Num : Subrange) {
18    std::cout << Num;
19  }
20}
21

1Original Range: 345656
2Returned Subrange: 3456
3

std::ranges::shift_right (C++ 23)

Note: std::ranges::shift_right is a recent addition to the language and is not yet available on all compilers.

The shift_right algorithm works in the same way as shift_left, covered above. Elements are simply moved in the opposite direction. This means values on the right edge of the container will be overwritten. Values on the left edge will be left in a moved-from state, and excluded in the returned subrange:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Range{1, 2, 3, 4, 5, 6};
7
8  auto Subrange{
9      std::ranges::shift_right(Range, 2)};
10
11  std::cout << "Original Range: ";
12  for (auto& Num : Range) {
13    std::cout << Num;
14  }
15
16  std::cout << "\nReturned Subrange: ";
17  for (auto& Num : Subrange) {
18    std::cout << Num;
19  }
20}
21

1Original Range: 121234
2Returned Subrange: 1234
3