Question

STL 算法库（由头文件 algorithm 和 numeric 支持）提供了大量基于迭代器的非成员模板函数。正如第 16 章介绍的，选择的模板参数名指出了特定参数应模拟的概念。例如，ForwardIterator 用于指出，参数至少应模拟正向迭代器的要求；Predicate 用于指出，参数应是一个接受一个参数并返回 bool 值的函数对象。C++标准将算法分成 4 组：非修改式序列操作、修改式序列操作、排序和相关运算符以及数值操作（C++11 将数值操作从 STL 移到了 numeric 库中，但这不影响它们的用法）。序列操作（sequence operation）表明，函数将接受两个迭代器作为参数，它们定义了要操作的区间或序列。修改式（mutating）意味着函数可以修改容器的内容。

G.5.1 非修改式序列操作

表 G.13 对非修改式序列操作进行了总结。这里没有列出参数，而重载函数只列出了一次。表后做了更详细的说明，其中包括原型。因此，可以浏览该表，以了解函数的功能，如果对某个函数非常感兴趣，则可以了解其细节。

表 G.13 非修改式序列操作

函 数	描 述
all_of( )	如果对于所有元素的谓词测试都为 true，则返回 true。这是 C++11 新增的
any_of( )	只要对于任何一个元素的谓词测试为 true，就返回 true。这是 C++11 新增的
none_of( )	如果对于所有元素的谓词测试都为 false，则返回 true。这是 C++11 新增的
for_each( )	将一个非修改式函数对象用于区间中的每个成员
find( )	在区间中查找某个值首次出现的位置
find_if( )	在区间中查找第一个满足谓词测试条件的值
find_if_not( )	在区间中查找第一个不满足谓词测试条件的值。这是 C++11 新增的
find_end( )	在序列中查找最后一个与另一个序列匹配的值。匹配时可以使用等式或二元谓词
find_first_of( )	在第二个序列中查找第一个与第一个序列的值匹配的元素。匹配时可以使用等式或二元谓词
adjacent_find	查找第一个与其后面的元素匹配的元素。匹配时可以使用等式或二元谓词
count( )	返回特定值在区间中出现的次数
count_if( )	返回特定值与区间中的值匹配的次数，匹配时使用二元谓词
mismatch( )	查找区间中第一个与另一个区间中对应元素不匹配的元素，并返回指向这两个元素的迭代器。匹配时可以使用等式或二元谓词
equal( )	如果一个区间中的每个元素都与另一个区间中的相应元素匹配，则返回 true。匹配时可以使用等式或二元谓词
is_permutation( )	如果可通过重新排列第二个区间，使得第一个区间和第二个区间对应的元素都匹配，则返回 true，否则返回 false。匹配可以是相等，也可以使用二元谓词进行判断。这是 C++11 新增的
search( )	在序列中查找第一个与另一个序列的值匹配的值。匹配时可以使用等式或二元谓词
search_n( )	查找第一个由 n 个元素组成的序列，其中每个元素都与给定值匹配。匹配时可以使用等式或二元谓词

下面更详细地讨论这些非修改型序列操作。对于每个函数，首先列出其原型，然后做简要地描述。和前面一样，迭代器对指出了区间，而选择的模板参数名指出了迭代器的类型。通常，[first, last]区间指的是从 first 到 last（不包括 last）。有些函数接受两个区间，这两个区间的容器类型可以不同。例如，可以使用 equal( ) 来对链表和矢量进行比较。作为参数传递的函数是函数对象，这些函数对象可以是指针（如函数名），也可以是定义了( ) 操作的对象。正如第 16 章介绍的，谓词是接受一个参数的布尔函数，二元谓词是接受 2 个参数的布尔函数（函数可以不是 bool 类型，只要它对于 false 返回 0，对于 true 返回非 0 值）。

1．all_of( )（C++11）

如果对于区间[first, last]中的每个迭代器，pred(*i) 都为 true，或者该区间为空，则函数 all_of( ) 返回 true；否则返回 false。

2．any_of( )（C++11）

如果对于区间[first, last]中的每个迭代器，pred(*i) 都为 false，或者该区间为空，则函数 any_of( ) 返回 false；否则返回 true。

3．none_of( )（C++11）

如果对于区间[first, last]中的每个迭代器，pred(*i) 都为 false，或者该区间为空，则函数 all_of( ) 返回 true；否则返回 false。

4．for_each( )

for_each( ) 函数将函数对象 f 用于[first, last]区间中的每个元素，它也返回 f。

5．find( )

find( ) 函数返回一个迭代器，该迭代器指向区间[first, last]中第一个值为 value 的元素；如果没有找到这样的元素，则返回 last。

6．find_if( )

find_if( ) 函数返一个迭代器，该迭代器指向[first, last]区间中第一个对其调用函数对象 pred(*i) 时结果为 true 的元素；如果没有找到这样的元素，则返回 last。

7．find_if_not( )

find_if_not( ) 函数返一个迭代器，该迭代器指向[first, last]区间中第一个对其调用函数对象 pred(*i) 时结果为 false 的元素；如果没有找到这样的元素，则返回 last。

8．find_end( )

find_end( ) 函数返回一个迭代器，该迭代器指向[first1, last1] 区间中最后一个与[first2, last2] 区间的内容匹配的序列的第一个元素。第一个版本使用值类型的= =运算符来比较元素；第二个版本使用二元谓词函数对象 pred 来比较元素。也就是说，如果 pred(*it1, *it2) 为 true，则 it1 和 it2 指向的元素匹配。如果没有找到这样的元素，则它们都返回 last1。

9．find_first_of( )

