Beginner's Guide

# Standard Library Sequence Reordering AlgorithmsSequence Reordering AlgorithmsReorder

## Shift ElementsShift

### `reverse` / `reverse_copy``reverse_copy`reverse

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

int main () {std::vector<int> v {0,1,2,4,6,8,9,3,5};
// reverse subrange (as shown in image):
reverse(begin(v)+2, begin(v)+7);
for (int x : v) { std::cout << x << ' '; }  // 0 1 9 8 6 4 2 3 5
std::cout << '\n';// reverse entire vector:
reverse(begin(v), end(v));
for (int x : v) { std::cout << x << ' '; }  // 5 3 2 4 6 8 9 1 0
std::cout << '\n';
}``````
``````#include <vector>
#include <iostream>
#include <algorithm>

int main () {std::vector<int> v {2,4,6,8,9};
std::ranges::reverse(v);
for (int x : v) { std::cout << x << ' '; }  // 9 8 6 4 2
std::cout << '\n';
}``````

the output must be able to receive as many elements as there are in the input range

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

int main () {std::vector<int> in {0,1,2,4,6,8,9,3,5};
std::vector<int> out;
out.resize(5);
reverse_copy(begin(in)+2, begin(in)+7, begin(out));
for (int x : out) { std::cout << x << ' '; }  // 9 8 6 4 2
std::cout << '\n';
}``````

the output must be able to receive as many elements as there are in the input range

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

int main () {std::vector<int> in {2,4,6,8,9};
std::vector<int> out;
out.resize(in.size());
std::ranges::reverse_copy(in, begin(out));
for (int x : out) { std::cout << x <<' '; }  // 9 8 6 4 2
std::cout << '\n';
}``````

### `rotate` / `rotate_copy``rotate`rotate

performs a cyclic left rotation: all elements from `begin` to one before `new_fist` are moved behind the last element

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

int main () {std::vector<int> v {1,2,3,4,5,6,7};
auto i = rotate(begin(v), begin(v)+2, end(v));
for (int x : v) { std::cout << x <<' '; }  // 3 4 5 6 7 1 2
std::cout << '\n';// returned iterator refers to old first:
auto const value = *i;  // 1
auto const index = distance(begin(v), i);  // 5
std::cout << "value: " << value << '\n';
std::cout << "index: " << index << '\n';}``````
``````#include <vector>
#include <iostream>
#include <algorithm>

int main () {std::vector<int> v {1,2,3,4,5,6,7};
auto sub = std::ranges::rotate(v, begin(v)+4);
for (int x : v)   { std::cout << x <<' '; }  // 5 6 7 1 2 3 4
std::cout << '\n';for (int x : sub) { std::cout << x <<' '; }  // 1 2 3 4
std::cout << '\n';
}``````

the output must be able to receive as many elements as there are in the input range

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

int main () {std::vector<int> in {1,2,3,4,5,6,7};
std::vector<int> out;
out.resize(in.size());
rotate_copy(begin(in), begin(in)+2,             end(in), begin(out));
for (int x : out) { std::cout << x <<' '; }  // 3 4 5 6 7 1 2
std::cout << '\n';
}``````

the output must be able to receive as many elements as there are in the input range

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

int main () {std::vector<int> in {1,2,3,4,5,6,7};
std::vector<int> out;
out.resize(in.size());
std::ranges::rotate_copy(in, begin(in)+4, begin(out));
for (int x : out) { std::cout << x <<' '; }  // 5 6 7 1 2 3 4
std::cout << '\n';
}``````

### `shift_left`shift_leftC++20/23

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

int main () {std::vector<int> v {1,2,3,4,5,6,7,8};
int const by = 3;
shift_left(begin(v), end(v), by);
for (int x : v) { std::cout << x <<' '; }  // 4 5 6 7 8 ? ? ?
std::cout << '\n';
}``````
``````#include <vector>
#include <iostream>
#include <algorithm>

