喜欢文学作品的朋友请记住本站网址：HIGrid.NET
当前位置：嗨网首页>书籍在线阅读

12-排序和相关操作

  
选择背景色： 黄橙 洋红 淡粉 水蓝 草绿 白色 选择字体： 宋体 黑体 微软雅黑 楷体 选择字体大小： 小 中 大 特 恢复默认
Previous 上一篇本节目录 Next 下一篇

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()

template<class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void sort(RandomAccessIterator first, RandomAccessIterator last,
          Compare comp);

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

（2）stable_sort()

template<class RandomAccessIterator>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last,
                 Compare comp);

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

（3）partial_sort()

template<class RandomAccessIterator>
void partial_sort(RandomAccessIterator first, RandomAccessIterator middle,
                  RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void partial_sort(RandomAccessIterator first, RandomAccessIterator middle,
RandomAccessIterator last, Compare comp);

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

（4）partial_sort_copy()

template<class InputIterator, class RandomAccessIterator>
RandomAccessIterator partial_sort_copy(InputIterator first,
                        InputIterator last,
                        RandomAccessIterator result_first,
                        RandomAccessIterator result_last);
template<class InputIterator, class RandomAccessIterator, class Compare>
RandomAccessIterator
partial_sort_copy(InputIterator first, InputIterator last,
                  RandomAccessIterator result_first,
                  RandomAccessIterator result_last,
                  Compare comp);

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）

template<class ForwardIterator>
bool is_sorted(ForwardIterator first, ForwardIterator last);
template<class ForwardIterator, class Compare>
bool is_sorted(ForwardIterator first, ForwardIterator last
               Compare comp);

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

（6）is_sorted_until（C++11）

template<class ForwardIterator>
ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last);
template<class ForwardIterator, class Compare>
ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last
               Compare comp);

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

（7）nth_element()

template<class RandomAccessIterator>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
                 RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
RandomAccessIterator last, Compare comp);

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

2．二分法搜索

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

（1）lower_bound()

template<class ForwardIterator, class T>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,
                            const T& value);
template<class ForwardIterator, class T, class Compare>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,
                            const T& value, Compare comp);

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

（2）upper_bound()

template<class ForwardIterator, class T>
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last,
                            const T& value);
template<class ForwardIterator, class T, class Compare>
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last,
const T& value, Compare comp);

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

（3）equal_range()

template<class ForwardIterator, class T>
pair<ForwardIterator, ForwardIterator> equal_range(
    ForwardIterator first, ForwardIterator last, const T& value);
template<class ForwardIterator, class T, class Compare>
pair<ForwardIterator, ForwardIterator> equal_range(
    ForwardIterator first, ForwardIterator last, const T& value,
    Compare comp);

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

（4）binary_search()

template<class ForwardIterator, class T>
bool binary_search(ForwardIterator first, ForwardIterator last,
                   const T& value);
template<class ForwardIterator, class T, class Compare>
bool binary_search(ForwardIterator first, ForwardIterator last,
                   const T& value, Compare comp);

