# Movement Algorithms

An introduction to the seven 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
###### Ryan McCombe
Updated

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:
1, 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:

#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 "
"index "
<< std::distance(
Destination.begin(), out);
}
Values in Destination:
0, 1, 2, 3, 0,
The 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:

What it means for an object to be "moved" is defined by the move constructor and move assignment operator 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:

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

class Player {/*...*/};

int main() {
using namespace std::string_literals;
std::vector<Player> Source{
"Anna"s, "Roderick"s, "Robert"s};

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

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

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

std::cout << "\nPlayers in Destination:\n";
for (auto& Player : Destination) {
std::cout << Player.Name << "\n";
}
}
Players in Source:
Anna (Moved)
Roderick (Moved)
Robert (Moved)

Players in Destination:
Anna
Roderick
Robert

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

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

#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: 0, 0, 1, 2, 3,
The output iterator is at position 2
The 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:

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

struct T {/*...*/};

int main() {
std::vector<T> Values{
T{1}, T{2}, T{3}, T{0}, T{0}};

std::ranges::move(
Values.begin(),
Values.begin() + 3,
// Undefined behaviour - this
// destination is within the input range
Values.begin() + 2);

for (T& x : Values) {
std::cout << x.Value << ", ";
}
}

The result is not exactly what we had inÂ mind:

0, 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:

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

struct T {/*...*/};

int main() {
std::vector<T> Values{
T{1}, T{2}, T{3}, T{0}, T{0}};

std::ranges::move_backward(
Values.begin(),
Values.begin() + 3,
// This is better - the destination is no
// longer within the input range
Values.end());

for (T& x : Values) {
std::cout << x.Value << ", ";
}
}
0, 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:

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.

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

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

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

struct T {
int Value;
};

void swap(T& A, T& B) {
std::cout << "Swapping " << A.Value
<< " and " << B.Value << '\n';
std::swap(A.Value, B.Value);
}

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

std::ranges::reverse(Numbers);

std::cout << "Numbers: ";
for (auto& Num : Numbers) {
std::cout << Num.Value << ", ";
}
}
Swapping 1 and 5
Swapping 2 and 4
Numbers: 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:

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

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

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

struct T {/*...*/};

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

std::ranges::shift_left(Range, 1);
std::cout << "Numbers: ";
for (auto& Num : Range) {
std::cout << Num.Value << ", ";
}
}
Numbers: 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:

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

struct T {/*...*/};

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

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

std::cout << "Original Range: ";
for (T& Object : Range) {
std::cout << Object.Value << ", ";
}

std::cout << "\nReturned Subrange: ";
for (T& Object : Subrange) {
std::cout << Object.Value << ", ";
}
}
Original Range: 3, 4, 5, 6, 5, 6,
Returned 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:

#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: 1, 2, 1, 2, 3, 4,
Returned 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:

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

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

std::ranges::reverse(
Numbers.begin() + 1, Numbers.end() - 1);

std::cout << "Numbers: ";
for (auto& Num : Numbers) {
std::cout << Num << ", ";
}
}
Numbers: 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():

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

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().
New: AI-Powered AssistanceAI Assistance

### Questions and HelpNeed Help?

Get instant help using our free AI assistant, powered by state-of-the-art language models.

Updated
Lesson Contents

### Movement Algorithms

An introduction to the seven 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

###### Movement Algorithms

An introduction to the seven 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:

• 124 Lessons
• 550+ Code Samples
• 96% Positive Reviews
• Regularly Updated
• Help and FAQ
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().