G.5.3 排序和相关操作（1）
表G.15对排序和相关操作进行了总结。其中没有列出参数，而重载函数也只列出了一次。每一个函数都有一个使用<对元素进行排序的版本和一个使用比较函数对象对元素进行排序的版本。表后做了更详细的说明，其中包括原型。因此，可以浏览该表，以了解函数的功能，如果对某个函数非常感兴趣，则可以了解其细节。
表G.15排序和相关操作
|
函 数< xml:namespace prefix = o ns = "urn:schemas-microsoft-com:office:office" /> |
描 述 |
|
sort( ) |
对区间进行排序 |
|
stable_sort( ) |
对区间进行排序，并保留相同元素的相对顺序 |
|
partial_sort( ) |
对区间进行部分排序，提供完整排序的前n个元素 |
|
partial_sort_copy( ) |
将经过部分排序的区间复制到另一个区间中 |
|
is_sorted( ) |
如果对区间进行了排序，则返回true，
这是C++(www.cppentry.com)11新增的 |
|
is_sorted_until( ) |
返回一个迭代器，指向经过排序的区间末
尾，这是C++(www.cppentry.com)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++(www.cppentry.com)11新增的 |
|
is_heap_until( ) |
返回一个迭代器，指向属于堆的区间的末尾，
这是C++(www.cppentry.com)11新增的 |
|
min( ) |
返回两个值中较小的值，如果参数为
initializer_list，则返回最小的元素
（这是C++(www.cppentry.com)11新增的） |
|
max( ) |
返回两个值中较大的值，如果参数为
initializer_list，则返回最大的元素
（这是C++(www.cppentry.com)11新增的） |
|
minmax( ) |
返回一个pair对象，其中包含按递增顺
序排列的两个参数；如果参数为initializer_list，
则返回pair对象包含最小和最大的元素。
这是C++(www.cppentry.com)11新增的 |
|
min_element( ) |
在区间找到最小值第一次出现的位置 |
|
max_element( ) |
在区间找到最大值第一次出现的位置 |
|
minmax_element( ) |
返回一个pair对象，其中包含两个迭代器，
它们分别指向区间中最小值第一次出现的位
置和区间中最大值最后一次出现的位置。
这是C++(www.cppentry.com)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章介绍的，一元函数对象接受一个参数，而二元函数对象接受两个参数。