find_first_of( ) 函数返回一个迭代器，该迭代器指向区间[first1, last1]中第一个与[first2, last2]区间中的任何元素匹配的元素。第一个版本使用值类型的= =运算符对元素进行比较；第二个版本使用二元谓词函数对象 pred 来比较元素。也就是说，如果 pred(*it1, *it2) 为 true，则 it1 和 it2 指向的元素匹配。如果没有找到这样的元素，则它们都将返回 last1。

10．adjacent_find( )

adjacent_find( ) 函数返回一个迭代器，该迭代器指向[first1, last1] 区间中第一个与其后面的元素匹配的元素。如果没有找到这样的元素，则返回 last。第一个版本使用值类型的= =运算符来对元素进行比较；第二个版本使用二元谓词函数对象 pred 来比较元素。也就是说，如果 pred(*it1, *it2) 为 true，则 it1 和 it2 指向的元素匹配。

11．count( )

count( ) 函数返回[first, last) 区间中与值 value 匹配的元素数目。对值进行比较时，将使用值类型的= =运算符。返回值类型为整型，它足以存储容器所能存储的最大元素数。

12．count_if( )

count if( ) 函数返回[first, last]区间中这样的元素数目，即将其作为参数传递给函数对象 pred 时，后者的返回值为 true。

13．mismatch( )

每个 mismatch( ) 函数都在[first1, last1) 区间中查找第一个与从 first2 开始的区间中相应元素不匹配的元素，并返回两个迭代器，它们指向不匹配的两个元素。如果没有发现不匹配的情况，则返回值为 pair<last1, first2 + (last1 - first1)>。第一个版本使用= =运算符来测试匹配情况；第二个版本使用二元谓词函数对象 pred 来比较元素。也就是说，如果 pred(*it1, *it2) 为 false，则 it1 和 it2 指向的元素不匹配。

14．equal( )

如果[first1, last1) 区间中每个元素都与以 first2 开始的序列中相应元素匹配，则 equal( ) 函数返回 true，否则返回 false。第一个版本使用值类型的= =运算符来比较元素；第二个版本使用二元谓词函数对象 pred 来比较元素。也就是说，如果 pred(*it1, *it2) 为 true，则 it1 和 it2 指向的元素匹配。

15．is_permutation( )（C++11）

如果通过对从 first2 开始的序列进行排列，可使其与区间[first1, last1]相应的元素匹配，则函数 is_permutation( ) 返回 true，否则返回 false。第一个版本使用值类型的==运算符来比较元素；第二个版本使用二元谓词函数对象 pred 来比较元素，也就是说，如果 pred(*it1, *it2) 为 true，则 it1 和 it2 指向的元素匹配。

16．search( )

search( ) 函数在[first1, last1]区间中搜索第一个与[first2, last2] 区间中相应的序列匹配的序列；如果没有找到这样的序列，则返回 last1。第一个版本使用值类型的= =运算符来对元素进行比较；第二个版本使用二元谓词函数对象 pred 来比较元素。也就是说，如果 pred(*it1, *it2) 为 true，则 it1 和 it2 指向的元素是匹配的。

17．search_n( )

search_n( ) 函数在[first1, last1) 区间中查找第一个与 count 个 value 组成的序列匹配的序列；如果没有找到这样的序列，则返回 last1。第一个版本使用值类型的= =运算符来对元素进行比较；第二个版本使用二元谓词函数对象 pred 来比较元素。也就是说，如果 pred(*it1, *it2) 为 true，则 it1 和 it2 指向的元素是匹配的。

G.5.2 修改式序列操作

表 G.14 对修改式序列操作进行了总结。其中没有列出参数，而重载函数也只列出了一次。表后做了更详细的说明，其中包括原型。因此，可以浏览该表，以了解函数的功能，如果对某个函数非常感兴趣，则可以了解其细节。

表 G.14 修改式序列操作

函 数	描 述
copy( )	将一个区间中的元素复制到迭代器指定的位置
copy_n( )	从一个迭代器指定的地方复制 n 个元素到另一个迭代器指定的地方，这是 C++11 新增的
copy_if( )	将一个区间中满足谓词测试的元素复制到迭代器指定的地方，这是 C++11 新增的
copy_backward( )	将一个区间中的元素复制到迭代器指定的地方。复制时从区间结尾开始，由后向前进行
move( )	将一个区间中的元素移到迭代器指定的地方，这是 C++11 新增的
move_backward( )	将一个区间中的元素移到迭代器指定的地方；移动时从区间结尾开始，由后向前进行。这是 C++11 新增的
swap( )	交换引用指定的位置中存储的值
swap_ranges( )	对两个区间中对应的值进行交换
iter_swap( )	交换迭代器指定的位置中存储的值
transform( )	将函数对象用于区间中的每一个元素（或区间对中的每对元素），并将返回的值复制到另一个区间的相应位置
replace( )	用另外一个值替换区间中某个值的每个实例
replace_if( )	如果用于原始值的谓词函数对象返回 true，则使用另一个值来替换区间中某个值的所有实例
replace_copy( )	将一个区间复制到另一个区间中，使用另外一个值替换指定值的每个实例
replace_copy_if( )	将一个区间复制到另一个区间，使用指定值替换谓词函数对象为 true 的每个值
fill( )	将区间中的每一个值设置为指定的值
fill_n( )	将 n 个连续元素设置为一个值
generate( )	将区间中的每个值设置为生成器的返回值，生成器是一个不接受任何参数的函数对象
generate_n( )	将区间中的前 n 个值设置为生成器的返回值，生成器是一个不接受任何参数的函数对象
remove( )	删除区间中指定值的所有实例，并返回一个迭代器，该迭代器指向得到的区间的超尾
remove_if( )	将谓词对象返回 true 的值从区间中删除，并返回一个迭代器，该迭代器指向得到的区间的超尾
remove_copy( )	将一个区间中的元素复制到另一个区间中，复制时忽略与指定值相同的元素
remove_copy_if( )	将一个区间中的元素复制到另一个区间中，复制时忽略谓词函数对象返回 true 的元素
unique( )	将区间内两个或多个相同元素组成的序列压缩为一个元素
unique_copy( )	将一个区间中的元素复制到另一个区间中，并将两个或多个相同元素组成的序列压缩为一个元素
reverse( )	反转区间中的元素的排列顺序
reverse_copy( )	按相反的顺序将一个区间中的元素复制到另一个区间中
rotate( )	将区间中的元素循环排列，并将元素左转
rotate_copy( )	以旋转顺序将区间中的元素复制到另一个区间中
random_shuffle( )	随机重新排列区间中的元素
shuffle( )	随机重新排列区间中的元素，使用的函数对象满足 C++11 对统一随机生成器的要求
is_partitioned( )	如果区间根据指定的谓词进行了分区，则返回 true
partition( )	将满足谓词函数对象的所有元素都放在不满足谓词函数对象的元素之前
stable_partition( )	将满足谓词函数对象的所有元素放置在不满足谓词函数对象的元素之前，每组中元素的相对顺序保持不变
partition_copy( )	将满足谓词函数对象的所有元素都复制到一个输出区间中，并将其他元素都复制到另一个输出区间中，这是 C++11 新增的
partition_point( )	对于根据指定谓词进行了分区的区间，返回一个迭代器，该迭代器指向第一个不满足该谓词的元素

