字典序比较


类别: 算法	组件类型: 函数

原型

Lexicographical_compare是一个重载名称；实际上有两个字典序比较函数。

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

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

描述

Lexicographical_compare返回true如果元素范围[first1, last1)在字典序上小于元素范围[first2, last2), 并且false否则。字典序比较意味着“字典”（逐元素）排序。也就是说，[first1, last1)小于[first2, last2)如果*first1小于*first2, 并且如果大于则大于*first1大于*first2。如果前两个元素等价，则字典序比较比较第二个元素，依此类推。与普通的字典顺序一样，如果第一个范围中的每个元素都等于第二个范围中对应的元素，但第二个范围包含更多元素，则第一个范围被认为小于第二个范围。

这两个版本字典序比较在如何定义一个元素小于另一个元素方面有所不同。第一个版本使用operator<比较对象，第二个版本使用一个函数对象comp.

定义

在标准头文件algorithm中定义，并在非标准向后兼容头文件algo.h中定义。

类型要求

对于第一个版本

InputIterator1是输入迭代器的模型。
InputIterator2是输入迭代器的模型。
InputIterator1的值类型是小于可比较的模型。
InputIterator2的值类型是小于可比较的模型。
如果v1是InputIterator1的值类型的对象，并且v2是InputIterator2的值类型，则两者v1 < v2和v2 < v1都被定义。

对于第二个版本

InputIterator1是输入迭代器的模型。
InputIterator2是输入迭代器的模型。
BinaryPredicate是二元谓词的模型。
InputIterator1的值类型可转换为BinaryPredicate的第一个参数类型和第二个参数类型。
InputIterator2的值类型可转换为BinaryPredicate的第一个参数类型和第二个参数类型。

先决条件

[first1, last1)是一个有效的范围。
[first2, last2)是一个有效的范围。

复杂度

线性。最多2 * min(last1 - first1, last2 - first2)次比较。

示例

int main()
{
  int A1[] = {3, 1, 4, 1, 5, 9, 3};
  int A2[] = {3, 1, 4, 2, 8, 5, 7};
  int A3[] = {1, 2, 3, 4};
  int A4[] = {1, 2, 3, 4, 5};

  const int N1 = sizeof(A1) / sizeof(int);
  const int N2 = sizeof(A2) / sizeof(int);
  const int N3 = sizeof(A3) / sizeof(int);
  const int N4 = sizeof(A4) / sizeof(int);

  bool C12 = lexicographical_compare(A1, A1 + N1, A2, A2 + N2);
  bool C34 = lexicographical_compare(A3, A3 + N3, A4, A4 + N4);

  cout << "A1[] < A2[]: " << (C12 ? "true" : "false") << endl;
  cout << "A3[] < A4[]: " << (C34 ? "true" : "false") << endl;
}

注释

另请参阅

equal, mismatch, lexicographical_compare_3way, search, 小于可比较, 严格弱排序,sort