c++的priority

• • 一、基础知识
  • • 1. priority基本知识
    • 2. `priority_queue` 的 `API` 接口
  • 二、预备知识
  • 三、自定义排序规则
  • • 1. 使用函数对象
    • 2. 自定义类
    • 3. 函数指针
    • 4. 使用lamada表达式
  • 附录：源代码

priority_queue 是容器适配器，它提供常数时间的（默认）最大元素查找，对数代价的插入与释出。

可用用户提供的Compare更改顺序，例如，用 std::greater 将导致最小元素作为top()出现。

用priority_queue工作类似管理某些随机访问容器中的堆，优势是不可能突然把堆非法化。

priority_queue 容器适配器定义了一个元素有序排列的队列。默认队列头部的元素优先级最高。因为它是一个队列，所以只能访问第一个元素，这也意味着优先级最高的元素总是第一个被处理。但是如何定义“优先级”完全取决于我们自己。如果一个优先级队列记录的是医院里等待接受急救的病人，那么病人病情的严重性就是优先级。如果队列元素是银行的借贷业务，那么借记可能会优先于信贷。

priority_queue 模板有 3 个参数，其中两个有默认的参数；第一个参数是存储对象的类型，第二个参数是存储元素的底层容器，第三个参数是函数对象，它定义了一个用来决定元素顺序的断言。因此模板类型是：

template , typename Compare=std::less> class priority_queue

priority_queue 实例默认有一个 vector 容器。函数对象类型 less 是一个默认的排序断言，定义在头文件 function 中，决定了容器中最大的元素会排在队列前面。fonction 中定义了 greater，用来作为模板的最后一个参数对元素排序，最小元素会排在队列前面。当然，如果指定模板的最巵一个参数，就必须提供另外的两个模板类型参数。

优先级队列可以使用任何容器来保存元素，只要容器有成员函数 front()、push_back()、pop_back()、size()、empty()。

对 priority_queue 进行操作有一些限制：

1. push(const T& obj)：将obj的副本放到容器的适当位置，这通常会包含一个排序操作。
2. push(T&& obj)：将obj放到容器的适当位置，这通常会包含一个排序操作。
3. emplace(T constructor a rgs...)：通过调用传入参数的构造函数，在序列的适当位置构造一个T对象。为了维持优先顺序，通常需要一个排序操作。
4. top()：返回优先级队列中第一个元素的引用。
5. pop()：移除第一个元素。
6. size()：返回队列中元素的个数。
7. empty()：如果队列为空的话，返回true。
8. swap(priority_queue& other)：和参数的元素进行交换，所包含对象的类型必须相同。

重载函数调用操作符的类，其对象称为函数对象。
函数对象使用重载的()时，行为类似函数调用，也叫仿函数。
函数对象（仿函数）是一个类，不是一个函数。

一般如果使用指针的话，就需要使用函数对象了。

使用函数对象需要注意的是，优先队列在声明的时候采取：

template<
    class T,
    class Container = std::vector,
    class Compare = std::less
> class priority_queue;

这样的声明方式，

T：参数类型
Container：容器类型。默认是用vector容器实现，参数类型必须是T
Compare：排序规则。默认是小顶堆弹出std::less

1. 第一个参数为优先队列存储的类型
2. 第二个参数为实现优先队列的容器类型
3. 第三个参数为排序的仿函数名称

struct persion{
    int age;
    persion(int a){age = a;}

    bool operator<(const persion& a) const {
        return this->age < a.age;
    }
};

struct cmp{
    bool operator()(persion *a, persion *b) const{
        return a->age < b-> age;
    }
};

int main() {
    cout << "cds:" << endl;
    priority_queue, cmp> container;
    persion* a = new persion(3);
    container.emplace(a);
    container.emplace(new persion(5));
    container.emplace(new persion(1));
    container.emplace(new persion(4));
    container.emplace(new persion(2));

    while (!container.empty()) {
        cout << container.top()->age << " ";
        container.pop();
    }
    cout << endl;
    return -1;
}

• 输出

5 4 3 2 1 

对于自定义的类，比如persion类，想要进入优先队列进行自动排序，仅需要重载类的<运算符即刻。

struct persion{
    int age;
    persion(int a){age = a;}