下面详细地介绍这些修改型序列操作。对于每个函数，首先列出其原型，然后做简要的描述。正如前面介绍的，迭代器对指出了区间，而选择的模板参数名指出了迭代器的类型。通常，[first, last]区间指的是从 first 到 last（不包括 last）。作为参数传递的函数是函数对象，这些函数对象可以是指针，也可以是定义了( ) 操作的对象。正如第 16 章介绍的，谓词是接受一个参数的布尔函数，二元谓词是接受两个参数的布尔函数（函数可以不是 bool 类型，只要它对于 false 返回 0，对于 true 返回非 0 值）。另外，正如第 16 章介绍的，一元函数对象接受一个参数，而二元函数对象接受两个参数。

1．copy( )

copy( ) 函数将[first, last) 区间中的元素复制到区间[result, result + (last – first)) 中，并返回 result + (last – first)，即指向被复制到的最后一个位置后面的迭代器。该函数要求 result 不位于[first, last) 区间中，也就是说，目标不能与源重叠。

2．copy_n( )（C++11）

函数 copy_n( ) 从位置 first 开始复制 n 个元素到区间[result, result + n] 中，并返回 result + n，即指向被复制到的最后一个位置后面的迭代器。该函数不要求目标和源不重叠。

3．copy_if( )（C++11）

函数 copy_if( ) 将[first, last) 区间中满足谓词 pred 的元素复制到区间[result, result + (last – first)) 中，并返回 result + (last – first)，即指向被复制到的最后一个位置后面的迭代器。该函数要求 result 不位于[first, last) 区间中，也就是说，目标不能与源重叠。

4．copy_backward( )

函数 copy_backward( ) 将[first, last) 区间中的元素复制到区间[result - (last - first), result) 中。复制从 last - 1 开始，该元素被复制到位置 result - 1，然后由后向前处理，直到 first。该函数返回 result - (last - first)，即指向被复制到的最后一个位置后面的迭代器。该函数要求 result 不位于[first, last) 区间中。然而，由于复制是从后向前进行的，因此目标和源可能重叠。

5．move( )（C++11）

函数 move( ) 使用 std::move( ) 将[first, last) 区间中的元素移到区间[result, result + (last – first)) 中，并返回 result + (last – first)，即指向被复制到的最后一个位置后面的迭代器。该函数要求 result 不位于[first, last) 区间中，也就是说，目标不能与源重叠。

6．move_backward( )（C++11）

函数 move_backward( ) std::move( ) 将[first, last) 区间中的元素移到区间[result - (last - first), result) 中。复制从 last - 1 开始，该元素被复制到位置 result - 1，然后由后向前处理，直到 first。该函数返回 result - (last - first)，即指向被复制到的最后一个位置后面的迭代器。该函数要求 result 不位于[first, last) 区间中。然而，由于复制是从后向前进行的，因此目标和源可能重叠。

7．swap( )

swap( ) 函数对引用指定的两个位置中存储的值进行交换（C++11 将这个函数移到了头文件 utility 中）。

8．swap_ranges( )

swap_ranges( ) 函数将[first1, last1]区间中的值与从 first2 开始的区间中对应的值交换。这两个区间不能重叠。

9．iter_swap( )

iter_swap( ) 函数将迭代器指定的两个位置中存储的值进行交换。

10．transform( )

第一个版本的 transform( ) 将一元函数对象 op 应用到[first, last) 区间中每个元素，并将返回值赋给从 result 开始的区间中对应的元素。因此，*result 被设置为 op(*first)，依此类推。该函数返回 result + (last - first)，即目标区间的超尾值。

第二个版本的 transform( ) 将二元函数对象 op 应用到[first1, last1) 区间和[first2, last2) 区间中的每个元素，并将返回值赋给从 result 开始的区间中对应的元素。因此，*result 被设置成 op(*first1, *first2)，依此类推。该函数返回 result + (last – first)，即目标区间的超尾值。

11．replace( )

replace( ) 函数将[first, last]中的所有 old_value 替换为 new_value。

12．replace_if( )

