STL 中 algorithm 使用——总介绍

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