如果在排序后的区间[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()

template<class InputIterator1, class InputIterator2,
         class OutputIterator>
OutputIterator merge(InputIterator1 first1, InputIterator1 last1,
                     InputIterator2 first2, InputIterator2 last2,
                     OutputIterator result);
template<class InputIterator1, class InputIterator2,
         class OutputIterator,
class Compare>
OutputIterator merge(InputIterator1 first1, InputIterator1 last1,
                     InputIterator2 first2, InputIterator2 last2,
                     OutputIterator result, Compare comp);

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

（2）inplace_merge()

template<class BidirectionalIterator>
void inplace_merge(BidirectionalIterator first,
     BidirectionalIterator middle, BidirectionalIterator last);
template<class BidirectionalIterator, class Compare>
void inplace_merge(BidirectionalIterator first,
     BidirectionalIterator middle, BidirectionalIterator last,
     Compare comp);

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()

template<class InputIterator1, class InputIterator2>
bool includes(InputIterator1 first1, InputIterator1 last1,
              InputIterator2 first2, InputIterator2 last2);
template<class InputIterator1, class InputIterator2, class Compare>
bool includes(InputIterator1 first1, InputIterator1 last1,
              InputIterator2 first2, InputIterator2 last2, Compare comp);

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

（2）set_union()

template<class InputIterator1, class InputIterator2,
         class OutputIterator>
OutputIterator set_union(InputIterator1 first1, InputIterator1 last1,
                         InputIterator2 first2, InputIterator2 last2,
                         OutputIterator result);
template<class InputIterator1, class InputIterator2,
         class OutputIterator, class Compare>
OutputIterator set_union(InputIterator1 first1, InputIterator1 last1,
                         InputIterator2 first2, InputIterator2 last2,
                         OutputIterator result, Compare comp);

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

（3）set_intersection()

template<class InputIterator1, class InputIterator2,
         class OutputIterator>
OutputIterator set_intersection(InputIterator1 first1,
      InputIterator1 last1,InputIterator2 first2,
      InputIterator2 last2, OutputIterator result);
template<class InputIterator1, class InputIterator2,
         class OutputIterator, class Compare>
OutputIterator set_intersection(InputIterator1 first1,
      InputIterator1 last1, InputIterator2 first2,
      InputIterator2 last2, OutputIterator result,
      Compare comp);

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

（4）set_difference()

template<class InputIterator1, class InputIterator2,
         class OutputIterator>
OutputIterator set_difference(InputIterator1 first1,
      InputIterator1 last1, InputIterator2 first2,
      InputIterator2 last2, OutputIterator result);
template<class InputIterator1, class InputIterator2,
         class OutputIterator, class Compare>
OutputIterator set_difference(InputIterator1 first1,
      InputIterator1 last1, InputIterator2 first2,
      InputIterator2 last2, OutputIterator result,
      Compare comp);

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

（5）set_symmetric_difference()

template<class InputIterator1, class InputIterator2,
         class OutputIterator>
OutputIterator set_symmetric_difference(
               InputIterator1 first1, InputIterator1 last1,
               InputIterator2 first2, InputIterator2 last2,
               OutputIterator result);
template<class InputIterator1, class InputIterator2,
         class OutputIterator, class Compare>
OutputIterator set_symmetric_difference(
               InputIterator1 first1, InputIterator1 last1,
               InputIterator2 first2, InputIterator2 last2,
                 OutputIterator result, Compare comp);

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

5．使用堆

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

（1）make_heap()

template<class RandomAccessIterator>
void make_heap(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void make_heap(RandomAccessIterator first, RandomAccessIterator last,
               Compare comp);

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

（2）push_heap()

template<class RandomAccessIterator>
void push_heap(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void push_heap(RandomAccessIterator first, RandomAccessIterator last,
               Compare comp);

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

（3）pop_heap()

template<class RandomAccessIterator>
void pop_heap(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void pop_heap(RandomAccessIterator first, RandomAccessIterator last,
              Compare comp);

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

（4）sort_heap()

template<class RandomAccessIterator>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last,
               Compare comp);

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

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

template<class RandomAccessIterator>
bool is_heap(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
bool is_heap(RandomAccessIterator first, RandomAccessIterator last
               Compare comp);

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

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

template<class RandomAccessIterator>
RandomAccessIterator is_heap_until(RandomAccessIterator first,
                                     RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
RandomAccessIterator is_heap_until(
             RandomAccessIterator first, RandomAccessIterator last
             Compare comp);

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

6．查找最小和最大值

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

（1）min()

template<class T> const T& min(const T& a, const T& b);
template<class T, class Compare>
const T& min(const T& a, const T& b, Compare comp);

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

template<class T> T min(initializer_list<T> t);
template<class T, class Compare>
T min(initializer_list<T> t), Compare comp);

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

（2）max()

template<class T> const T& max(const T& a, const T& b);
template<class T, class Compare>
const T& max(const T& a, const T& b, Compare comp);

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

template<class T> T max(initializer_list<T> t);
template<class T, class Compare>
T max(initializer_list<T> t), Compare comp);

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

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

template<class T>
  pair<const T&,const T&> minmax(const T& a, const T& b);
template<class T, class Compare>
  pair<const T&,const T&> minmax(const T& a, const T& b,
                                 Compare comp);

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

template<class T> pair<T,T> minmax(initializer_list<T> t);
template<class T, class Compare>
pair<T,T> minmax(initializer_list<T> t), Compare comp);

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

（4）min_element()

template<class ForwardIterator>
ForwardIterator min_element(ForwardIterator first, ForwardIterator last);
template<class ForwardIterator, class Compare>
ForwardIterator min_element(ForwardIterator first, ForwardIterator last,
Compare comp);

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

（5）max_element()

template<class ForwardIterator>
ForwardIterator max_element(ForwardIterator first, ForwardIterator last);
template<class ForwardIterator, class Compare>
ForwardIterator max_element(ForwardIterator first, ForwardIterator last,
Compare comp);

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

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

template<class ForwardIterator>
  pair<ForwardIterator,ForwardIterator>
     minmax_element(ForwardIterator first, ForwardIterator last);
template<class ForwardIterator, class Compare>
  pair<ForwardIterator,ForwardIterator>
    minmax_element(ForwardIterator first, ForwardIterator last,
                Compare comp);

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

（7）lexicographical_compare()

template<class InputIterator1, class InputIterator2>
bool lexicographical_compare(
     InputIterator1 first1, InputIterator1 last1,
     InputIterator2 first2, InputIterator2 last2);
template<class InputIterator1, class InputIterator2, class Compare>
bool lexicographical_compare(
     InputIterator1 first1, InputIterator1 last1,
     InputIterator2 first2, InputIterator2 last2,
     Compare comp);

如果[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种排列如下：

123 132 213 232 312 321

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

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

（1）next_permutation()

template<class BidirectionalIterator>
bool next_permutation(BidirectionalIterator first,
                      BidirectionalIterator last);
template<class BidirectionalIterator, class Compare>
bool next_permutation(BidirectionalIterator first,
                      BidirectionalIterator last, Compare comp);

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

（2）prev_permutation()

template<class BidirectionalIterator>
bool prev_permutation(BidirectionalIterator first,
                      BidirectionalIterator last);
template<class BidirectionalIterator, class Compare>
bool prev_permutation(BidirectionalIterator first,
                      BidirectionalIterator last, Compare comp);

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

Previous 上一篇本节目录 Next 下一篇