<算法><algorithm>

定义执行算法的 C++ 标准库容器模板函数。Defines C++ Standard Library container template functions that perform algorithms.

语法Syntax

(see relevant links below for specific algorithm syntax)

备注Remarks

C++ 标准库算法可在多种数据结构上运算,因此属于通用算法。The C++ Standard Library algorithms are generic because they can operate on a variety of data structures. 可用 C++ 标准库运算的数据结构不仅包括 C++ 标准库容器类(例如 vectorlist),还包括程序定义的数据结构和满足特定算法要求的元素数组。The data structures that they can operate on include not only the C++ Standard Library container classes such as vector and list, but also program-defined data structures and arrays of elements that satisfy the requirements of a particular algorithm. C++ 标准库算法通过迭代器间接访问并遍历容器元素来实现这种通用性。C++ Standard Library algorithms achieve this level of generality by accessing and traversing the elements of a container indirectly through iterators.

C++ 标准库算法处理迭代器范围通常是由其开始或末尾位置指定。C++ Standard Library algorithms process iterator ranges that are typically specified by their beginning or ending positions. 引用的范围必须有效,即范围中的所有指针必须可以取消引用,并且在每个范围的序列中,可从第一个位置递增到达最后一个位置。The ranges referred to must be valid in the sense that all pointers in the ranges must be dereferenceable and, within the sequences of each range, the last position must be reachable from the first by incrementation.

C++ 标准库算法扩展了由每个 C++ 标准库容器的运算和成员函数支持的操作,并允许同时处理不同类型的容器对象。The C++ Standard Library algorithms extend the actions supported by the operations and member functions of each C++ Standard Library container and allow working, for example, with different types of container objects at the same time. 两个后缀已用于传递与算法目的相关的信息。Two suffixes have been used to convey information about the purpose of the algorithms.

  • _if 后缀指示将算法用于对元素的值(而非元素本身的值)产生作用的函数对象。The _if suffix indicates that the algorithm is used with function objects operating on the values of the elements rather than on the values of the elements themselves. find_if 算法查找其值满足函数对象指定的条件的元素,find 算法搜索特定值。The find_if algorithm looks for elements whose values satisfy the criterion specified by a function object, and the find algorithm searches for a particular value.

  • _copy 后缀指示算法不仅操作元素的值,还将修改的值复制到目标范围。The _copy suffix indicates that the algorithm not only manipulates the values of the elements but also copies the modified values into a destination range. reverse 算法反向排序范围中的元素,reverse_copy 算法还将结果复制到目标范围。The reverse algorithm reverses the order of the elements within a range, and the reverse_copy algorithm also copies the result into a destination range.

C++ 标准库算法通常会按照其目的或需求相关指示信息进行分组。C++ Standard Library algorithms are often classified into groups that indicate something about their purpose or requirements. 这些包括更改元素值的修改算法和不更改元素值的非修改算法。These include modifying algorithms that change the value of elements as compared with non-modifying algorithms that do not. 改变算法将更改元素顺序,但不更改其元素的值。Mutating algorithms change the order of elements, but not the values of their elements. 移除算法可将元素从范围或范围副本中消除。Removing algorithms can eliminate elements from a range or a copy of a range. 排序算法重新排序以各种方式范围中的元素,并已排序的范围算法只作用于其元素具有以特定方式排序的范围。Sorting algorithms reorder the elements in a range in various ways and sorted range algorithms only act on ranges whose elements have been sorted in a particular way.

为数值处理提供的 C++ 标准库数值算法具有自己的标头文件 <numeric>,而函数对象和适配器则在标头 <functional> 中定义。返回布尔值的函数对象称为谓词。The C++ Standard Library numeric algorithms that are provided for numerical processing have their own header file <numeric>, and function objects and adaptors are defined in the header <functional> Function objects that return Boolean values are known as predicates. 默认二元谓词是比较 operator<The default binary predicate is the comparison operator<. 通常,排序的元素需小于比较元素,因此,给定任意两个元素,可以确定它们是等效的(即两者均不小于对方)或其中一个小于另一个。In general, the elements being ordered need to be less than comparable so that, given any two elements, it can be determined either that they are equivalent (in the sense that neither is less than the other) or that one is less than the other. 这将导致在非等效元素之间进行排序。This results in an ordering among the nonequivalent elements.

函数模板Function templates