replace_if( ) 函数使用 new_value 值替换[first, last]区间中 pred（old）为 true 的每个 old 值。

13．replace_copy( )

replace_copy( ) 函数将[first, last]区间中的元素复制到从 result 开始的区间中，但它使用 new_value 代替所有的 old_value。该函数返回 result + (last - first)，即目标区间的超尾值。

14．replace_copy_if( )

replace_copy_if( ) 函数将[first, last]区间中的元素复制到从 result 开始的区间中，但它使用 new_value 代替 pred(old) 为 true 的所有 old 值。该函数返回 result + (last - first)，即目标区间的超尾值。

15．fill( )

fill( ) 函数将[first, last]区间中的每个元素都设置为 value。

16．fill_n( )

fill_n( ) 函数将从 first 位置开始的前 n 个元素都设置为 value。

17．generate( )

generate( ) 函数将[first, last) 区间中的每个元素都设置为 gen( )，其中 gen 是一个生成器函数对象，即不接受任何参数。例如，gen 可以是一个指向 rand( ) 的指针。

18．generate_n( )

generate_n( ) 函数将从 first 开始的区间中前 n 个元素都设置为 gen( )，其中，gen 是一个生成器函数对象，即不接受任何参数。例如，gen 可以是一个指向 rand( ) 的指针。

19．remove( )

remove( ) 函数删除[first, last) 区间中所有值为 value 的元素，并返回得到的区间的超尾迭代器。该函数是稳定的，这意味着未删除的元素的顺序将保持不变。

注意：由于所有的 remove( ) 和 unique( ) 函数都不是成员函数，同时这些函数并非只能用于 STL 容器，因此它们不能重新设置容器的长度。相反，它们返回一个指示新超尾位置的迭代器。通常，被删除的元素只是被移到容器尾部。然而，对于 STL 容器，可以使用返回的迭代器和 erase( ) 方法来重新设置 end( )。

20．remove_if( )

remove_if( ) 函数将 pred(val) 为 true 的所有 val 值从[first, last) 区间删除，并返回得到的区间的超尾迭代器。该函数是稳定的，这意味着未删除的元素的顺序将保持不变。

21．remove_copy( )

remove_copy( ) 函数将[first, last) 区间中的值复制到从 result 开始的区间中，复制时将忽略 value。该函数返回得到的区间的超尾迭代器。该函数是稳定的，这意味着没有被删除的元素的顺序将保持不变。

22．remove_copy_if( )

remove_copy_if( ) 函数将[first, last) 区间中的值复制到从 result 开始的区间，但复制时忽略 pred(val) 为 true 的 val。该函数返回得到的区间的超尾迭代器。该函数是稳定的，这意味着没有删除的元素的顺序将保持不变。

23．unique( )

unique( ) 函数将[first, last) 区间中由两个或更多相同元素构成的序列压缩为一个元素，并返回新区间的超尾迭代器。第一个版本使用值类型的= =运算符对元素进行比较；第二个版本使用二元谓词函数对象 pred 来比较元素。也就是说，如果 pred(*it1, *it2) 为 true，则 it1 和 it2 指向的元素是匹配的。

24．unique_copy( )

unique_copy( ) 函数将[first, last) 区间中的元素复制到从 result 开始的区间中，并将由两个或更多个相同元素组成的序列压缩为一个元素。该函数返回新区间的超尾迭代器。第一个版本使用值类型的= =运算符，对元素进行比较；第二个版本使用二元谓词函数对象 pred 来比较元素。也就是说，如果 pred(*it1, *it2) 为 true，则 it1 和 it2 指向的元素是匹配的。

25．reverse( )

reverse( ) 函数通过调用 swap(first, last - 1) 等来反转[first, last]区间中的元素。

26．reverse_copy

reverse_copy( ) 函数按相反的顺序将[first, last) 区间中的元素复制到从 result 开始的区间中。这两个区间不能重叠。

27．rotate( )

rotate( ) 函数将[first, last) 区间中的元素左旋。middle 处的元素被移到 first 处，middle + 1 处的元素被移到 first + 1 处，依此类推。middle 前的元素绕回到容器尾部，以便 first 处的元素可以紧接着 last - 1 处的元素。

28．rotate_copy( )

rotate_copy( ) 函数使用为 rotate( ) 函数描述的旋转序列，将[first, last) 区间中的元素复制到从 result 开始的区间中。

29．random_shuffle( )

这个版本的 random_shuffle( ) 函数将[first, last) 区间中的元素打乱。分布是一致的，即原始顺序的每种可能排列方式出现的概率相同。

30．random_shuffle( )

这个版本的 random_shuffle( ) 函数将[first, last) 区间中的元素打乱。函数对象 random 确定分布。假设有 n 个元素，表达式 random(n) 将返回[0, n) 区间中的一个值。在 C++98 中，参数 random 是一个左值引用，而在 C++11 中是一个右值引用。

31．shuffle( )

函数 shuffle( ) 将[first, last) 区间中的元素打乱。函数对象 rgen 确定分布，它应满足 C++11 指定的有关均匀随机数生成器的要求。假设有 n 个元素，表达式 rgen(n) 将返回[0, n]区间中的一个值。

32．is_partitioned( )（C++11）

如果区间为空或根据 pred 进行了分区（即满足谓词 pred 的元素都在不满足该谓词的元素前面），函数 is__partitioned( ) 将返回 true，否则返回 false。

33．partition( )

函数 partition( ) 将其值 val 使得 pred(val) 为 true 的元素都放在不满足该测试条件的所有元素之前。这个函数返回一个迭代器，指向最后一个使得谓词对象函数为 true 的值的后面。

34．stable_partition( )