    bool operator<(const persion& a) const {
        return this->age > a.age;
    }
};

int main() {

    cout << "重载<运算符:" << endl;
    priority_queue p;
    p.emplace(persion(4));
    p.emplace(persion(1));
    p.emplace(persion(3));
    p.emplace(persion(2));
    while (!p.empty()) {
        cout << p.top().age << " ";
        p.pop();
    }
    cout << endl;
}

• 输出：

重载<运算符:
1 2 3 4 

bool cmpFun(const Node &a, const Node &b) {
    return a.size == b.size ? a.price > b.price : a.size < b.size;
}
priority_queue, decltype(cmpFun)*> priorityQueue(cmpFun);

举例：

struct persion{
    int age;
    persion(int a){age = a;}

//    bool operator<(const persion& a) const {
//        return this->age > a.age;
//    }
};

bool cmp_f(const persion& a,const persion& b)  {
    return  a.age < b.age;
}
int main(){
    cout << "函数指针:"  << endl;
    priority_queue, decltype(cmp_f)*> dd(cmp_f);
    dd.emplace(persion(4));
    dd.emplace(persion(2));
    dd.emplace(persion(3));
    dd.emplace(persion(1));
    while (!dd.empty()){
        cout << dd.top().age << " ";
        dd.pop();
    }
    cout << endl;
}

• 输出：

函数指针:
4 3 2 1 

    // 用 lambda 比较元素。
    auto cmp = [](int left, int right) { return (left ^ 1) < (right ^ 1); };
    std::priority_queue, decltype(cmp)> q3(cmp);

• 输出：

使用函数对象:
1 2 3 4 5 
重载<运算符:
1 2 3 4 
函数指针:
1 2 3 4 
lamda表达式：
1 2 3 4 

• 源代码

#include 
#include 
#include 
#include 
#include 

using namespace std;

struct persion{
    int age;
    persion(int a){age = a;}

    bool operator<(const persion& a) const {
        return this->age > a.age;
    }
};

bool cmp_f(const persion& a,const persion& b)  {
    return  a.age > b.age;
}

struct cmp{
    bool operator()(persion *a, persion *b) const{
        return a->age > b-> age;
    }
};


void funcation_obj();

void opreator_less();

void funcaton_pointer();

void lamada_();

int main() {
    // 1. 函数对象
    funcation_obj();
    // 2. 重载操作服
    opreator_less();
    // 3. 函数指针
    funcaton_pointer();
    // 4. lamada表达式
    lamada_();
    return -1;
}

void lamada_() {
    auto lam = [](persion a, persion b){
        return a.age > b.age;
    };
    cout << "lamda表达式：" << endl;
    priority_queue, decltype(lam)> lam_contaner(lam);
    lam_contaner.emplace(persion(1));
    lam_contaner.emplace(persion(4));
    lam_contaner.emplace(persion(3));
    lam_contaner.emplace(persion(2));
    while (!lam_contaner.empty()){
        cout << lam_contaner.top().age << " ";
        lam_contaner.pop();
    }
    cout << endl;
}

void funcaton_pointer() {
    cout << "函数指针:" << endl;
    priority_queue, decltype(cmp_f)*> dd(cmp_f);
    dd.emplace(persion(4));
    dd.emplace(persion(2));
    dd.emplace(persion(3));
    dd.emplace(persion(1));
    while (!dd.empty()){
        cout << dd.top().age << " ";
        dd.pop();
    }
    cout << endl;
}

void opreator_less() {
    cout << "重载<运算符:" << endl;
    priority_queue p;
    p.emplace(persion(4));
    p.emplace(persion(1));
    p.emplace(persion(3));
    p.emplace(persion(2));
    while (!p.empty()) {
        cout << p.top().age << " ";
        p.pop();
    }
    cout << endl;
}

void funcation_obj() {
    cout << "使用函数对象:" << endl;
    priority_queue, cmp> container;
    persion* a = new persion(3);
    container.emplace(a);
    container.emplace(new persion(5));
    container.emplace(new persion(1));
    container.emplace(new persion(4));
    container.emplace(new persion(2));

    while (!container.empty()) {
        cout << container.top()->age << " ";
        container.pop();
    }
    cout << endl;
}

参考链接：
cppreference: priority_queue