## Nonmodifying Sequence Algorithms

### Search Algorithms

`adjacent_find()` Finds the first instance of two consecutive elements that are equal to each other or are equivalent to each other as specified by a predicate `O(N)`
`find()`, `find_if()` Finds the first element that matches a value or causes a predicate to return `true` `O(N)`
`find_first_of()` Like `find`, but searches for one of several elements at the same time `O(N*M) `
`find_if_not()` Finds the first element that causes a predicate to return `false` `O(N) `
`find_end()` Finds the last subsequence in a sequence that matches another sequence or whose elements are equivalent, as specified by a predicate `O(M*(N-M))`
`search()` Finds the first subsequence in a sequence that matches another sequence or whose elements are equivalent, as specified by a predicate `O(N*M)`
`search_n()` Finds the first instance of n consecutive elements that are equal to a given value or relate to that value according to a predicate `O(N)`

### Comparison Algorithms

`equal()` Determines whether two sequences are equal by checking whether parallel elements are equal or match a predicate
`mismatch()` Returns the first element in each sequence that does not match the element in the same location in the other sequence
`lexicographical_compare()` Compares two sequences to determine their “lexicographical” ordering. This algorithm compares each element of the first sequence with its equivalent element in the second. If one element is less than the other, that sequence is lexicographically first. If the elements are equal, it compares the next elements in order
`lexicographical_compare_three_way()` Compares two sequences to determine their “lexicographical” ordering using C++20 three-way comparisons and returns a comparison category type (`strong_ordering`, `weak_ordering`, or `partial_ordering`).

### Counting Algorithms

`all_of()` Returns `true` if a given predicate returns `true` for all the elements in the sequence or if the sequence is empty; `false` otherwise
`any_of()` Returns `true` if a given predicate returns `true` for at least one element in the sequence; `false` otherwise
`none_of()` Returns `true` if a given predicate returns `false` for all the elements in the sequence or if the sequence is empty; `false` otherwise
`count()`, `count_if()` Counts the number of elements matching a value or that cause a predicate to return `true`

## Modifying Sequence Algorithms

• `copy()`
• `copy_backward()`
Copies elements from one sequence to another
`copy_if()` Copies elements for which a predicate returns `true` from one sequence to another
`copy_n()` Copies n elements from one sequence to another
`fill()` Sets all elements in the sequence to a new value
`fill_n()` Sets the first n elements in the sequence to a new value
`generate()` Calls a specified function to generate a new value for each element in the sequence
`generate_n()` Calls a specified function to generate a new value for the first n elements in the sequence
• `move()`
• `move_backward()`
Moves elements from one sequence to another using efficient move semantics
• `remove()`
• `remove_if()`
• `remove_copy()`
• `remove_copy_if()`
Removes all elements that match a given value or that cause a predicate to return true, either in place or by copying the results to a different sequence
• `replace()`
• `replace_if()`
• `replace_copy()`
• `replace_copy_if()`
Replaces all elements matching a value or that cause a predicate to return true with a new element, either in place or by copying the results to a different sequence
• `reverse()`
• `reverse_copy()`
Reverses the order of the elements in the sequence, either in place or by copying the results to a different sequence
• `rotate()`
• `rotate_copy()`
Swaps the first and second “halves” of the sequence, either in place or by copying the results to a different sequence. The two subsequences to be swapped need not be equal in size
`sample()` Selects n random elements from the sequence
• `shift_left()`
• `shift_right()`
Shifts the elements in a sequence left or right by a given number of positions. Elements are moved to their new position. Elements that fall of either end of the sequence are removed. shift_left() returns an iterator to the end of the new sequence; shift_right() returns an iterator to the beginning of the new sequence
• `shuffle()`
• `random_shuffle()`
random_shuffle() Shuffles the sequence by randomly reordering the elements. It is possible to specify the properties of the random number generator used for shuffling. random_shuffle() is deprecated since C++14, and is removed from C++17
`transform()` Calls a unary function on each element of a sequence or a binary function on parallel elements of two sequences, and stores the results in a destination sequence. If the source and destination sequences are the same, the transformation happens in-place
• `unique()`
• `unique_copy()`
Removes consecutive duplicates from the sequence, either in place or by copying results to a different sequence

## Operational Algorithms

算法名称 算法说明
`for_each()` Executes a function on each element in the sequence. The sequence is specified with a begin and end iterator
`for_each_n()` Similar to for_each() but only processes the first n elements in the sequence. The sequence is specified by a begin iterator and a number of elements (n)

## Swap Algorithms

算法名称 算法说明
• `iter_swap()`
• `swap_ranges()`
Swaps two elements or sequences of elements

## Partition Algorithms

算法名称 算法说明 复杂度
`is_partitioned()` Returns true if all elements for which a predicate returns true are before all elements for which it returns false Linear
`partition()` Sorts the sequence such that all elements for which a predicate returns true are before all elements for which it returns false, without preserving the original order of the elements within each partition Linear
`stable_partition()` Sorts the sequence such that all elements for which a predicate returns true are before all elements for which it returns false, while preserving the original order of the elements within each partition Linear logarithmic
`partition_copy()` Copies elements from one sequence to two different sequences. The target sequence is selected based on the result of a predicate, either true or false Linear
`partition_point()` Returns an iterator such that all elements before this iterator return true for a predicate and all elements after this iterator return false for that predicate Logarithmic