int main () {std::vector<int> v {1,2,3,4,5,6,7,8};
int const by = 3;
auto result = std::ranges::shift_left(v, by);
for (int x : result) { std::cout << x <<' '; }  // 4 5 6 7 8
std::cout << '\n';
}``````

### `shift_right`shift_rightC++20/23

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

int main () {std::vector<int> v {1,2,3,4,5,6,7,8};
int const by = 3;
shift_right(begin(v), end(v), by);
for (int x : v) { std::cout << x <<' '; }  // ? ? ? 1 2 3 4 5
std::cout << '\n';
}``````
``````#include <vector>
#include <iostream>
#include <algorithm>

int main () {std::vector<int> v {1,2,3,4,5,6,7,8};
int const by = 3;
auto result = std::ranges::shift_right(v, by);
for (int x : result) { std::cout << x <<' '; }  // 1 2 3 4 5
std::cout << '\n';
}``````

### `shuffle`shuffleC++11

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

int main () {// 32 bit mersenne twister engine
auto const seed = std::random_device{}();
auto reng = std::mt19937{seed};
std::vector<int> v {0,1,2,3,4,5,6,7,8};
shuffle(begin(v)+2, begin(v)+7, reng);
for (int x : v) { std::cout << x <<' '; }  // 0 1 … 7 8
std::cout << '\n';
}``````
``````#include <vector>
#include <iostream>#include <algorithm>
#include <random>

int main () {// 32 bit mersenne twister engine
auto const seed = std::random_device{}();
auto reng = std::mt19937{seed};
std::vector<int> v {2,3,4,5,6};
std::ranges::shuffle(v, reng);
for (int x : v) { std::cout << x <<' '; }
std::cout << '\n';
}``````

## SortingSort

### `sort`sort

a custom function(object) for comparing elements can be passed as 3rd argument

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

int main () {std::vector<int> v {8,9,3,1,2,3,5,4,7,6};
// sort subrange (as shown in image):
sort(begin(v)+2, begin(v)+8);
for (int x : v) { std::cout << x <<' '; }  // 8 9 1 2 3 3 4 5 7 6
std::cout << '\n';
// sort entire vector:
sort(begin(v), end(v));
for (int x : v) { std::cout << x <<' '; }  // 1 2 3 3 4 5 6 7 8 9
std::cout << '\n';
// sort vector in descending order:
sort(begin(v), end(v), std::greater<>{});
for (int x : v) { std::cout << x <<' '; }  // 9 8 7 6 5 4 3 3 2 1
std::cout << '\n';
}``````

a custom function(object) for comparing elements can be passed as 2nd argument

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

int main () {std::vector<int> range {3,1,2,3,5,4};
std::ranges::sort(range);
for (int x : range) { std::cout << x <<' '; }  // 1 2 3 3 4 5
std::cout << '\n';
// sort in descending order:
std::ranges::sort(range, std::greater<>{});
for (int x : range) { std::cout << x <<' '; }  // 5 4 3 3 2 1
std::cout << '\n';
}``````

### `stable_sort`stable_sort

stable ⇒ `a` stays before `A` (and `E` stays before `e`) even though they are equivalent with respect to case insensitive comparison

compares elements using `operator <` by default; a custom function(object) for comparing elements can be passed as 3rd argument

``````#include <iostream>
#include <algorithm>#include <cctype>  // std::tolower

int main () {auto compare_cicase_insensitive = [](char x, char y) {
return std::tolower(x) < std::tolower(y); };
std::string s = "gbaEAfec";
stable_sort(begin(s)+1, begin(s)+7, compare_cicase_insensitive);
std::cout << s << '\n';  // gaAbEefc
}``````

stable ⇒ `a` stays before `A` (and `E` stays before `e`) even though they are equivalent with respect to case insensitive comparison

compares elements using `operator <` by default; a custom function(object) for comparing elements can be passed as 2nd argument

