C++ 自定义比较器

重载操作符 <

实际上是对自定义的 struct，重写它的 operator < 方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct Str{
    string s;
    bool operator < (const Str &str) const { //注意有两个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);
    }
    sort(vec.begin(), vec.end());
    return 0;
}

函数比较器

可以通过写一个外部的比较器函数，实现 < 方法：

使用这种方式常常用在如下情形：

  1. 比较内置类型

  2. 不能修改需要比较的运算符

  3. 除了类型自定义的比较方式以外的比较方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool cmp(const string &s1, const string &s2) { //const 切记不要漏
    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);
    }
    sort(vec.begin(), vec.end(), cmp);
    return 0;
}

函数对象结构体比较器

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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);
    }
    sort(vec.begin(), vec.end(), Cmper());
    return 0;
}

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

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

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

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

C++ 优先队列自定义比较

重载运算符

成员函数写法

1
2
3
4
5
6
7
8
9
10
11
12
struct Node {
    int x, y;
    bool operator<(Node &a) const {    //必须加const
        return y < a.y;
    }
    bool operator>(Node &a) const {    //必须加const
        return y > a.y;
    }
};
//  priority_queue<Node> A;   //默认  大根堆
priority_queue<Node, vector<Node>, less<Node>>A;    //大根堆
priority_queue<Node, vector<Node>, greater<Node>> B;    //小根堆
1
2
3
4
5
6
7
struct Node {
    int x, y;
    bool operator<(Node &a) const {    //必须加const
        return y < a.y;
    }
};
priority_queue<Node>A;    //大根堆
1
2
3
4
5
6
7
struct Node {
    int x, y;
    bool operator<(Node &a) const {    //必须加const
        return y > a.y;
    }
};
priority_queue<Node> B;    //小根堆

友元函数写法

1
2
3
4
5
6
7
8
9
10
11
12
struct Node {
    int x, y;
    friend bool operator<(const Node &a, const Node &b) {
        return  a.x < b.x; //大顶堆
    }
    friend bool operator>(const Node &a, const Node &b) {
        return  a.x > b.x; //小顶堆
    }
};

priority_queue<Node> A; //默认 大根堆
priority_queue<Node, vector<Node>, greater<Node> > B; //小根堆
1
2
3
4
5
6
7
8
struct Node {
    int x, y;
    friend bool operator<(const Node &a, const Node &b) {
        return  a.x < b.x;  //大顶堆
    }
};

priority_queue<Node> A; //大根堆
1
2
3
4
5
6
7
struct Node {
    int x, y;
    friend bool operator<(const Node &a, const Node &b) {
        return  a.x > b.x; //小顶堆
    }
};
priority_queue<Node> B; //小根堆

函数对象比较器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct Node {
    int x, y;
};

struct cmp {
    bool operator()(Node &a,Node &b) {
        return  a.x > b.x;  //小顶堆
    }
};

struct cmp1 {
    bool operator()(Node &a,Node &b) {
        return  a.x < b.x;  //大顶堆
    }
};

priority_queue<Node, vector<Node>, cmp1> A;      //大根堆
priority_queue<Node, vector<Node>, cmp> B;    //小根堆

自定义函数比较器

如果想要用升序排列怎么办？先看一下优先队列的定义

1
priority_queue<Type, Container, Functional>

其中 Type 就是数据类型，Container 就是容器类型（ Container 必须是用数组实现的容器，比如 vector, deque 等等，但不能用 list。STL里面默认用的是vector），Functional 就是比较的方式，当需要用自定义的数据类型时才需要传入这三个参数，使用基本数据类型时，只需要传入数据类型，默认是大顶堆。
 
如果传入的是int类型，我们可以用👇定义一个升序优先队列

1
priority_queue <int,vector<int>,greater<int>> pq;

如果要定义一个降序优先队列（等同于默认的不写 Container , Functional 的方式），可以使用这种方法：

1
priority_queue <int,vector<int>,less<int>> pq;

其中greater和less是std实现的两个仿函数
 
如果不想用greater和less，可以使用自定义的比较方法：

1
2
auto comp = []( int a, int b ) { return a > b; };
 priority_queue< int , vector<int>, decltype(comp)> pq(comp);

问题来了，为什么初始化pq的时候还要传comp进去？
按照我们熟悉的sort函数的经验，sort使用lambda表达式定制排序时，可以这样写：

1
sort (vec.begin(), vec.end(), [](int a, int b) { return a < b; });

比着葫芦画瓢，把priority_queue写成👇却不行。

1
priority_queue< int , vector<int>, [](int a, int b) { return a < b; }> pq;

为什么会出现这种情况，这就需要看一下priority_queue的构造函数：

1
2
explicit priority_queue( const Compare& compare = Compare(),
                         const Container& cont = Container() );

可以看到，如果我们构造时，不指定特定的compare对象，那么就用typename Compare的默认构造函数构造一个，然而lambda表达式的匿名类型是没有默认构造函数的，所以想要正确初始化这个优先队列，还得在构造函数里再把lambda表达式本身传进去。

优先队列自定义比较总结

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class student {
public:
    int age;
    string name;
    /**重载小于操作符，
     *这里必须是非成员函数才可以
     */
    friend bool operator<(const student& a, const student& b) {
        return a.age < b.age;
    }
};

/**可调用的函数操作符的对象*/
struct mycmp {
    bool operator()(const student& a, const student& b) { return a.age < b.age; }
};

/**函数指针*/
bool cmpfunc(const student& a, const student& b) { return a.age < b.age; }

/**默认使用student的oprator<来进行比较*/
priority_queue<student> que1;

/**使用重载函数操作符的类对象*/
priority_queue<student, vector<student>, mycmp> que2;

/**定义一下比较函数*/
auto cmp = [](const student& a, const student& b) { return a.age < b.age; };
/**
 *	需要把lambda表达式作为优先队列参数进行初始化
 * 并且指定priority_queue的模板实参，decltype(cmp)，c++11 declare type，声明类型
 * 可以认为是确定函数的类型
 * bool (const student & a,const student & b)
 **/
priority_queue<student, vector<student>, decltype(cmp)> que4(cmp);

/*使用函数对象来定义这个比较函数原型*/
// lambda 函数来初始化函数对象
priority_queue<student, vector<student>,
    function<bool(const student&, const student&)>>
    que5(cmp);

//函数指针来初始化函数对象
priority_queue<student, vector<student>,
    function<bool(const student&, const student&)>>
    que6(cmpfunc);

/**函数对象*/
function<bool(const student&, const student&)> func(cmpfunc);
priority_queue<student, vector<student>,
    function<bool(const student&, const student&)>>
    que7(func);

队列节点是指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct Node {
    int x, y;
};
struct cmp {
    bool operator() (Node const *n1, Node const *n2) {
        return n1->x < n2->x;     //大顶推
    }
};
struct cmp1 {
    bool operator() (Node const *n1, Node const *n2) {
        return n1->x > n2->x;     //小顶推
    }
};

priority_queue<Node*, vector<Node*>, cmp()> A;   //大根堆
priority_queue<Node*, vector<Node*>, cmp1()> B;  //小根堆