【C++】自定义比较器的正确姿势

发表于 | 更新于 | 分类于 ，

在 C++ 中有很多情况下，我们需要自定义比较器，无非就是三种情况：

  1. 对一个自定义的 struct 重写它的 operator < 方法
  2. 定义一个 Comparator 函数
  3. 定义一个 Comparator 结构体对象

这三个其实我都已经用过很多次了，但是偶尔还是会出错，主要是错在 const 这个关键字上，所以这次来整理总结一下。

1. 自定义的结构体

如果我们自定义了一个 struct，然后想要对其排序又不想额外写一个比较器，那么最好实现它的 operaotr < 方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
struct Str
{
    string s;
    bool operator < (const Str &str) const
    {
        return s.length() < str.s.length();
    }
};

int main()
{
    vector<Str> vec;
    for (int i = 0; i < 5; ++i)
    {
        Str s;
        cin >> s.s;
        vec.push_back(s);
    }
    stable_sort(vec.begin(), vec.end());
    return 0;
}

要注意这两个 const，如果写成这样: 

1
bool operator < (const Str &str)

会报错：

error: no match for 'operator<' (operand types are 'const Str' and 'Str')

如果是这样：

1
bool operator < (Str &str) const

则会：

error: binding 'const Str' to reference of type 'Str&' discards qualifiers

2. 函数比较器

可以通过编写一个外部的比较器函数，实现 < 功能。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool cmp(const string &s1, const string &s2)
{
    return s1.length() < s2.length();
}

int main()
{
    vector<string> vec;
    for (int i = 0; i < 5; ++i)
    {
        string s;
        cin >> s;
        vec.push_back(s);
    }
    stable_sort(vec.begin(), vec.end(), cmp);
    return 0;
}

同样，const 不可言省略，否则：

binding 'const std::__cxx11::basic_string' to reference of type 'std::__cxx11::basic_string&' discards qualifiers

3. 函数对象比较器

所谓函数对象是指实现了 operator () 的类或者结构体。可以用这样的一个对象来代替函数作为比较器。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
struct Cmper
{
    bool operator() (const string &s1, const string &s2)
    {
        return s1.length() < s2.length();
    }
};

int main()
{
    vector<string> vec;
    for (int i = 0; i < 5; ++i)
    {
        string s;
        cin >> s;
        vec.push_back(s);
    }
    stable_sort(vec.begin(), vec.end(), Cmper());
    return 0;
}

函数的两个参数位置的 const 不能省略，否则会报错：

error: binding 'const std::__cxx11::basic_string' to reference of type 'std::__cxx11::string& {aka std::__cxx11::basic_string&}' discards qualifiers

但是和第一个略有不同的是，方法末尾的 const 修饰可有可无。这是因为方法末尾的 const 代表了不会修改结构体内部变量的值，显然和我们要用到的功能毫无关系。

1
2
3
//这两个都可以
bool operator() (const string &s1, const string &s2)
bool operator() (const string &s1, const string &s2) const

最后要注意的是，传给 stable_sort 的应当是一个结构体对象而不是结构体名称。

1
2
3
4
//错
stable_sort(vec.begin(), vec.end(), Cmper);
//对
stable_sort(vec.begin(), vec.end(), Cmper());

否则会报错：

error: expected primary-expression before ')' token