C++

参考

<algorithm>

函数模板
<algorithm>

std::lexicographical_compare

默认 (1)
template <class InputIterator1, class InputIterator2>  bool lexicographical_compare (InputIterator1 first1, InputIterator1 last1,                                InputIterator2 first2, InputIterator2 last2);
自定义 (2)
template <class InputIterator1, class InputIterator2, class Compare>  bool lexicographical_compare (InputIterator1 first1, InputIterator1 last1,                                InputIterator2 first2, InputIterator2 last2,                                Compare comp);
字典序小于比较
如果范围 [first1,last1) 的字典序小于范围 [first2,last2)，则返回 true。

字典序比较 是在字典中对单词按字母顺序排序时通常使用的那种比较；它通过依次比较两个范围中相同位置的元素，直到其中一个元素不等于另一个为止。这些第一个不匹配元素的比较结果就是字典序比较的结果。

如果两个序列在其中一个结束之前都相等，则较短的序列字典序小于较长的序列。

元素使用第一个版本的 operator< 进行比较，第二个版本使用 comp。两个元素 a 和 b 被认为是等价的，如果 (!(a<b) && !(b<a))，或者如果 (!comp(a,b) && !comp(b,a))。

此函数模板的行为等同于
1
2
3
4
5
6
7
8
9
10
11
12
 
template <class InputIterator1, class InputIterator2>
  bool lexicographical_compare (InputIterator1 first1, InputIterator1 last1,
                                InputIterator2 first2, InputIterator2 last2)
{
  while (first1!=last1)
  {
    if (first2==last2 || *first2<*first1) return false;
    else if (*first1<*first2) return true;
    ++first1; ++first2;
  }
  return (first2!=last2);
}

参数

first1, last1
输入迭代器指向第一个序列的起始和结束位置。使用的范围是 [first1,last1)，它包含 first1 和 last1 之间的所有元素，包括 first1 指向的元素，但不包括 last1 指向的元素。
first2, last2
输入迭代器指向第二个序列的起始和结束位置。使用的范围是 [first2,last2)。
comp
二元函数，接受由迭代器指向的类型的两个参数，并返回一个可转换为 bool 的值。返回的值指示第一个参数在它定义的特定严格弱序中是否被认为排在第二个之前。
该函数不得修改其任何参数。
这可以是指向函数的指针，也可以是函数对象。

返回值

如果第一个范围的字典序小于第二个范围，则返回 true。
否则返回 false（包括当两个范围的所有元素都等价时）。

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
// lexicographical_compare example
#include <iostream>     // std::cout, std::boolalpha
#include <algorithm>    // std::lexicographical_compare
#include <cctype>       // std::tolower

// a case-insensitive comparison function:
bool mycomp (char c1, char c2)
{ return std::tolower(c1)<std::tolower(c2); }

int main () {
  char foo[]="Apple";
  char bar[]="apartment";

  std::cout << std::boolalpha;

  std::cout << "Comparing foo and bar lexicographically (foo<bar):\n";

  std::cout << "Using default comparison (operator<): ";
  std::cout << std::lexicographical_compare(foo,foo+5,bar,bar+9);
  std::cout << '\n';

  std::cout << "Using mycomp as comparison object: ";
  std::cout << std::lexicographical_compare(foo,foo+5,bar,bar+9,mycomp);
  std::cout << '\n';

  return 0;
}

默认比较会比较普通 ASCII 字符代码，其中 'A' (65) 小于 'a' (97)。
我们的 mycomp 函数在比较前会将字母转换为小写，因此这里第一个不匹配的字母是第三个（'a' vs 'p'）。

输出
Comparing foo and bar lexicographically (foo<bar):
Using default comparison (operator<): true
Using mycomp as comparison object: false



复杂度

最多执行 2*min(count1,count2) 次比较或 comp 的应用（其中 countX 是 firstX 和 lastX 之间的距离）。

复杂度

线性时间（最多为 2*min(count1,count2)，其中 countX 是 firstX 和 lastX 之间的距离）：对称地比较元素直到找到不匹配项。

数据竞争

访问范围 [first1,last1) 和 [first2,last2) 中的对象。

异常

如果元素比较或迭代器操作引发异常，则抛出。
请注意，无效参数会导致未定义行为。

另见

mismatch
返回两个范围首次出现差异的位置 （函数模板）
equal
测试两个范围中的元素是否相等 （函数模板）
search
在范围中搜索子序列 （函数模板）
find_end
在范围中查找最后一个子序列 （函数模板）
includes
测试一个已排序范围是否包含另一个已排序范围 （函数模板）