函数 stable_partition( ) 将其值 val 使得 pred(val) 为 true 的元素都放在不满足该测试条件的所有元素之前；在这两组中，元素的相对顺序保持不变。这个函数返回一个迭代器，指向最后一个使得谓词对象函数为 true 的值的后面。

35．partition_copy( )（C++11）

函数 partition_copy( ) 将所有这样的元素都复制到从 out_true 开始的区间中，即其值 val 使得 pred(val) 为 true；并将其他的元素都复制到从 out_false 开始的区间中。它返回一个 pair 对象，该对象包含两个迭代器，分别指向从 out_true 和 out_false 开始的区间的末尾。

36．partition_point( )（C++11）

函数 partition_point( ) 要求区间根据 pred 进行了分区。它返回一个迭代器，指向最后一个让谓词对象函数为 true 的值所在的位置。

G.5.3 排序和相关操作

表 G.15 对排序和相关操作进行了总结。其中没有列出参数，而重载函数也只列出了一次。每一个函数都有一个使用<对元素进行排序的版本和一个使用比较函数对象对元素进行排序的版本。表后做了更详细的说明，其中包括原型。因此，可以浏览该表，以了解函数的功能，如果对某个函数非常感兴趣，则可以了解其细节。

表 G.15 排序和相关操作

函 数	描 述
sort( )	对区间进行排序
stable_sort( )	对区间进行排序，并保留相同元素的相对顺序
partial_sort( )	对区间进行部分排序，提供完整排序的前 n 个元素
partial_sort_copy( )	将经过部分排序的区间复制到另一个区间中
is_sorted( )	如果对区间进行了排序，则返回 true，这是 C++11 新增的
is_sorted_until( )	返回一个迭代器，指向经过排序的区间末尾，这是 C++11 新增的
nth_element( )	对于给定指向区间的迭代器，找到区间被排序时，相应位置将存储哪个元素，并将该元素放到这里
lower_bound( )	对于给定的一个值，在一个排序后的区间中找到第一个这样的位置，使得将这个值插入到这个位置前面时，不会破坏顺序
upper_bound( )	对于给定的一个值，在一个排序后的区间中找到最后一个这样的位置，使得将这个值插入到这个位置前面时，不会破坏顺序
equal_range( )	对于给定的一个值，在一个排序后的区间中找到一个最大的区间，使得将这个值插入其中的任何位置，都不会破坏顺序
binary_search( )	如果排序后的区间中包含了与给定的值相同的值，则返回 true，否则返回 false
merge( )	将两个排序后的区间合并为第三个区间
inplace_merge( )	就地合并两个相邻的、排序后的区间
includes( )	如果对于一个集合中的每个元素都可以在另外一个集合中找到，则返回 true
set_union( )	构造两个集合的并集，其中包含在任何一个集合中出现过的元素
set_intersection( )	构造两个集合的交集，其中包含在两个集合中都出现过的元素
set_difference( )	构造两个集合的差集，即包含第一个集合中且没有出现在第二个集合中的所有元素
set_symmetric_difference( )	构造由只出现在其中一个集合中的元素组成的集合
make_heap( )	将区间转换成堆
push_heap( )	将一个元素添加到堆中
pop_heap( )	删除堆中最大的元素
sort_heap( )	对堆进行排序
is_heap( )	如果区间是堆，则返回 true，这是 C++11 新增的
is_heap_until( )	返回一个迭代器，指向属于堆的区间的末尾，这是 C++11 新增的
min( )	返回两个值中较小的值，如果参数为 initializer_list，则返回最小的元素（这是 C++11 新增的）
max( )	返回两个值中较大的值，如果参数为 initializer_list，则返回最大的元素（这是 C++11 新增的）
minmax( )	返回一个 pair 对象，其中包含按递增顺序排列的两个参数；如果参数为 initializer_list，则返回 pair 对象包含最小和最大的元素。这是 C++11 新增的
min_element( )	在区间找到最小值第一次出现的位置
max_element( )	在区间找到最大值第一次出现的位置
minmax_element( )	返回一个 pair 对象，其中包含两个迭代器，它们分别指向区间中最小值第一次出现的位置和区间中最大值最后一次出现的位置。这是 C++11 新增的
lexicographic_compare( )	按字母顺序比较两个序列，如果第一个序列小于第二个序列，则返回 true，否则返回 false
next-permutation( )	生成序列的下一种排列方式
previous_permutation( )	生成序列的前一种排列方式

本节中的函数使用为元素定义的<运算符或模板类型 Compare 指定的比较对象来确定两个元素的顺序。如果 comp 是一个 Compare 类型的对象，则 comp(a, b) 就是 a<b 的统称，如果在排序机制中，a 在 b 之前，则返回 true。如果 a<b 返回 fasle，同时 b<a 也返回 false，则说明 a 和 b 相等。比较对象必须至少提供严格弱排序功能（strict weak ordering）。这意味着：

• 表达式 comp(a, a) 一定为 false，这是“值不能比其本身小”的统称（这是严格部分）。
• 如果 comp(a, b) 为 true，且 comp(b, c) 也为 true，则 comp(a, c) 为 true（也就是说，比较是一种可传递的关系）。
• 如果 a 与 b 等价，且 b 与 c 也等价，则 a 与 c 等价（也就是说，等价也是一种可传递的关系）。

如果想将<运算符用于整数，则等价就意味着相等，但这一结论不能推而广之。例如，可以用几个描述邮件地址的成员来定义一个结构，同时定义一个根据邮政编码对结构进行排序的 comp 对象。则邮政编码相同的地址是等价的，但它们并不相等。

