# C++ Movement Algorithms

An introduction to the 7 movement algorithms in the C++ standard library: move, move_backward, rotate, reverse, shuffle, shift_left, and shift_right
This lesson is part of the course:

### Professional C++

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

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:

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

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

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

std::vector Destination{0, 0, 0};

std::ranges::move(Source,
Destination.begin());

std::cout << "Values in Destination:\n";
for (auto& Num : Destination) {
std::cout << Num;
}
}

Values in Destination:
123


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:

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

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

std::vector Destination{0, 0, 0, 0, 0};

auto [in, out]{std::ranges::move(
Source, Destination.begin() + 1)};

std::cout << "Values in Destination:\n";
for (auto& Num : Destination) {
std::cout << Num;
}

std::cout << "\nThe input had "
<< std::distance(Source.begin(), in)
<< " objects\n";

std::cout << "The output iterator is at "
"position "
<< std::distance(
Destination.begin(), out);
}

Values in Destination:
01230
The output iterator is at position 4


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:

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

class Character {
public:
std::string Name;

Character() = default;
Character(std::string n) : Name(n) {}
Character(const Character& Original) =
default;

Character& operator=(
Character&& Original) noexcept {
if (&Original != this) {
Name = Original.Name;
Original.Name += " (Moved)";
}

return *this;
}
};

int main() {
using namespace std::string_literals;
std::vector<Character> Source{
"Legolas"s, "Gimli"s, "Gandalf"s};

std::vector<Character> Destination{
Source.size()};

std::ranges::move(Source,
Destination.begin());

std::cout << "Characters in Source:\n";
for (auto& Character : Source) {
std::cout << Character.Name << "\n";
}

std::cout << "\nCharacters in Destination:\n";
for (auto& Character : Destination) {
std::cout << Character.Name << "\n";
}
}

Characters in Source:
Legolas (Moved)
Gimli (Moved)
Gandalf (Moved)

Characters in Destination:
Legolas
Gimli
Gandalf


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

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

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

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

std::vector Destination{0, 0, 0};

std::move(Source.begin(), Source.end(),
Destination.begin());

std::cout << "Values in Destination: ";
for (auto& Num : Destination) {
std::cout << Num;
}
}

Values in Destination: 123


### A note on std::move

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 <algorithm> header, which we’ve shown above, is for moving a collection of objects to another container
• The std::move in the <utility> header, which we introduced in our lessons on memory management, is for casting objects to rvalue references

Even when both functions are in scope, they require a different number of arguments, so the compiler can understand which one we’re calling.

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

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

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

std::ranges::move_backward(Source,
Destination.end());

std::cout << "Values in Destination: ";
for (auto& Num : Destination) {
std::cout << Num;
}
}

Values in Destination: 00123


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:

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

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

std::vector Destination{0, 0, 0, 0, 0};

auto [in, out]{std::ranges::move_backward(
Source, Destination.end())};

std::cout << "Values in Destination: ";
for (auto& Num : Destination) {
std::cout << Num;
}

std::cout << "\nThe input had "
<< std::distance(Source.begin(), in)
<< " objects\n";

std::cout << "The output iterator is at "
"position "
<< std::distance(
Destination.begin(), out);

std::cout << "\nThe last element moved was "
<< *out;
}

Values in Destination: 00123
The output iterator is at position 2
The last element moved was 1


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

std::vector Days{"Mon", "Tue", "Wed", "Thu",
"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.

std::vector Days{"Sun", "Mon", "Tue", "Wed",
"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.

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

int main() {
std::vector Days{"Mon", "Tue", "Wed", "Thu",
"Fri", "Sat", "Sun"};

std::ranges::rotate(Days, Days.end() - 1);

for (auto& Day : Days) {
std::cout << Day << ", ";
}
}

Sun, 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.

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

int main() {
std::vector Days{"Mon", "Tue", "Wed", "Thu",
"Fri", "Sat", "Sun"};

auto Subrange{std::ranges::rotate(
Days, Days.end() - 1)};

for (auto& Day : Days) {
std::cout << Day << ", ";
}

std::cout << "Subrange has "
<< Subrange.size() << " elements ("
<< Subrange.front() << " - "
<< Subrange.back() << ")";
}

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


## std::ranges::reverse

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

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

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

std::ranges::reverse(Numbers);

std::cout << "Numbers: ";
for (auto& Num : Numbers) {
std::cout << Num;
}
}

Numbers: 54321


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.

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

struct MyStruct {
int Value;

MyStruct(int x) : Value{x} {};

// Copy constructor
MyStruct(const MyStruct& Source) = default;

// Move constructor
MyStruct(const MyStruct&& Source)
: Value{Source.Value} {};

// Move operator
MyStruct& operator=(const MyStruct&& Source) {
Value = Source.Value;
return *this;
}
};

int main() {
std::vector Numbers{MyStruct{1}, MyStruct{2},
MyStruct{3}};

std::ranges::reverse(Numbers);

std::cout << "Numbers: ";
for (auto& Num : Numbers) {
std::cout << Num.Value;
}
}

Numbers: 321


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

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

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

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

std::random_device Device;
std::mt19937 Generator{Device()};

std::ranges::shuffle(Range, Generator);

std::cout << "Shuffled Numbers: ";
for (auto& Num : Range) {
std::cout << Num;
}
}

Shuffled Numbers: 613542


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:

// Move everything left by two steps
std::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:

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

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

std::ranges::shift_left(Range, 2);

std::cout << "Numbers: ";
for (auto& Num : Range) {
std::cout << Num;
}
}


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:

Numbers: 345656


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

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

struct MyStruct {
int Value;

MyStruct(int x) : Value{x} {};

MyStruct(const MyStruct& Source) = default;

MyStruct& operator=(
MyStruct&& Source) noexcept {
Value = Source.Value;
Source.Value = 0;
return *this;
}
};

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

std::ranges::shift_left(Range, 1);
std::cout << "Numbers: ";
for (auto& Num : Range) {
std::cout << Num.Value;
}
}

Numbers: 345600


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:

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

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

auto Subrange{
std::ranges::shift_left(Range, 2)};

std::cout << "Original Range: ";
for (auto& Num : Range) {
std::cout << Num;
}

std::cout << "\nReturned Subrange: ";
for (auto& Num : Subrange) {
std::cout << Num;
}
}

Original Range: 345656
Returned Subrange: 3456


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

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

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

auto Subrange{
std::ranges::shift_right(Range, 2)};

std::cout << "Original Range: ";
for (auto& Num : Range) {
std::cout << Num;
}

std::cout << "\nReturned Subrange: ";
for (auto& Num : Subrange) {
std::cout << Num;
}
}

Original Range: 121234
Returned Subrange: 1234 ###### Ryan McCombe
Posted
This lesson is part of the course:

### Professional C++

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

###### C++ Movement Algorithms

An introduction to the 7 movement algorithms in the C++ standard library: move, move_backward, rotate, reverse, shuffle, shift_left, and shift_right. 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:

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

### C++ Copying Algorithms

An introduction to the 7 movement algorithms in the C++ standard library: copy, copy_n, copy_if, copy_backward, reverse_copy, rotate_copy, and unique_copy. 