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>

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}

1Values in Destination:
21, 2, 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 - Where the sentinel was encountered for the input range. In the previous example, this would be equivalent to Source.end()
• out - An iterator for the destination container, pointing at the position after that last element that was moved

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               "index "
24            << std::distance(
25                   Destination.begin(), out);
26}

1Values in Destination:
20, 1, 2, 3, 0,
3The input had 3 objects
4The output iterator is at index 4

Controlling Move Semantics

The std::ranges::move() algorithm, and the other algorithms in this lesson, require our types to have implemented move semantics. We covered this in more detail earlier in the course:

Move Semantics

Learn how we can improve the performance of our types using move constructors, move assignment operators and std::move()

What it means for an object to be "moved" is defined by the functions we implement as part of that process.

Below, we define a custom Player type that contains a string representing its name. Our movement assignment operator copies that string to the new object, and then appends "Moved" to the original player’s name, indicating that the object is in the "moved from" state:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
Player Class|Show
5class Player {/*...*/};
24
25int main() {
26  using namespace std::string_literals;
27  std::vector<Player> Source{
28      "Anna"s, "Roderick"s, "Robert"s};
29
30  std::vector<Player> Destination{
31      Source.size()};
32
33  std::ranges::move(Source,
34                    Destination.begin());
35
36  std::cout << "Players in Source:\n";
37  for (auto& Player : Source) {
38    std::cout << Player.Name << "\n";
39  }
40
41  std::cout << "\nPlayers in Destination:\n";
42  for (auto& Player : Destination) {
43    std::cout << Player.Name << "\n";
44  }
45}

1Players in Source:
2Anna (Moved)
3Roderick (Moved)
4Robert (Moved)
5
6Players in Destination:
7Anna
8Roderick
9Robert

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, and right to left in the destination range. The net effect of this maintains the relative order of the elements - it does not reverse the elements. We’ll cover the reverse() algorithm later in this lesson.

Given move_backward() traverses containers in reverse order, they require our input range and output iterator to be bidirectional.

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}

1Values in Destination: 0, 0, 1, 2, 3,

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

• in - A iterator pointing to where the sentinel was found in the input range. In the previous example, this will be equivalent to Source.end()
• 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}

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

What’s the point of move_backward()?

It seems the previous behavior could have been implemented with the move() algorithm and, when moving objects to a different container, that is true.

The reason we have both a move() and a move_backward() algorithm is to deal with scenarios where our destination range overlaps with our input range. This typically happens when we’re trying to move objects within the same container.

However, if our destination iterator is within our input range, the behavior of both move() and move_backward() is undefined.

In the following example, we have the collection {1, 2, 3, 0, 0}. We’d like to move the 1, 2, and 3 by two positions to the right, giving us {0, 0, 1, 2, 3}. If we try this with move(), our destination iterator will be within our input range, leading to undefined behavior:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
T Struct|Show
5struct T {/*...*/};
18
19int main() {
20  std::vector<T> Values{
21    T{1}, T{2}, T{3}, T{0}, T{0}};
22
23  std::ranges::move(
24    Values.begin(),
25    Values.begin() + 3,
26   // Undefined behaviour - this
27   // destination is within the input range
28    Values.begin() + 2);
29
30  for (T& x : Values) {
31    std::cout << x.Value << ", ";
32  }
33}

The result is not exactly what we had in mind:

10, 0, 0, 2, 1,

The first step of this process involves moving the 1 by two positions to the right. But this overwrites the 3, a value which we haven’t moved yet. We then move the 2 successfully, and finally, we move the 3, which is now a 1, to the end of our destination.

In this situation, we should use move_backward(). Now, our destination iterator will be outside of our input range, giving us exactly what we want:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
T Struct|Show
5struct T {/*...*/};
18
19int main() {
20  std::vector<T> Values{
21    T{1}, T{2}, T{3}, T{0}, T{0}};
22
23  std::ranges::move_backward(
24    Values.begin(),
25    Values.begin() + 3,
26    // This is better - the destination is no
27    // longer within the input range
28    Values.end());
29
30  for (T& x : Values) {
31    std::cout << x.Value << ", ";
32  }
33}

10, 0, 1, 2, 3,

There is a simple guideline to avoid the undefined behavior of our destination being within our range when moving objects within a container:

• If we’re moving objects left, use move()
• If we’re moving objects right, use move_backward()

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"};

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"};

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.

Below, we rotate our container such that the element at Days.end() - 1 - that is "Sun" - becomes the new first element:

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}

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

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}

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

Creating Views using std::ranges::subrange

This lesson introduces std::ranges::subrange, allowing us to create non-owning ranges that view some underlying container

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}

1Numbers: 5, 4, 3, 2, 1,

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, the reverse() algorithm will use a swap() function, if a suitable candidate is found:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5struct T {
6  int Value;
7};
8
9void swap(T& A, T& B) {     
10  std::cout << "Swapping " << A.Value       
11            << " and " << B.Value << '\n';  
12  std::swap(A.Value, B.Value);              
13}  
14
15int main() {
16  std::vector Numbers{
17    T{1}, T{2}, T{3}, T{4}, T{5}};
18
19  std::ranges::reverse(Numbers);
20
21  std::cout << "Numbers: ";
22  for (auto& Num : Numbers) {
23    std::cout << Num.Value << ", ";
24  }
25}