``````#include <iostream>
#include <algorithm>#include <cctype>  // std::tolower

int main () {auto compare_cicase_insensitive = [](char x, char y) {
return std::tolower(x) < std::tolower(y); };
std::string str = "baEAfe";
std::ranges::stable_sort(str, compare_cicase_insensitive);
std::cout << str << '\n';  // aAbEef
}``````

### `partial_sort` / `partial_sort_copy``partial_sort_copy`partial_sort

compares elements using `operator <` by default; a custom function(object) for comparing elements can be passed as 4th argument

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

int main () {std::vector<int> v {7,4,6,2,3,5,1,9};
// sort 4 smallest elements:
auto const nth = begin(v) + 4;
partial_sort(begin(v), nth, end(v));
for (int x : v) { std::cout << x <<' '; }  // 1 2 3 4 7 6 5 9
std::cout << '\n';
}``````

compares elements using `operator <` by default; a custom function(object) for comparing elements can be passed as 3rd argument

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

int main () {std::vector<int> v {7,4,6,2,3,5,1,9};
// sort 4 smallest elements:
auto const nth = begin(v) + 4;
std::ranges::partial_sort(v, nth);
for (int x : v) { std::cout << x <<' '; }  // 1 2 3 4 7 6 5 9
std::cout << '\n';
}``````

compares elements using `operator <` by default; a custom function(object) for comparing elements can be passed as 5th argument

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

int main () {std::vector<int> in {6,2,3,5,1};
// get sorted copy of 3 smallest elements:
int const n = 3;
std::vector<int> out;
out.resize(n);
partial_sort_copy(begin(in), end(in),                   begin(out), end(out));
for (int x : out) { std::cout << x <<' '; }  // 1 2 3
std::cout << '\n';
// if output is larger than input:
out.resize(100);
auto const e = partial_sort_copy(begin(in), end(in),                   begin(out), end(out));
out.erase(e, end(out));  // shrink to fit
for (int x : out) { std::cout << x <<' '; }  // 1 2 3 5 6
std::cout << '\n';
}``````

compares elements using `operator <` by default; a custom function(object) for comparing elements can be passed as 3rd argument

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

int main () {std::vector<int> in {6,2,3,5,1};
// get sorted copy of 3 smallest elements:
int const n = 3;
std::vector<int> out;
out.resize(n);
std::ranges::partial_sort_copy(in, out);
for (int x : out) { std::cout << x <<' '; }  // 1 2 3
std::cout << '\n';
}``````

### `nth_element`nth_element

compares elements using `operator <` by default; a custom function(object) for comparing elements can be passed as 4th argument

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

int main () {std::vector<int> v {4,2,5,6,3,7,1};
// get 5th element in sorted order
int const n = 4;
auto nth = begin(v) + n;
nth_element(begin(v), nth, end(v));
std::cout << *nth;  // 5
std::cout << '\n';
}``````

compares elements using `operator <` by default; a custom function(object) for comparing elements can be passed as 3rd argument

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

int main () {std::vector<int> v {4,2,5,6,3,7,1};
// get 5th element in sorted order
int const n = 4;
auto nth = begin(v) + n;
std::ranges::nth_element(v, nth);
std::cout << *nth;  // 5
std::cout << '\n';
}``````

### `is_sorted`is_sorted

compares elements using `operator <` by default; a custom function(object) for comparing elements can be passed as 3rd argument

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

int main () {std::vector<int> v {2,3,4,5,6,1,0};
// test subrange (as shown in image):
std::cout << is_sorted(begin(v), begin(v)+5);  // true
std::cout << '\n';
// test entire vector:
std::cout << is_sorted(begin(v), end(v));  // false
std::cout << '\n';
}``````

compares elements using `operator <` by default; a custom function(object) for comparing elements can be passed as 2nd argument

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

