C++ STL比较算法std::lexicographical_compare()函数入门

前面一节我们学习了比较算法mismatch()函数，读者是否还记得它的功能是什么吗？没错，它不仅仅能判断两个序列是否完全相等，在不等的情况下，它还能帮我们找出哪一对元素不相等。本节我们将学习新的比较算法——lexicographical_compare()函数。“lexico”表示“字典”，“graphical”表示“书写的”，这里lexicographical_compare()函数指的是对两个序列进行字典序比较。读者是否了解什么是字典序？比如我们有两个字符串s1,s2;

string s1 = "Dotcpp";
string s2 = "dotcpp";
if(s1<s2)cout << "s1<s2\n";

因为'D'的ascii码小于'd'的ascii码，所以s1和s2进行第一个字符比较时就比不过了，所以会返回bool值true，输出“s1<s2”。我们也能通过lexicographical_compare()函数来对两个序列进行类似的比较。

lexicographical_compare()函数的语法格式如下：

// 形式1：使用默认的 < 操作符进行比较
template< class InputIt1, class InputIt2 >
bool lexicographical_compare( InputIt1 first1, InputIt1 last1,
                              InputIt2 first2, InputIt2 last2 );
// 形式2：使用自定义比较函数
template< class InputIt1, class InputIt2, class Compare >
bool lexicographical_compare( InputIt1 first1, InputIt1 last1,
                              InputIt2 first2, InputIt2 last2,
                              Compare comp );

lexicographical_compare(first1, last1, first2, last2)函数，它的功能是字典序比较区间[first1, last1)和[first2, last2)，有返回值，数据类型是bool值。

下面我们分别通过lexicographical_compare(first1, last1, first2, last2)对两个序列进行字典序比较：

#include<iostream>
#include<vector>
#include<functional>
#include<cmath>
#include<algorithm>
using namespace std;
/*普通函数&&判断误差在[0,1]之间都相等*/
bool pred(const float& f1, const float& f2)
{
    return abs(f1 - f2) <= 1.0f;
} 
/*lexicographical_compare(first1,last1,first2,last2)*/ 
void test1() {
    vector<int> v1{1, 2, 3, 4, 5};
    vector<int> v2{1, 2, 9, 4, 5};
    cout << "序列1为：";
    for(auto it = v1.begin(); it != v1.end(); ++it) cout << *it << " ";
    cout << '\n'; 
    cout << "序列2为：";
    for(auto it = v2.begin(); it != v2.end(); ++it) cout << *it << " ";
    cout << '\n'; 
    
    // 字典序比较 
    if(lexicographical_compare(v1.begin(), v1.end(), v2.begin(), v2.end()))
    {
        cout << "通过lexicographical_compare()函数判断两个序列得到【v1 < v2】\n\n";
    } else {
        cout << "通过lexicographical_compare()函数判断两个序列得到【v1 >= v2】\n";
    }
} 
/*lexicographical_compare(first1,last1,first2,last2,pred)*/ 
/*通过二元谓词进行模糊字典序比较*/ 
void test2() {
    vector<float> v1{1.1, 2.2, 3.9, 4.4, 5.5};
    vector<float> v2{1.2, 2.3, 2.5, 4.5, 5.6};
    cout << "序列1为：";
    for(auto it = v1.begin(); it != v1.end(); ++it) cout << *it << " ";
    cout << '\n'; 
    cout << "序列2为：";
    for(auto it = v2.begin(); it != v2.end(); ++it) cout << *it << " ";
    cout << '\n'; 
    
    // 模糊字典序比较 
    if(lexicographical_compare(v1.begin(), v1.end(), v2.begin(), v2.end(), pred))
    {
        cout << "通过lexicographical_compare()函数判断两个序列得到【v1 < v2】\n";
    } else {
        cout << "通过lexicographical_compare()函数判断两个序列得到【v1 >= v2】\n";
    }
} 
int main(){
    system("title dotcpp.com");
    test1();
    test2();
    return 0;
}

编译结果如下：

基于绝对比较规则，由于序列1中的“3”小于序列2中的“9”，所以“v1<v2”；基于模糊比较，由于序列1中的"3.9"与序列2中的"2.5"差值的绝对值不在[0,1]区间内，进而比较3.9 > 2.5，所以"v1 > v2"。

总结：就像字符串进行字典序比较一样，如果我们想让序列实现类似的比较行为，我们可以通过lexicographical_compare()函数进行比较；同时，在蓝桥杯、ACM等算法竞赛上该函数主要运用于最小表示问题，排列组合生成和多关键字排序等。