## Sorting Algorithms

算法名称 算法说明 复杂度
• `iter_swap()`
• `swap_ranges()`
Checks if a sequence is sorted or which subsequence is sorted Linear
`nth_element()` Relocates the n thelement of the sequence such that the element in the position pointed to by n this the element that would be in that position if the whole range were sorted, and it rearranges all elements such that all elements preceding the n thelement are less than the new n thelement, and the ones following it are greater than the new n thelement Linear
• `partial_sort()`
• `partial_sort_copy()`
partial_sort_copy() Partially sorts the sequence: the first n elements (specified by iterators) are sorted; the rest are not. They are sorted either in place or by copying them to a new sequence Linear logarithmic
• `stable_sort()`
• `sort()`
Sorts elements in place, either preserving the order of duplicate elements (stable) or not Linear logarithmic

## Binary Search Algorithms

算法名称 算法说明
`lower_bound()` Finds the first element in a sequence not less than (that is, greater or equal to) a given value
`upper_bound()` Finds the first element in a sequence greater than a given value
`equal_range()` Returns a pair containing the result of both lower_bound() and upper_bound()
`binary_search()` Returns true if a given value is found in a sequence; false otherwise

## Set Algorithms

算法名称 算法说明 复杂度
`inplace_merge()` Merges two sorted sequences in place Linear logarithmic
`merge()` Merges two sorted sequences by copying them to a new sequence Linear
`includes()` Determines whether every element from one sorted sequence is in another sorted sequence Linear
• `set_union()`
• `set_intersection()`
• `set_difference()`
• `set_symmetric_difference()`
Performs the specified set operation on two sorted sequences, copying results to a third sorted sequence Linear

## Heap Algorithms

算法名称 算法说明 复杂度
`is_heap()` Checks whether a range of elements is a heap Linear
`is_heap_until()` Finds the largest subrange in the given range of elements that is a heap Linear
`make_heap()` Creates a heap from a range of elements Linear
• `push_heap()`
• `pop_heap()`
Adds an element to, or removes an element from, a heap Logarithmic
`sort_heap()` Converts a heap into a range of ascending sorted elements Linear logarithmic

## Minimum/Maximum Algorithms

算法名称 算法说明
`clamp()` Makes sure a value (v) is between a given minimum (lo) and maximum (hi). Returns a reference to lo if v < lo; returns a reference to hi if v > hi; otherwise returns a reference to v.
• `min()`
• `max()`
Returns the minimum or maximum of two or more values
`minmax()` Returns the minimum and maximum of two or more values as a pair
• `min_element() `
• `max_element()`
Returns the minimum or maximum element in a sequence
`minmax_element()` Returns the minimum and maximum element in a sequence as a pair

## Numerical Processing Algorithms

算法名称 算法说明
`iota()` Fills a sequence with successively incrementing values starting with a given value
`adjacent_difference()` Generates a new sequence in which each element is the difference (or other binary operation) of the second and first of each adjacent pair of elements in the source sequence
`partial_sum()` Generates a new sequence in which each element is the sum (or other binary operation) of an element and all its preceding elements in the source sequence
• `exclusive_scan()`
• `inclusive_scan()`
inclusive_scan() These are similar to partial_sum(). An inclusive scan is identical to a partial sum if the given summation operation is associative. However, inclusive_scan() sums in a nondeterministic order, while partial_sum() left to right, so for nonassociative summation operations the result of the former is nondeterministic. The exclusive_scan() algorithm also sums in a nondeterministic order. For inclusive_scan(), the i thelement is included in the i thsum, just as for partial_sum(). For exclusive_scan(), the i thelement is not included in the i thsum
• `transform_exclusive_scan()`
• `transform_inclusive_scan()`
Applies a transformation to each element in a sequence, then performs an exclusive/inclusive scan
`accumulate()` “Accumulates” the values of all the elements in a sequence. The default behavior is to sum the elements, but the caller can supply a different binary function instead
`inner_product()` Similar to accumulate(), but works on two sequences. This algorithm calls a binary function (multiplication by default) on parallel elements in the sequences, accumulating the result using another binary function (addition by default). If the sequences represent mathematical vectors, the algorithm calculates the dot product of the vectors
`reduce()` Similar to accumulate(), but supports parallel execution. The order of evaluation for reduce() is nondeterministic, while it’s from left to right for accumulate(). This means that the behavior of the former is nondeterministic if the given binary operation is not associative or not commutative
`transform_reduce()` Applies a transformation to each element in a sequence, then performs a reduce()

## Permutation Algorithms

算法名称 算法说明 复杂度
`is_permutation()` Returns true if the elements in one range are a permutation of the elements in another range Quadratic
• `next_permutation()`
• `prev_permutation()`
Modifies the sequence by transforming it into its “next” or “previous” lexicographical permutation. Successive calls to one or the other will permute the sequence into all possible permutations of its elements, if you start with a properly sorted sequence. This algorithm returns false if no more permutations exist Linear