函数模板Function template 描述Description
adjacent_findadjacent_find 搜索相等或满足指定条件的两个相邻元素。Searches for two adjacent elements that are either equal or satisfy a specified condition.
all_ofall_of 返回 ,则返回 true位于给定范围中的每个元素满足条件时。Returns true when a condition is present at each element in the given range.
any_ofany_of 返回 ,则返回 true满足条件时指定的元素范围中的至少一次。Returns true when a condition is present at least once in the specified range of elements.
binary_searchbinary_search 测试已排序的范围中是否有等于指定值的元素,或在二元谓词指定的意义上与指定值等效的元素。Tests whether there is an element in a sorted range that is equal to a specified value or that is equivalent to it in a sense specified by a binary predicate.
copycopy 将一个源范围中的元素值分配到目标范围,循环访问元素的源序列并将它们分配在一个向前方向的新位置。Assigns the values of elements from a source range to a destination range, iterating through the source sequence of elements and assigning them new positions in a forward direction.
copy_backwardcopy_backward 将一个源范围中的元素值分配到目标范围,循环访问元素的源序列并将它们分配在一个向后方向的新位置。Assigns the values of elements from a source range to a destination range, iterating through the source sequence of elements and assigning them new positions in a backward direction.
copy_ifcopy_if 测试某个给定范围内复制所有元素 ,则返回 true针对指定的条件Copy all elements in a given range that test true for a specified condition
copy_ncopy_n 复制指定数量的元素。Copies a specified number of elements.
countcount 返回范围中其值与指定值匹配的元素的数量。Returns the number of elements in a range whose values match a specified value.
count_ifcount_if 返回范围中其值与指定条件匹配的元素的数量。Returns the number of elements in a range whose values match a specified condition.
equalequal 逐个元素比较两个范围是否相等或是否在二元谓词指定的意义上等效。Compares two ranges element by element either for equality or equivalence in a sense specified by a binary predicate.
equal_rangeequal_range 在排序的范围中查找符合以下条件的位置对:第一个位置小于或等效于指定元素的位置,第二个位置大于此元素位置,等效意义或用于在序列中建立位置的排序可通过二元谓词指定。Finds a pair of positions in an ordered range, the first less than or equivalent to the position of a specified element and the second greater than the element's position, where the sense of equivalence or ordering used to establish the positions in the sequence may be specified by a binary predicate.
fillfill 将相同的新值分配给指定范围中的每个元素。Assigns the same new value to every element in a specified range.
fill_nfill_n 将新值分配给以特定元素开始的范围中的指定数量的元素。Assigns a new value to a specified number of elements in a range starting with a particular element.
findfind 在范围中找到具有指定值的元素的第一个匹配项位置。Locates the position of the first occurrence of an element in a range that has a specified value.
find_endfind_end 在范围中查找与指定序列相同的最后一个序列,或在二元谓词指定的意义上等效的最后一个序列。Looks in a range for the last subsequence that is identical to a specified sequence or that is equivalent in a sense specified by a binary predicate.
find_first_offind_first_of 在目标范围中搜索若干值中任意值的第一个匹配项,或搜索在二元谓词指定的意义上等效于指定元素集的若干元素中任意元素的第一个匹配项。Searches for the first occurrence of any of several values within a target range or for the first occurrence of any of several elements that are equivalent in a sense specified by a binary predicate to a specified set of the elements.
find_iffind_if 在范围中找到满足指定条件的元素的第一个匹配项位置。Locates the position of the first occurrence of an element in a range that satisfies a specified condition.
find_if_notfind_if_not 返回指示的范围中不满足条件的第一个元素。Returns the first element in the indicated range that does not satisfy a condition.
for_eachfor_each 将指定的函数对象按向前顺序应用于范围中的每个元素并返回此函数对象。Applies a specified function object to each element in a forward order within a range and returns the function object.
generategenerate 将函数对象生成的值分配给范围中的每个元素。Assigns the values generated by a function object to each element in a range.
generate_ngenerate_n 将函数对象生成的值分配给范围中指定数量的元素,并返回到超出最后一个分配值的下一位置。Assigns the values generated by a function object to a specified number of element is a range and returns to the position one past the last assigned value.
includesincludes 测试一个排序的范围是否包含另一排序范围中的所有元素,其中元素之间的排序或等效条件可通过二元谓词指定。Tests whether one sorted range contains all the elements contained in a second sorted range, where the ordering or equivalence criterion between elements may be specified by a binary predicate.
inplace_mergeinplace_merge 将两个连续的排序范围中的元素合并为一个排序范围,其中排序条件可通过二元谓词指定。Combines the elements from two consecutive sorted ranges into a single sorted range, where the ordering criterion may be specified by a binary predicate.
is_heapis_heap 返回 ,则返回 true如果指定范围中的元素形成堆。Returns true if the elements in the specified range form a heap.
is_heap_untilis_heap_until 返回 ,则返回 true如果指定的范围形成一个堆,直到最后一个元素。Returns true if the specified range forms a heap until the last element.
is_partitionedis_partitioned 返回 ,则返回 true如果给定范围中的所有元素的都测试true对某个条件都测试的所有元素之前falseReturns true if all the elements in the given range that test true for a condition come before any elements that test false.
is_permutationis_permutation 确定给定范围的元素是否形成有效排列。Determines whether the elements in a given range form a valid permutation.
is_sortedis_sorted 返回 ,则返回 true如果指定范围中的元素按顺序排序。Returns true if the elements in the specified range are in sorted order.
is_sorted_untilis_sorted_until 返回 ,则返回 true如果指定范围中的元素按顺序排序。Returns true if the elements in the specified range are in sorted order.
iter_swapiter_swap 交换由一对指定迭代器引用的两个值。Exchanges two values referred to by a pair of specified iterators.
lexicographical_comparelexicographical_compare 逐个元素比较两个序列以确定其中的较小序列。Compares element by element between two sequences to determine which is lesser of the two.
lower_boundlower_bound 在排序的范围中查找其值大于或等效于指定值的第一个元素的位置,其中排序条件可通过二元谓词指定。Finds the position of the first element in an ordered range that has a value greater than or equivalent to a specified value, where the ordering criterion may be specified by a binary predicate.
make_heapmake_heap 将指定范围中的元素转换到第一个元素是最大元素的堆中,其中排序条件可通过二元谓词指定。Converts elements from a specified range into a heap in which the first element is the largest and for which a sorting criterion may be specified with a binary predicate.
maxmax 比较两个对象并返回较大对象,其中排序条件可通过二元谓词指定。Compares two objects and returns the larger of the two, where the ordering criterion may be specified by a binary predicate.
max_elementmax_element 在指定范围中查找最大元素的第一个匹配项,其中排序条件可通过二元谓词指定。Finds the first occurrence of largest element in a specified range where the ordering criterion may be specified by a binary predicate.
mergemerge 将两个排序的源范围中的所有元素合并为一个排序的目标范围,其中排序条件可通过二元谓词指定。Combines all the elements from two sorted source ranges into a single, sorted destination range, where the ordering criterion may be specified by a binary predicate.
minmin 比较两个对象并返回较小对象,其中排序条件可通过二元谓词指定。Compares two objects and returns the lesser of the two, where the ordering criterion may be specified by a binary predicate.
min_elementmin_element 在指定范围中查找最小元素的第一个匹配项,其中排序条件可通过二元谓词指定。Finds the first occurrence of smallest element in a specified range where the ordering criterion may be specified by a binary predicate.
minmaxminmax 比较两个输入参数,并按最小到最大的顺序将它们作为参数对返回。Compares two input parameters and returns them as a pair, in order of least to greatest.
minmax_elementminmax_element 在一次调用中执行 min_elementmax_element 执行的操作。Performs the work performed by min_element and max_element in one call.
mismatchmismatch 逐个元素比较两个范围是否相等或是否在二元谓词指定的意义上等效,并找到出现不同的第一个位置。Compares two ranges element by element either for equality or equivalent in a sense specified by a binary predicate and locates the first position where a difference occurs.
<alg> move<alg> move 移动与指定范围关联的元素。Move elements associated with a specified range.
move_backwardmove_backward 将一个迭代器的元素移动到另一迭代器。Moves the elements of one iterator to another. 移动从指定范围的最后一个元素开始,并在此范围的第一个元素结束。The move starts with the last element in a specified range, and ends with the first element in that range.
next_permutationnext_permutation 重新排序范围中的元素,以便使用按字典顺序的下一个更大排列(如果有)替换原有排序,其中“下一个”的意义可通过二元谓词指定。Reorders the elements in a range so that the original ordering is replaced by the lexicographically next greater permutation if it exists, where the sense of next may be specified with a binary predicate.
none_ofnone_of 返回 ,则返回 true满足条件时永远不会在给定范围中没有元素。Returns true when a condition is never present among elements in the given range.
nth_elementnth_element 对范围内的元素分区,正确找到范围中序列的第 n 个元素,以使序列中位于此元素之前的所有元素小于或等于此元素,位于此元素之后的所有元素大于或等于此元素。Partitions a range of elements, correctly locating the nth element of the sequence in the range so that all the elements in front of it are less than or equal to it and all the elements that follow it in the sequence are greater than or equal to it.
partial_sortpartial_sort 将范围中指定数量的较小元素按非降序顺序排列,或根据二元谓词指定的排序条件排列。Arranges a specified number of the smaller elements in a range into a nondescending order or according to an ordering criterion specified by a binary predicate.
partial_sort_copypartial_sort_copy 将源范围中的元素复制到目标范围,其中源元素按降序或二元谓词指定的其他顺序排序。Copies elements from a source range into a destination range where the source elements are ordered by either less than or another specified binary predicate.
partitionpartition 将范围中的元素分为两个不相交的集,满足一元谓词的元素在不满足一元谓词的元素之前。Classifies elements in a range into two disjoint sets, with those elements satisfying a unary predicate preceding those that fail to satisfy it.
partition_copypartition_copy 是的条件的元素复制 ,则返回 true到一个目标和条件为false到另一个。Copies elements for which a condition is true to one destination, and for which the condition is false to another. 元素必须来自于指定范围。The elements must come from a specified range.
partition_pointpartition_point 返回给定范围中不满足条件的第一个元素。Returns the first element in the given range that does not satisfy the condition. 元素经过排序,满足条件的元素在不满足条件的元素之前。The elements are sorted so that those that satisfy the condition come before those that do not.
pop_heappop_heap 移除从堆顶到范围中倒数第二个位置之间的最大元素,然后将剩余元素形成新堆。Removes the largest element from the front of a heap to the next-to-last position in the range and then forms a new heap from the remaining elements.
prev_permutationprev_permutation 重新排序范围中的元素,以便使用按字典顺序的下一个更大排列(如果有)替换原有排序,其中“下一个”的意义可通过二元谓词指定。Reorders the elements in a range so that the original ordering is replaced by the lexicographically next greater permutation if it exists, where the sense of next may be specified with a binary predicate.
push_heappush_heap 将范围末尾的元素添加到包括范围中前面元素的现有堆中。Adds an element that is at the end of a range to an existing heap consisting of the prior elements in the range.
random_shufflerandom_shuffle 将范围中 N 个元素的序列重新排序为随机 N! 种序列中的Rearranges a sequence of N elements in a range into one of N! 可能排列之一。possible arrangements selected at random.
removeremove 从给定范围中消除指定值,而不影响剩余元素的顺序,并返回不包含指定值的新范围的末尾。Eliminates a specified value from a given range without disturbing the order of the remaining elements and returning the end of a new range free of the specified value.
remove_copyremove_copy 将源范围中的元素复制到目标范围(不复制具有指定值的元素),而不影响剩余元素的顺序,并返回新目标范围的末尾。Copies elements from a source range to a destination range, except that elements of a specified value are not copied, without disturbing the order of the remaining elements and returning the end of a new destination range.
remove_copy_ifremove_copy_if 将源范围中的元素复制到目标范围(不复制满足谓词的元素),而不影响剩余元素的顺序,并返回新目标范围的末尾。Copies elements from a source range to a destination range, except that satisfying a predicate are not copied, without disturbing the order of the remaining elements and returning the end of a new destination range.
remove_ifremove_if 从给定范围中消除满足谓词的元素,而不影响剩余元素的顺序,并返回不包含指定值的新范围的末尾。Eliminates elements that satisfy a predicate from a given range without disturbing the order of the remaining elements and returning the end of a new range free of the specified value.
replacereplace 检查范围中的每个元素,并替换与指定值匹配的元素。Examines each element in a range and replaces it if it matches a specified value.
replace_copyreplace_copy 检查源范围中的每个元素,并替换与指定值匹配的元素,同时将结果复制到新的目标范围。Examines each element in a source range and replaces it if it matches a specified value while copying the result into a new destination range.
replace_copy_ifreplace_copy_if 检查源范围中的每个元素,并替换满足指定谓词的元素,同时将结果复制到新的目标范围。Examines each element in a source range and replaces it if it satisfies a specified predicate while copying the result into a new destination range.
replace_ifreplace_if 检查范围中的每个元素,并替换满足指定谓词的元素。Examines each element in a range and replaces it if it satisfies a specified predicate.
reversereverse 反转范围中元素的顺序。Reverses the order of the elements within a range.
reverse_copyreverse_copy 反转源范围中元素的顺序,同时将这些元素复制到目标范围Reverses the order of the elements within a source range while copying them into a destination range
rotaterotate 交换两个相邻范围中的元素。Exchanges the elements in two adjacent ranges.
rotate_copyrotate_copy 交换源范围中两个相邻范围内的元素,并将结果复制到目标范围。Exchanges the elements in two adjacent ranges within a source range and copies the result to a destination range.
searchsearch 在目标范围中搜索其元素与给定序列中的元素相等或在二元谓词指定的意义上等效于给定序列中的元素的序列的第一个匹配项。Searches for the first occurrence of a sequence within a target range whose elements are equal to those in a given sequence of elements or whose elements are equivalent in a sense specified by a binary predicate to the elements in the given sequence.
search_nsearch_n 在范围中搜索具有特定值或按二元谓词的指定与此值相关的指定数量的元素。Searches for the first subsequence in a range that of a specified number of elements having a particular value or a relation to that value as specified by a binary predicate.
set_differenceset_difference 将属于一个排序的源范围、但不属于另一排序的源范围的所有元素相并到一个排序的目标范围,其中排序条件可通过二元谓词指定。Unites all of the elements that belong to one sorted source range, but not to a second sorted source range, into a single, sorted destination range, where the ordering criterion may be specified by a binary predicate.
set_intersectionset_intersection 将属于两个排序的源范围的所有元素相并为一个排序的目标范围,其中排序条件可通过二元谓词指定。Unites all of the elements that belong to both sorted source ranges into a single, sorted destination range, where the ordering criterion may be specified by a binary predicate.
set_symmetric_differenceset_symmetric_difference 将属于一个而不是两个排序的源范围的所有元素相并为一个排序的目标范围,其中排序条件可通过二元谓词指定。Unites all of the elements that belong to one, but not both, of the sorted source ranges into a single, sorted destination range, where the ordering criterion may be specified by a binary predicate.
set_unionset_union 将至少属于两个排序的源范围之一的所有元素相并为一个排序的目标范围,其中排序条件可通过二元谓词指定。Unites all of the elements that belong to at least one of two sorted source ranges into a single, sorted destination range, where the ordering criterion may be specified by a binary predicate.
sortsort 将指定范围中的元素按非降序顺序排列,或根据二元谓词指定的排序条件排列。Arranges the elements in a specified range into a nondescending order or according to an ordering criterion specified by a binary predicate.
shuffleshuffle 使用随机数生成器重新排列给定范围中的元素。Shuffles (rearranges) elements for a given range using a random number generator.
sort_heapsort_heap 将堆转换为排序的范围。Converts a heap into a sorted range.
stable_partitionstable_partition 将范围中的元素分为两个不相交的集,满足一元谓词的元素在不满足一元谓词的元素之前,并保留等效元素的相对顺序。Classifies elements in a range into two disjoint sets, with those elements satisfying a unary predicate preceding those that fail to satisfy it, preserving the relative order of equivalent elements.
stable_sortstable_sort 将指定范围中的元素按非降序顺序排列,或根据二元谓词指定的排序条件排列,并保留等效元素的相对顺序。Arranges the elements in a specified range into a nondescending order or according to an ordering criterion specified by a binary predicate and preserves the relative ordering of equivalent elements.
swapswap 在两种类型的对象之间交换元素值,将第一个对象的内容分配给第二个对象,将第二个对象的内容分配给第一个对象。Exchanges the values of the elements between two types of objects, assigning the contents of the first object to the second object and the contents of the second to the first.
swap_rangesswap_ranges 将一个范围中的元素与另一大小相等的范围中的元素交换。Exchanges the elements of one range with the elements of another, equal sized range.
transformtransform 将指定的函数对象应用于源范围中的每个元素或两个源范围中的元素对,并将函数对象的返回值复制到目标范围。Applies a specified function object to each element in a source range or to a pair of elements from two source ranges and copies the return values of the function object into a destination range.
uniqueunique 移除指定范围中彼此相邻的重复元素。Removes duplicate elements that are adjacent to each other in a specified range.
unique_copyunique_copy 将源范围中的元素复制到目标范围,彼此相邻的重复元素除外。Copies elements from a source range into a destination range except for the duplicate elements that are adjacent to each other.
upper_boundupper_bound 在排序的范围中查找其值大于指定值的第一个元素的位置,其中排序条件可通过二元谓词指定。Finds the position of the first element in an ordered range that has a value that is greater than a specified value, where the ordering criterion may be specified by a binary predicate.

请参阅See also

头文件引用Header Files Reference
C++ 标准库中的线程安全Thread Safety in the C++ Standard Library
C++ 标准库参考C++ Standard Library Reference