• c++的priority_queue各种使用方法

    文章目录

    一、基础知识

    1. priority基本知识

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

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

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

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

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

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

    • 1
    • 2

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

    2. priority_queue 的 API 接口

    优先级队列可以使用任何容器来保存元素，只要容器有成员函数 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)：和参数的元素进行交换，所包含对象的类型必须相同。

    二、预备知识

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

    三、自定义排序规则

    1. 使用函数对象

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

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

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

    • 1
    • 2
    • 3
    • 4
    • 5

    这样的声明方式，

    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;
}

    • 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
    • 输出
    5 4 3 2 1 

    • 1

    2. 自定义类

    对于自定义的类，比如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
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 输出：
    重载<运算符:
1 2 3 4 

    • 1
    • 2

    3. 函数指针

    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);


    • 1
    • 2
    • 3
    • 4
    • 5

    举例：

    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;
}

    • 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
    • 输出：
    函数指针:
4 3 2 1 


    • 1
    • 2
    • 3

    4. 使用lamada表达式

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

    • 1
    • 2
    • 3

    附录：源代码

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 源代码
    #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;
}




    • 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
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112

    参考链接：
    cppreference: priority_queue

  • 相关阅读:
    C++多线程同步
    Shopee可以绑定大陆银行卡吗？Shopee收款方式选哪种？——站斧浏览器
    实现支付宝订单状态查询_大数据培训
    一篇五分生信临床模型预测文章代码复现——Figure 3. 基因富集分析（二）
    经典算法学习之-----直接选择排序
    pytorch深度学习实战lesson13
    2.证明 非单一点 Oct.2023
    python调用c++版本dll03-简单的函数调用
    JavaSE 第六章 面向对象基础-中（继承）
    vue3中css使用script中定义的变量
  • 原文地址：https://blog.csdn.net/sexyluna/article/details/125901499