C++ Reference ยท Algorithms
The std::reverse and std::rotate algorithms
Reference for C++ std::reverse, reverse_copy, rotate, rotate_copy and shift_left/right: reorder a range in place, return values and typical uses.
std::reverse flips a range in place so the first element becomes the last. std::rotate turns a range so that a chosen element becomes the first one: the elements before it move to the back, in order. Both work in place on any suitable range of a container or array, and have _copy versions that write the result elsewhere.
std::shift_left and std::shift_right (C++20) slide elements within the range, leaving moved-from slots at the other end. Rotation is the building block behind insertion into the middle of a sorted range, moving an element to the front and implementing "slide" operations on lists.
std::reverse(v.begin(), v.end()); std::rotate(v.begin(), v.begin() + 2, v.end()); // element at index 2 becomes first
Try it
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.
Syntax
template<class BidIt> void reverse(BidIt first, BidIt last); template<class BidIt, class OutIt> OutIt reverse_copy(BidIt first, BidIt last, OutIt d_first); template<class FwdIt> FwdIt rotate(FwdIt first, FwdIt middle, FwdIt last); template<class FwdIt, class OutIt> OutIt rotate_copy(FwdIt first, FwdIt middle, FwdIt last, OutIt d_first); template<class FwdIt> FwdIt shift_left(FwdIt first, FwdIt last, difference_type n); // C++20 template<class FwdIt> FwdIt shift_right(FwdIt first, FwdIt last, difference_type n); // C++20
| Name | Description |
|---|---|
first, last |
The range to rearrange. |
middle |
The element that becomes the first one after rotate; must lie in [first, last]. |
d_first |
Output start for the _copy versions; must not overlap the source. |
n |
Shift distance; n <= 0 does nothing. |
Returns: reverse returns nothing. rotate returns the new position of the element that was first (that is, first + (last - middle)). shift_left returns the new end of the valid elements; shift_right the new beginning.
Errors / undefined behavior: middle outside [first, last] is undefined behavior; so are output ranges that are too short or overlap.
Usage notes
- Bidirectional needed for reverse: it works on arrays, vectors, deques, lists and strings, but not on forward-only ranges.
- Rotation direction:
middleis the new first element. Left byk:middle = first + k. Right byk:middle = last - k. - Move one element:
rotate(pos, element, element + 1)moveselementback toposwhile shifting the others, keeping their order. It is how insertion sort and "move to front" are written. - Complexity:
reversedoes aboutn/2swaps;rotateis linear (at mostnswaps/moves). On astd::listconsider the memberspliceinstead, which moves nodes without touching elements. shift_left/shift_right: the moved-from slots hold unspecified values; erase them yourself. These shifts drop elements, whereasrotatekeeps them.- Ranges (C++20):
std::ranges::reverse,reverse_copy,rotate,rotate_copy;ranges::rotatereturns a subrange. - Lazy reverse:
std::views::reverse(C++20) iterates backward without touching the data. - Parallel overloads: execution policies are accepted as the first argument.