Standard Library Sequence Reordering Algorithms Sequence Reordering Algorithms Reorder

New to C++'s standard library algorithms? ⇒ Short Introduction

Shift Elements Shift

`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';
}

cppreference

#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

cppreference

#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

cppreference

#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

cppreference

#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';}

cppreference

#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

cppreference

#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

cppreference

#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_left C++20/23

cppreference

#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';
}

cppreference

#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_right C++20/23

cppreference

#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';
}

cppreference

#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` shuffle C++11

cppreference

#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';
}

cppreference

#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';
}

Sorting Sort

`sort` sort

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

cppreference

#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 2^nd argument

cppreference

#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 3^rd argument

cppreference

#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 2^nd argument

cppreference

#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 4^th argument

cppreference

#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 3^rd argument

cppreference

#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 5^th argument

cppreference

#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 3^rd argument

cppreference

#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 4^th argument

cppreference

#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 3^rd argument

cppreference

#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 3^rd argument

cppreference

#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 2^nd argument

cppreference

#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 3^rd argument

cppreference

#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 2^nd argument

cppreference

#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';
}

Partitioning Partition

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

cppreference

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

cppreference

#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';
}

cppreference

#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';
}

cppreference

#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

cppreference

#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';
}

cppreference

#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

cppreference

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

cppreference

#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

cppreference

#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

cppreference

#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';
}

Permutations Permute

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

cppreference

#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)) );
}

cppreference

#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 );
}

`is_permutation` is_permutation C++11

cppreference

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

cppreference

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

Range Copy

Beginner's Guide / Std.Library 2

Change

Related …

A Tour of C++: Containers and Algorithms

Algorithms Overview Sheet

Last updated: 2022-11-20

First Steps

Input & Output

Custom Types – Part 1

Diagnostics

Standard Library – Part 1

Function Objects

Standard Library – Part 2

Code Organization

Custom Types – Part 2

Generic Programming

Memory Management

Software Design Basics

Standard Library Sequence Reordering Algorithms Sequence Reordering Algorithms Reorder

New to C++'s standard library algorithms? ⇒ Short Introduction

Shift Elements Shift

`reverse` / `reverse_copy` `reverse_copy` reverse

`rotate` / `rotate_copy` `rotate` rotate

`shift_left` shift_left C++20/23

`shift_right` shift_right C++20/23

`shuffle` shuffle C++11

Sorting Sort

`sort` sort

`stable_sort` stable_sort

`partial_sort` / `partial_sort_copy` `partial_sort_copy` partial_sort

`nth_element` nth_element

`is_sorted` is_sorted

`is_sorted_until` is_sorted_until

Partitioning Partition

`partition` / `partition_copy` `partition_copy` partition

`stable_partition` stable_partition

`is_partitioned` is_partitioned

`partition_point` partition_point

Permutations Permute

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

`is_permutation` is_permutation C++11

Related …

Comments…

First Steps

Input & Output

Custom Types – Part 1

Diagnostics

Standard Library – Part 1

Function Objects

Standard Library – Part 2

Code Organization

Custom Types – Part 2

Generic Programming

Memory Management

Software Design Basics

New to C++'s standard library algorithms? ⇒ Short Introduction

Shift Elements Shift

reverse / reverse_copy reverse_copy reverse

rotate / rotate_copy rotate rotate

shift_left shift_left C++20/23

shift_right shift_right C++20/23

shuffle shuffle C++11

Sorting Sort

sort sort

stable_sort stable_sort

partial_sort / partial_sort_copy partial_sort_copy partial_sort

nth_element nth_element

is_sorted is_sorted

is_sorted_until is_sorted_until

Partitioning Partition

partition / partition_copy partition_copy partition

stable_partition stable_partition

is_partitioned is_partitioned

partition_point partition_point

Permutations Permute

prev_permutation / next_permutation prev_ / next_permutation prev_/next_permutation

is_permutation is_permutation C++11

Related …

Comments…

`reverse` / `reverse_copy` `reverse_copy` reverse

`rotate` / `rotate_copy` `rotate` rotate

`shift_left` shift_left C++20/23

`shift_right` shift_right C++20/23

`shuffle` shuffle C++11

`sort` sort

`stable_sort` stable_sort

`partial_sort` / `partial_sort_copy` `partial_sort_copy` partial_sort

`nth_element` nth_element

`is_sorted` is_sorted

`is_sorted_until` is_sorted_until

`partition` / `partition_copy` `partition_copy` partition

`stable_partition` stable_partition

`is_partitioned` is_partitioned

`partition_point` partition_point

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

`is_permutation` is_permutation C++11