int main () {std::vector<int> v {2,3,4,5,6};
std::cout << std::ranges::is_sorted(v);  // true
std::cout << '\n';
}``````

### `is_sorted_until`is_sorted_until

compares elements using `operator <` by default; a custom function(object) for comparing elements can be passed as 3rd argument

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

int main () {std::vector<int> v {2,3,4,5,4,2,0,7,8};
// test from 1st to 7th (as shown in image):
auto i = is_sorted_until(begin(v), begin(v)+7);
// print sorted subrange
auto const print = [](int x){ std::cout << x << ' '; };
std::for_each(begin(v), i, print);  // 2 3 4 5
std::cout << '\n';
}``````

compares elements using `operator <` by default; a custom function(object) for comparing elements can be passed as 2nd argument

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

int main () {std::vector<int> v {2,3,4,5,4,2,0};
auto const i = std::ranges::is_sorted_until(v);
// print sorted subrange
auto const print = [](int x){ std::cout << x << ' '; };
std::for_each(begin(v), i, print);  // 2 3 4 5
std::cout << '\n';
}``````

## PartitioningPartition

### `partition` / `partition_copy``partition_copy`partition

Note that the relative order of elements within the resulting partitions need not be the same as in the original sequence.

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

int main () {auto const is_odd = [](int x) {   return (x & 1); };
std::vector<int> v {3,4,6,5,7,8,0};
auto i = partition(begin(v), end(v), is_odd);
auto const print = [](int x){ std::cout << x << ' '; };
// print 1st subrange
std::for_each(begin(v), i, print);  // 3 7 5
std::cout << '\n';// print 2nd subrange
std::for_each(i, end(v), print);  // 6 4 8 0
std::cout << '\n';
}``````

Note that the relative order of elements within the resulting partitions need not be the same as in the original sequence.

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

int main () {auto const is_odd = [](int x) {   return (x & 1); };
std::vector<int> v {3,4,6,5,7,8,0};
auto r2 = std::ranges::partition(v, is_odd);
// print 2nd subrange
for (int x : r2) { std::cout << x << ' '; }  // 6 4 8 0
std::cout << '\n';
}``````
``````#include <vector>
#include <iostream>
#include <algorithm>

int main () {auto const is_odd = [](int x) {   return (x & 1); };
std::vector<int> in {3,4,6,5,0};
// ensure each output could hold all elements:
std::vector<int> out1; out1.resize(in.size());
std::vector<int> out2; out2.resize(in.size());
auto ends = partition_copy(begin(in), end(in), begin(out1), begin(out2), is_odd);
// resize partitions to fit content
out1.erase(ends.first,  end(out1));
out2.erase(ends.second, end(out2));
// print partitions
for (int x : out1) { std::cout << x << ' '; }  // 3 5
std::cout << '\n';for (int x : out2) { std::cout << x << ' '; }  // 4 6 0
std::cout << '\n';
}``````
``````#include <vector>
#include <iostream>
#include <algorithm>

int main () {auto const is_odd = [](int x) {   return (x & 1); };
std::vector<int> in {3,4,6,5,0};
// ensure each output could hold all elements:
std::vector<int> out1; out1.resize(in.size());
std::vector<int> out2; out2.resize(in.size());
auto ends = std::ranges::partition_copy(in, begin(out1), begin(out2), is_odd);
// resize partitions to fit content
out1.erase(ends.out1, end(out1));
out2.erase(ends.out2, end(out2));
// print partitions
for (int x : out1) { std::cout << x << ' '; }  // 3 5
std::cout << '\n';for (int x : out2) { std::cout << x << ' '; }  // 4 6 0
std::cout << '\n';
}``````

### `stable_partition`stable_partition

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