下面更详细地介绍排序及相关操作。对于每个函数，首先列出其原型，然后做简要的说明。我们将这一节分成几个小节。正如前面介绍的，迭代器对指出了区间，而选择的模板参数名指出了迭代器的类型。通常，[first, last) 区间指的是从 first 到 last（不包括 last）。作为参数传递的函数是函数对象，这些函数对象可以是指针，也可以是定义了( ) 操作的对象。正如第 16 章介绍的，谓词是接受一个参数的布尔函数，二元谓词是接受 2 个参数的布尔函数（函数可以不是 bool 类型，只要它对于 false 返回 0，对于 true 返回非 0 值）。另外，正如第 16 章介绍的，一元函数对象接受一个参数，而二元函数对象接受两个参数。

1．排序

首先来看看排序算法。

（1）sort( )

sort( ) 函数将[first, last) 区间按升序进行排序，排序时使用值类型的<运算符进行比较。第一个版本使用<来确定顺序，而第二个版本使用比较对象 comp。

（2）stable_sort( )

stable_sort( ) 函数对[first, last) 区间进行排序，并保持等价元素的相对顺序不变。第一个版本使用<来确定顺序，而第二个版本使用比较对象 comp。

（3）partial_sort( )

partial_sort( ) 函数对[first, last) 区间进行部分排序。将排序后的区间的前 middle - first 个元素置于[first, middle]区间内，其余元素没有排序。第一个版本使用<来确定顺序，而第二个版本使用比较对象 comp。

（4）partial_sort_copy( )

partial_sort_copy( ) 函数将排序后的区间[first, last]中的前 n 个元素复制到区间[result_first, result_first + n]中。n 的值是 last - first 和 result_last - result_first 中较小的一个。该函数返回 result - first + n。第一个版本使用<来确定顺序，第二个版本使用比较对象 comp。

（5）is_sorted（C++11）

如果区间[first, last]是经过排序的，函数 is_sorted( ) 将返回 true，否则返回 false。第一个版本使用<来确定顺序，而第二个版本使用比较对象 comp。

（6）is_sorted_until（C++11）

如果区间[first, last]包含的元素少于两个，函数 is_sorted_until 将返回 last；否则将返回迭代器 it，确保区间[first, it]是经过排序的。第一个版本使用<来确定顺序，而第二个版本使用比较对象 comp。

（7）nth_element( )

nth_element( ) 函数找到将[first, last) 区间排序后的第 n 个元素，并将该元素置于第 n 个位置。第一个版本使用<来确定顺序，而第二个版本使用比较对象 comp。

2．二分法搜索

二分法搜索组中的算法假设区间是经过排序的。这些算法只要求正向迭代器，但使用随机迭代器时，效率最高。

（1）lower_bound( )

lower_bound( ) 函数在排序后的区间[first, last) 中找到第一个这样的位置，即将 value 插入到它前面时不会破坏顺序。它返回一个指向这个位置的迭代器。第一个版本使用<来确定顺序，而第二个版本使用比较对象 comp。

（2）upper_bound( )

upper_bound( ) 函数在排序后的区间[first, last) 中找到最后一个这样的位置，即将 value 插入到它前面时不会破坏顺序。它返回一个指向这个位置的迭代器。第一个版本使用<来确定顺序，而第二个版本使用比较对象 comp。

（3）equal_range( )

equal_range( ) 函数在排序后的区间[first, last) 区间中找到这样一个最大的子区间[it1, it2)，即将 value 插入到该区间的任何位置都不会破坏顺序。该函数返回一个由 it1 和 it2 组成的 pair。第一个版本使用<来确定顺序，第二个版本使用比较对象 comp。

（4）binary_search( )

如果在排序后的区间[first, last]中找到与 value 等价的值，则 binary_search( ) 函数返回 true，否则返回 false。第一个版本使用<来确定顺序，而第二个版本使用比较对象 comp。

注意：前面说过，使用<进行排序时，如果 a<b 和 b<a 都为 false，则 a 和 b 等价。对于常规数字来说，等价意味着相等；但对于只根据一个成员进行排序的结构来说，情况并非如此。因此，在确保顺序不被破坏的情况下，可插入新值的位置可能不止一个。同样，如果使用比较对象 comp 进行排序，等价意味着 comp(a, b) 和 comp（b，a）都为 false（这是“如果 a 不小于 b，b 也不小于 a，则 a 与 b 等价”的统称）。

3．合并

合并函数假设区间是经过排序的。

（1）merge( )

merge( ) 函数将排序后的区间[first1, last1] 中的元素与排序后的区间[first2, last2] 中的元素进行合并，并将结果放到从 result 开始的区间中。目标区间不能与被合并的任何一个区间重叠。在两个区间中发现了等价元素时，第一个区间中的元素将位于第二个区间中的元素前面。返回值是合并的区间的超尾迭代器。第一个版本使用<来确定顺序，第二个版本使用比较对象 comp。

（2）inplace_merge( )

inplace_merge( ) 函数将两个连续的、排序后的区间—[first, middle] 和[middle, last] —合并为一个经过排序的序列，并将其存储在[first, last] 区间中。第一个区间中的元素将位于第二个区间中的等价元素之前。第一个版本使用<来确定顺序，而第二个版本使用比较对象 comp。

4．使用集合

集合操作可用于所有排序后的序列，包括集合（set）和多集合（multiset）。对于存储一个值的多个实例的容器（如 multiset）来说，定义是广义的。对于两个多集合的并集，将包含较大数目的元素实例，而交集将包含较小数目的元素实例。例如，假设多集合 A 包含了字符串“apple”7 次，多集合 B 包含该字符串 4 次。则 A 和 B 的并集将包含 7 个“apple”实例，它们的交集将包含 4 个实例。

（1）includes( )

