C++优先队列

  重载比较器有两种方式：重载小于号和自定义比较函数（重载括号）。其中，重载小于号可以直接写在你的类里面，需要注意的就是两个const。重载括号需要新开一个类写。
  需要注意的是，优先队列实际的排序顺序和你比较器里面定义的顺序（或者说和其他STL模板相比）是反过来的，例如下面的程序：

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

// 方法1：重载小于号
class myPoint1 {
public:
        int x, y;
        myPoint1(int x, int y) : x(x), y(y) { }

        // 方法1：重载小于号，这里的参数const和后面的const都不能少
        // 后面的const修饰的是类函数隐藏的第一个参数 this指针，这表明this指针只读，也即类成员不可修改
        // 注意该用法只能是成员函数，要是类的静态函数或者是非成员函数就不可以在函数名后面加上const
        bool operator < (const myPoint1& p) const
        {
                if (x == p.x) return y < p.y;
                return x < p.x;
        }
};

// 方法2：自定义比较函数
class myPoint2 {
public:
        int x, y;
        myPoint2(int x, int y) : x(x), y(y) { }
};

// 方法2：自定义比较函数
class myComparator {
// 如果是class，public不能少；否则就用struct
public:
        bool operator () (myPoint2 &a, myPoint2 &b)
        {
                if (a.x == b.x) return a.y < b.y;
                return a.x < b.x;
        }
};

std::priority_queue<myPoint1> pq1;

std::priority_queue<myPoint2, std::vector<myPoint2>, myComparator> pq2;

int main()
{
        pq1.push(myPoint1(1, 2));
        pq1.push(myPoint1(2, 1));
        pq1.push(myPoint1(1, 1));
        pq1.push(myPoint1(0, 1));
        pq1.push(myPoint1(2, 2));

        while (!pq1.empty())
        {
                myPoint1 p = pq1.top();
                pq1.pop();
                std::cout << p.x << " " << p.y << std::endl;
        }

        std::cout << "---------------------------" << std::endl;
        
        pq2.push(myPoint2(1, 2));
        pq2.push(myPoint2(2, 1));
        pq2.push(myPoint2(1, 1));
        pq2.push(myPoint2(0, 1));
        pq2.push(myPoint2(2, 2));

        while (!pq2.empty()) {
                myPoint2 p = pq2.top();
                pq2.pop();
                std::cout << p.x << " " << p.y << std::endl;
        }
}

  运行结果是：

2 2
2 1
1 2
1 1
0 1
---------------------------
2 2
2 1
1 2
1 1
0 1

  很显然，这和我们定义的X小在前并不相同，而是相反。具体原因我也不清楚，不过好像是因为优先队列是大根堆，然后top是倒着访问的。

sort自定义比较函数

  下面是一个sort函数自定义比较函数的例子：

#include <iostream>
#include <vector>
#include <algorithm>

std::vector <int> v1 = {3,2,1,5,4,3,6,2,1,4,5,9};

bool cmp(int a, int b)
{
        return a < b;
}

int main()
{
        std::sort(v1.begin(), v1.end(), cmp);

        for (auto &it : v1) {
                std::cout << it << " ";
        }
}

  输出结果是：

1 1 2 2 3 3 4 4 5 5 6 9

  因为我们的cmp函数的含义是，a是不是应该排在b前面？如果函数返回1，那么a在b前面，而cmp里面写的是 a < b ，所以是从小到大排序。