Standard Library AlgorithmsStandard AlgorithmsAlgorithms

Non-Modifying Operations Non-Modifying Non-Mod.

Existence Queries Existence

returns true if predicate 'check' yields true for any element in the input range; otherwise returns false

returns true if predicate 'check' yields true for all elements in the input range; otherwise returns false

returns true if predicate 'check' yields false for all elements in the input range; otherwise returns false

returns the number of elements equal to 'value'

returns the number of elements for which predicate 'condition' yields true

Finding / Locating Elements Locate

Find Single Elements

find the 1^st matching position of a single element that compares equal to 'value'

find the 1^st matching position of a single element for which predicate 'f' is true

find the 1^st matching position of a single element for which predicate 'f' is false

find the 1^st matching position in range 1 of any element contained in range 2

Find Consecutive Runs of Equal Elements

find the starting position of a run of at least 2 consecutive identical elements

find the starting position of a run of at least 'n' consecutive identical elements equal to 'value'

Find Ranges in Ranges

searches for the first occurrence of range 2 inside range 1

find last occurrence of range 2 inside range 1

Comparing Ranges Compare

returns true if all elements in both ranges are equal; otherwise returns false

returns a pair of iterators to the first mismatching elements in 2 ranges

returns true if range 1 is lexicographically less than range 2

compares 2 ranges using 3-way comparisons and returns the result as a value of the strongest applicable comparsion category

Binary Search of Sorted Ranges Binary Search Binary Search

returns true if the input range contains an element equivalent to 'value'; otherwise returns false;
input range must be sorted

returns the position of the first element not smaller than 'value';
input range must be sorted

returns the position of the first element greater than 'value';
input range must be sorted

returns an iterator range of all elements equivalent to 'value';
input range must be sorted

return true if sorted range 2 was found inside sorted range 1;
input ranges must be sorted

Minimum / Maximum Min/Max

returns an iterator to the smallest element;
the 2^nd version uses 'compare' for comparing elements, while the 1^st version uses operator<

returns an iterator to the largest element;
the 2^nd version uses 'compare' for comparing elements, while the 1^st version uses operator<

returns a pair of iterators to both the smallest and largest elements;
the 2^nd version uses 'comp' for comparing elements, while the 1^st version uses operator<

Non-Range min/max/clamp

min(a, b) → a if (a < b) is true, b otherwise

min({v1,v2,v3, …}) → smallest value

min(a, b, f(o,o)→bool) → a if f(a,b) is true, b otherwise

max(a, b) → b if (a < b) is true, a otherwise

max({v1,v2,v3,…}) → largest value

max(a, b, f(o,o)→bool) → b if f(a,b) is true, a otherwise

minmax(a, b) → { smallest , largest }

minmax({v1,v2,v3, …}) → { smallest , largest }

minmax(a, b, f(o,o)→bool) → { smallest , largest }

custom comparison function/object: f(a,b) must return true if a is less than b

clamp(value,hi,lo) → clamped_value

clamp(value,hi,lo,f(o,o)→bool) → clamped_value

clamps value in the interval given by hi and lo; the second version uses f to compare values instead of operator <

Structural Properties Structural

#include <iterator>

returns the number of elements in an iterator range

#include <iterator>

returns the number of elements in an iterator range

returns true if the input range is sorted and false otherwise;
the 2^nd version uses 'compare' for comparing elements, while the 1^st version uses operator<

returns the first position where the input range is no longer sorted;
the 2^nd version uses 'compare' for comparing elements, while the 1^st version uses operator<

returns true if the input range is partitioned according to predicate 'f' and false otherwise

returns the start of the partition of elements for which predicate 'f'; yields false;
the input range must be partitioned according to 'f'

return true if range 2 is a permutation of range 1, i.e., both ranges must contain the same elements, but not necessarily in the same order

returns true if the input range is a max heap and false otherwise

returns the first position where the input range is no longer a max heap

Traversing Ranges Traversal

applies predicate 'f' to all elements in the input range [begin, end)

applies predicate 'f' to all elements in the input range [begin, begin+n)

Copying / Moving Elements Copying/Moving Copy/Move

copies all elements in the input range to a target (range) beginning at 'target_begin' and returns an iterator one behind the last target value;
the target must be able to recieve distance(begin,end) many elements

copies all elements in the range starting at 'begin' to a target (range) beginning at 'target_begin' and returns an iterator one behind the last target value;
the target must be able to recieve 'n' elements

copies all elements in the input range to a target (range) ending at 'target_end' and returns an iterator to the first target value;
the target must be able to recieve distance(begin,end) many elements

copies all elements in the input range for which 'select' yields true to a target (range) beginning at 'tgt' and returns an iterator one behind the last target value;
the target must be able to recieve the copied elements

moves all elements in the input range to a target (range) beginning at 'target_begin' and returns an iterator one behind the last target value;
the target must be able to recieve distance(begin,end) many elements

moves all elements in the input range to a target (range) ending at 'target_end' and returns an iterator to the first target value;
the target must be able to recieve distance(begin,end) many elements

Random Sampling

Selects 'n' elements (without replacement) with equal probability from an input population range using a random_generator (uniform random bit engine) and writes them to an output range.

Reordering Elements Reordering Reorder

Shifting Shift

reverses the order of the elements in the input range

copies all elements in the input range to an output (range) beginning at 'out' and returns an iterator one behind the last output value;
the output must be able to recieve distance(begin,end) many elements

performs a cyclic left rotation: elements in the range [begin, new_first) are put behind 'end' (in their original order) so that 'new_fist'

TODO

Randomly

TODO

Swapping Swap

TODO

Sorting Sort

TODO

returns true if the input range is sorted and false otherwise;
the 2^nd version uses 'compare' for comparing elements, while the 1^st version uses operator<

returns the first position where the input range is no longer sorted;
the 2^nd version uses 'compare' for comparing elements, while the 1^st version uses operator<