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