1Swapping 1 and 5
2Swapping 2 and 4
3Numbers: 5, 4, 3, 2, 1,

Otherwise, it will fall back to using move semantics where available, or copy semantics otherwise.

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:

Random Number Generation

This lesson covers the basics of using randomness, with practical applications

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}

1Shuffled Numbers: 6, 1, 3, 5, 4, 2,

The shuffle() algorithm is based on swapping elements, so has the same characteristics as std::ranges::reverse(), covered earlier.

std::ranges::shift_left()

Note: std::ranges::shift_left() is a recent addition to the language, added in C++23, 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);

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}

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: 3, 4, 5, 6, 5, 6,

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
T Struct|Show
5struct T {/*...*/};
17
18int main() {
19  std::vector Range{
20    T{1}, T{2}, T{3}, T{4}, T{5}, T{6}};
21
22  std::ranges::shift_left(Range, 1);
23  std::cout << "Numbers: ";
24  for (auto& Num : Range) {
25    std::cout << Num.Value << ", ";
26  }
27}

1Numbers: 3, 4, 5, 6, 0, 0,

Return Type

The std::ranges::shift_left() algorithm returns a subrange view that excludes the moved-from elements on the right edge of the container:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
T Struct|Show
5struct T {/*...*/};
17
18int main() {
19  std::vector Range{
20    T{1}, T{2}, T{3}, T{4}, T{5}, T{6}};
21
22  auto Subrange{
23    std::ranges::shift_left(Range, 2)};
24
25  std::cout << "Original Range: ";
26  for (T& Object : Range) {
27    std::cout << Object.Value << ", ";
28  }
29
30  std::cout << "\nReturned Subrange: ";
31  for (T& Object : Subrange) {
32    std::cout << Object.Value << ", ";
33  }
34}

1Original Range: 3, 4, 5, 6, 5, 6,
2Returned Subrange: 3, 4, 5, 6,

std::ranges::shift_right()

Note: std::ranges::shift_right() is a recent addition to the language, added in C++23, 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}

1Original Range: 1, 2, 1, 2, 3, 4,
2Returned Subrange: 1, 2, 3, 4,

Using Sentinels

As with most range-based algorithms, we have the option of providing our range as an iterator-sentinel pair, rather than a single argument.

Below, we use this technique with std::ranges::reverse() to reverse the elements in a container, excluding the first and last objects:

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(
9    Numbers.begin() + 1, Numbers.end() - 1);
10
11  std::cout << "Numbers: ";
12  for (auto& Num : Numbers) {
13    std::cout << Num << ", ";
14  }
15}

1Numbers: 1, 4, 3, 2, 5,

Movement Algorithms Pre-C++20

In this lesson, we focus on the version of these algorithms that work with ranges, a language feature added in C++20. The std::ranges::move() algorithm, and every other algorithm in this lesson, have implementations that are available in older specifications.

These variations work directly with iterators and are available by excluding the ranges qualification from our identifier. For example, instead of std::ranges::move(), we can use std::move():

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};
8
9  std::move(Source.begin(), Source.end(),
10            Destination.begin());
11
12  std::cout << "Values in Destination: ";
13  for (auto& Num : Destination) {
14    std::cout << Num << ", ";
15  }
16}

1Values in Destination: 1, 2, 3,

Isn’t std::move() for creating rvalue references?

The previous example may be confusing, as we’ve seen std::move() used for a completely different purpose in other contexts. These are two different functions that just happen to have the same name.

The std::move() in the <utility> header, which we introduced in our lessons on memory management, is for casting objects to an rvalue reference, indicating they are safe to be "moved from". We covered this concept in our lesson on move semantics.

Move Semantics

Learn how we can improve the performance of our types using move constructors, move assignment operators and std::move()

The std::move() in the <algorithm> header, which we’ve shown above, is for moving a collection of objects to another container

Even when both functions are in scope, they require a different number of arguments, so it’s generally obvious which one we’re using. The std::move() within <utility> accepts a single argument, whilst the std::move() within <algorithm> requires multiple arguments.

Summary

In this lesson, we explored the main movement algorithms within the C++ standard library, and how they interact with any move semantics we have defined on our type.

Main Points Learned

• Introduction to the seven key movement algorithms in C++: move(), move_backward(), rotate(), reverse(), shuffle(), shift_left(), and shift_right().
• Detailed examination of std::ranges::move() and std::ranges::move_backward(), including their syntax, usage, and their return values.
• Exploration of std::ranges::rotate() for cyclically shifting elements in a container, and how to determine the new first element.
• Discussion on std::ranges::reverse() for in-place reversal of container elements, and its reliance on swap() or move semantics.
• Using std::ranges::shuffle() for randomizing the order of elements with the help of a random number generator.
• Introduction to C++23 additions std::ranges::shift_left() and std::ranges::shift_right(), focusing on their role in shifting elements within a container.
• Using iterator-sentinel pairs with range-based algorithms for more precise control over the operations.
• The distinction between the std::move() in <algorithm> and the std::move() in <utility>.

Next Lesson

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

ContinueView Course