如果[first2, last2) 区间中的每一个元素在[first1, last1) 区间中都可以找到，则 includes( ) 函数返回 true，否则返回 false。第一个版本使用<来确定顺序，而第二个版本使用比较对象 comp。

（2）set_union( )

set_union( ) 函数构造一个由[first1, last1]区间和[first2, last2] 区间组合而成的集合，并将结果复制到 result 指定的位置。得到的区间不能与原来的任何一个区间重叠。该函数返回构造的区间的超尾迭代器。并集包含在任何一个集合（或两个集合）中出现的所有元素。第一个版本使用<来确定顺序，而第二个版本使用比较对象 comp。

（3）set_intersection( )

set_intersection( ) 函数构造[first1, last1) 区间和[first2, last2) 区间的交集，并将结果复制到 result 指定的位置。得到的区间不能与原来的任何一个区间重叠。该函数返回构造的区间的超尾迭代器。交集包含两个集合中共有的元素。第一个版本使用<来确定顺序，而第二个版本使用比较对象 comp。

（4）set_difference( )

set_difference( ) 函数构造[first1, last1) 区间与[first2, last2) 区间的差集，并将结果复制到 result 指定的位置。得到的区间不能与原来的任何一个区间重叠。该函数返回构造的区间的超尾迭代器。差集包含出现在第一个集合中，但不出现在第二个集合中的所有元素。第一个版本使用<来确定顺序，而第二个版本使用比较对象 comp。

（5）set_symmetric_difference( )

set_symmetric_difference( ) 函数构造[first1, last1) 区间和[first2, last2) 区间的对称（symmetric）差集，并将结果复制到 result 指定的位置。得到的区间不能与原来的任何一个区间重叠。该函数返回构造的区间的超尾迭代器。对称差集包含出现在第一个集合中，但不出现在第二个集合中，或者出现在第二个集合中，但不出现在第一个集合中的所有元素。第一个版本使用<来确定顺序，第二个版本使用比较对象 comp。

5．使用堆

堆（heap）是一种常用的数据形式，具有这样特征：第一个元素是最大的。每当第一个元素被删除或添加了新元素时，堆都可能需要重新排列，以确保这一特征。设计堆是为了提高这两种操作的效率。

（1）make_heap( )

make_heap( ) 函数将[first, last) 区间构造成一个堆。第一个版本使用<来确定顺序，而第二个版本使用 comp 比较对象。

（2）push_heap( )

push_heap( ) 函数假设[first, last – 1) 区间是一个有效的堆，并将 last - 1 位置（即被假设为有效堆的区间后面的一个位置）上的值添加到堆中，使[first, last) 区间成为一个有效堆。第一个版本使用<来确定顺序，而第二个版本使用 comp 比较对象。

（3）pop_heap( )

pop_heap( ) 函数假设[first, last) 区间是一个有效堆，并将位置 last - 1 处的值与 first 处的值进行交换，使[first, last – 1]区间成为一个有效堆。第一个版本使用<来确定顺序，而第二个版本使用 comp 比较对象。

（4）sort_heap( )

sort_heap( ) 函数假设[first, last) 区间是一个有效堆，并对其进行排序。第一个版本使用<来确定顺序，而第二个版本使用 comp 比较对象。

（5）is_heap( )（C++11）

如果区间[first, last]是一个有效的堆，函数 is_heap( ) 将返回 true，否则返回 false。第一个版本使用<来确定顺序，而第二个版本使用 comp 比较对象。

（6）is_heap_until( )（C++11）

如果区间[first, last) 包含的元素少于两个，则返回 last；否则返回迭代器 it，而区间[first, it) 是一个有效的堆。第一个版本使用<来确定顺序，而第二个版本使用 comp 比较对象。

6．查找最小和最大值

最小函数和最大函数返回两个值或值序列中的最小值和最大值。

（1）min( )

这些版本的 min( ) 函数返回两个值中较小一个；如果这两个值相等，则返回第一个值。第一个版本使用<来确定顺序，而第二个版本使用 comp 比较对象。

这些版本的 min( ) 函数是 C++11 新增的，它返回初始化列表 t 中最小的值。如果有多个相等的值且最小，则返回第一个。第一个版本使用<来确定顺序，而第二个版本使用 comp 比较对象。

（2）max( )

这些版本的 max( ) 函数返回这两个值中较大的一个；如果这两个值相等，则返回第一个值。第一个版本使用<来确定顺序，而第二个版本使用 comp 比较对象。

这些版本的 max( ) 函数是 C++11 新增的，它返回初始化列表 t 中最大的值。如果有多个相等的值且最大，则返回第一个。第一个版本使用<来确定顺序，而第二个版本使用 comp 比较对象。

（3）minmax( )（C++11）

如果 b 小于 a，这些版本的 minmax( ) 函数返回 pair(b, a)，否则返回 pair(a, b)。第一个版本使用<来确定顺序，而第二个版本使用 comp 比较对象。

这些版本的 minmax( ) 函数返回初始化列表 t 中最小元素和最大元素的拷贝。如果有多个最小的元素，则返回其中的第一个；如果有多个最大的元素，则返回其中的最后一个。第一个版本使用<来确定顺序，而第二个版本使用 comp 比较对象。

（4）min_element( )

min_element( ) 函数返回这样一个迭代器，该迭代器指向[first, last) 区间中第一个最小的元素。第一个版本使用<来确定顺序，而第二个版本使用 comp 比较对象。

（5）max_element( )

max_element( ) 函数返回这样一个迭代器，该迭代器指向[first, last] 区间中第一个最大的元素。第一个版本使用<来确定顺序，而第二个版本使用 comp 比较对象。

（6）minmax_element( )（C++11）

