35.mismatch与lexicographical_compare

Posted on | In

前言

 
一个STL菜鸟最常问的问题是“我该如何使用STL来进行忽略大小写的字符串比较？”。这个问题说难很难（考虑国际化问题），说简单也简单（仅设计为strcmp那种样式）。

比较字符

 
在解决字符串比对问题之前，我们需要有一种方法确定两个字符忽略大小写后是否相等。我们仅考虑最简单的版本：

1
2
3
4
5
6
7
int ciCharCompare(char c1, char c2) { 
    int Ic1 = tolower(static_cast<unsigned char>(c1));
    int Ic2 = tolower(static_cast<unsigned char>(c2));
    if (Ic1 < Ic2) return -1;
    if (lc1 > Ic2) return 1;
    return 0;
}

此函数遵循了strcmp，可以返回1，-1，0三个值。由于各个char的实现不同（可能有符号可能无符号），我们先将其转为uc，然后再将它们转为小写，如此则忽略了大小写区别，最后将比较结果返回。

基于mismatch实现的字符串比对

 
在调用mismatch之前，我们必须确定一个字符串是否比另一个要短，将短字符串作为第一个区间传递。这项工作将由以下函数完成：

1
2
3
4
5
int ciStringCompareImpl(const string& s1, const string& s2);
int ciStringCompare(const string& s1, const string& s2){
    if (s1.size() <= s2.size()) return ciStringCompareImpl(s1, s2);
    else return -ciStringCompareImpl(s2, s1);
}

在真正的字符串比较函数中，大部分工作由mismatch来完成，它返回一对迭代器，表示两个区间中第一个对应的字符不相同的位置：
1
2
3
4
5
6
7
8
9
int ciStringCompareImpl(const string& si, const strings s2){
    typedef pair<string::const_iterator, string::const_iterator> PSCI;
    PSCI p = mismatch(s1.begin(), s1.end(), s2.begin(), not2(ptr_fun(ciCharCompare))); 
    if (p.first== s1.end()) {
        if (p.second == s2.end()) return 0; 
        else return -1;
    }
    return ciCharCompare(*p.first, *p.second);
}

重点在于函数中使用的not2与ptr_fun.
使用not2是因为mismatch的谓词返回false时算法停止工作，所以我们需要把charcompare返回的0变为1。ptr_function则类似于std::function。

基于lexicographical_compare实现的字符串比对

 
我们还有一个方法就是把之前的charcompare变成一种类似谓词的形式，这样配合算法使用效果更佳，如下所示：

1
2
3
4
5
6
bool ciCharLess(char c1, char c2){//函数对象
    tolower(static_cast<unsigned char>(c1)) < tolower(static_cast<unsigned char>(c2));
} 
bool ciStringCompare(const string& s1, const string& s2){
    return lexicographical_compare(s1.begin(), s1.end(),s2.begin(), s2.end(), ciCharLess);
}

lexicographical_cmp是strcmp的泛型版本。strcmp只对字符数组有效，但前者对任何类型的值的区间都起作用，并且支持自定义比较器。