int main () {auto const is_odd = [](int x) {   return (x & 1); };
std::vector<int> v {3,4,6,5,7,8,0};
auto i = stable_partition(begin(v), end(v), is_odd);
auto const print = [](int x){ std::cout << x << ' '; };
// print 1st subrange
std::for_each(begin(v), i, print);  // 3 5 7
std::cout << '\n';// print 2nd subrange
std::for_each(i, end(v), print);  // 4 6 8 0
std::cout << '\n';
}``````
``````#include <vector>
#include <iostream>
#include <algorithm>

int main () {auto const is_odd = [](int x) {   return (x & 1); };
std::vector<int> v {3,4,6,5,7,8,0};
auto r2 = std::ranges::stable_partition(v, is_odd);
// print 2nd subrange
for (int x : r2) { std::cout << x << ' '; }  // 4 6 8 0
std::cout << '\n';
}``````

### `is_partitioned`is_partitioned

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

int main () {auto const is_odd = [](int x) {   return (x & 1); };
std::vector<int> v {3,7,5,6,4,8,0};
std::cout << is_partitioned(begin(v), end(v), is_odd) << '\n';  // true
}``````
``````#include <vector>
#include <iostream>
#include <algorithm>

int main () {auto const is_odd = [](int x) {   return (x & 1); };
std::vector<int> v {3,7,5,6,4,8,0};
std::cout << std::ranges::is_partitioned(v, is_odd) << '\n';  // true
}``````

### `partition_point`partition_point

performs a binary search for the first element in a partitioned input range for which `f` is false

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

int main () {auto const is_odd = [](int x) {   return (x & 1); };
std::vector<int> v {3,7,5,6,4,8,0};
auto i = partition_point(begin(v), end(v), is_odd);
auto const print = [](int x){ std::cout << x << ' '; };
// print 1st subrange
std::for_each(begin(v), i, print);  // 3 7 5
std::cout << '\n';// print 2nd subrange
std::for_each(i, end(v), print);  // 6 4 8 0
std::cout << '\n';
}``````

performs a binary search for the first element in a partitioned input range for which `f` is false

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

int main () {auto const is_odd = [](int x) {   return (x & 1); };
std::vector<int> v {3,7,5,6,4,8,0};
auto i = std::ranges::partition_point(v, is_odd);
auto const print = [](int x){ std::cout << x << ' '; };
// print 1st subrange
std::for_each(begin(v), i, print);  // 3 7 5
std::cout << '\n';// print 2nd subrange
std::for_each(i, end(v), print);  // 6 4 8 0
std::cout << '\n';
}``````

## PermutationsPermute

### `prev_permutation` / `next_permutation``prev_` / `next_permutation`prev_/next_permutation

``````#include <array>
#include <iostream>
#include <algorithm>

int main () {std::array<int,3> v {1,2,3};
do {
for (int x : v) { std::cout << x << ' '; }
std::cout << '\n';
} while( std::next_permutation(begin(v),end(v)) );
}``````
``````
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1``````
``````#include <array>
#include <iostream>
#include <algorithm>

int main () {std::array<int,3> v {1,2,3};
do {
for (int x : v) { std::cout << x << ' '; }
std::cout << '\n';
} while( std::ranges::next_permutation(v).found );
}``````
``````
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1``````

### `is_permutation`is_permutationC++11

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

int main () {std::vector<int> v1 {1,2,3,4};
std::vector<int> v2 {4,2,1,3};
std::vector<int> v3 {5,0,1,2};
std::cout << is_permutation(begin(v1), end(v1), begin(v2)) << '\n';  // true
std::cout << is_permutation(begin(v1), end(v1), begin(v3)) << '\n';  // false
}``````
``````#include <vector>
#include <iostream>
#include <algorithm>

int main () {std::vector<int> v1 {1,2,3,4};
std::vector<int> v2 {4,2,1,3};
std::vector<int> v3 {5,0,1,2};
std::cout << std::ranges::is_permutation(v1, v2) << '\n';  // true
std::cout << std::ranges::is_permutation(v1, v3) << '\n';  // false
}``````