函数 minmax_element( ) 返回一个 pair 对象，其中包含两个迭代器，分别指向区间[first, last) 中最小和最大的元素。第一个版本使用<来确定顺序，而第二个版本使用 comp 比较对象。

（7）lexicographical_compare( )

如果[first1, last1]区间中的元素序列按字典顺序小于[first2, last2]区间中的元素序列，则 lexicographical_compare( ) 函数返回 true，否则返回 false。字典比较将两个序列的第一个元素进行比较，即对*first1 和*first2 进行比较。如果*first1 小于*first2，则该函数返回 true；如果*first2 小于*first1，则返回 fasle；如果相等，则继续比较两个序列中的下一个元素。直到对应的元素不相等或到达了某个序列的结尾，比较才停止。如果在到达某个序列的结尾时，这两个序列仍然是等价的，则较短的序列较小。如果两个序列等价，且长度相等，则任何一个序列都不小于另一个序列，因此函数将返回 false。第一个版本使用<来比较元素，而第二个版本使用 comp 比较对象。字典比较是按字母顺序比较的统称。

7．排列组合

序列的排列组合是对元素重新排序。例如，由 3 个元素组成的序列有 6 种可能的排列方式，因为对于第一个位置，有 3 种选择；给第一个位置选定元素后，第二个位置有两种选择；第三个位置有 1 种选择。例如，数字 1、2 和 3 的 6 种排列如下：

通常，由 n 个元素组成的序列有 n*(n−1)*...*1 或 n!种排列。

排列函数假设按字典顺序排列各种可能的排列组合，就像前一个例子中的 6 种排列那样。这意味着，通常，在每个排列之前和之后都有一个特定的排列。例如，213 在 231 之前，312 在 231 之后。然而，第一个排列（如示例中的 123）前面没有其他排列，而最后一个排列（321）后面没有其他排列。

（1）next_permutation( )

next_permutation( ) 函数将[first, last]区间中的序列转换为字典顺序的下一个排列。如果下一个排列存在，则该函数返回 true；如果下一个排列不存在（即区间中包含的是字典顺序的最后一个排列），则该函数返回 false，并将区间转换为字典顺序的第一个排列。第一个版本使用<来确定顺序，而第二个版本则使用 comp 比较对象。

（2）prev_permutation( )

previous_permutation( ) 函数将[first, last] 区间中的序列转换为字典顺序的前一个序列。如果前一个排列存在，则该函数返回 true；如果前一个序列不存在（即区间包含的是字典顺序的第一个排列），则该函数返回 false，并将该区间转换为字典顺序的最后一个排列。第一个版本使用<来确定顺序，而第二个版本则使用 comp 比较对象。

G.5.4 数值运算

表 G.16 对数值运算进行了总结，这些操作是由头文件 numeric 描述的。其中没有列出参数，而重载函数也只列出了一次。每一个函数都有一个使用<对元素进行排序的版本和一个使用比较函数对象对元素进行排序的版本。表后做了更详细的说明，其中包括原型。因此，可以浏览该表，以了解函数的功能；如果对某个函数非常感兴趣，则可以了解其细节。

表 G.16 数值运算

函 数	描 述
accumulate( )	计算区间中的值的总和
inner_product( )	计算 2 个区间的内部乘积
partial_sum( )	将使用一个区间计算得到的小计复制到另一个区间中
adjacent_difference( )	将使用一个区间的元素计算得到的相邻差集复制到另一个区间中
iota( )	将使用运算符++生成的一系列相邻的值赋给一个区间中的元素，这是 C++11 新增的

1．accumulate( )

accumulate( ) 函数将 acc 的值初始化为 init，然后按顺序对[first, last]区间中的每一个迭代器 i 执行 acc = acc + * i（第一个版本）或 acc = binary_op(acc, *i)（第二个版本）。然后返回 acc 的值。

2．inner_product( )

inner_product( ) 函数将 acc 的值初始化为 init，然后按顺序对[first1, last1]区间中的每一个迭代器 i 和[first2, first2 + (last1−first1)]区间中对应的迭代器 j 执行 acc = * i * * j（第一个版本）或 acc = binary_op(*i, *j)（第二个版本）。也就是说，该函数对每个序列的第一个元素进行计算，得到一个值，然后对每个序列中的第二个元素进行计算，得到另一个值，依此类推，直到到达第一个序列的结尾（因此，第二个序列至少应同第一个序列一样长）。然后，函数返回 acc 的值。

3．partial_sum( )

partial_sum( ) 函数将*first 赋给*result，将*first + *(first + 1) 赋给*(result + 1)（第一个版本），或者将 binary_op(*first, *(first + 1)) 赋给*(result + 1)（第二个版本），依此类推。也就是说，从 result 开始的序列的第 n 个元素将包含从 first 开始的序列的前 n 个元素的总和（或 binary_op 的等价物）。该函数返回结果的超尾迭代器。该算法允许 result 等于 first，也就是说，如果需要，该算法允许使用结果覆盖原来的序列。

4．adjacent_difference( )

adjacent_difference( ) 函数将*first 赋给 result(*result = *first)。目标区间中随后的位置将被赋值为源区间中相邻位置的差集（或 binary_op 等价物）。也就是说，目标区间的下一个位置(result +1) 将被赋值为*(first + 1) - * first（第一个版本）或 binary_op(*(first + 1), * first)（第二个版本），依此类推。该函数返回结果的超尾迭代器。该算法允许 result 等于 first，也就是说，如果需要，该算法允许结果覆盖原来的序列。

5．iota( )（C++11）

函数 iota( ) 将 value 赋给*first，再将 value 递增（就像执行运算++value），并将结果赋给下一个元素，依次类推，直到最后一个元素。