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
測試一個已排序範圍是否包含另一個已排序範圍 （函式模板）