C++ priority_queue

定义

priority_queue 容器适配器模拟的也是队列这种存储结构, 即使用此容器适配器存储元素只能从一端进 (称为队尾), 从另一端出 (称为队头), 且每次只能访问 priority_queue 中位于队头的元素. 但是, priority_queue 容器适配器中元素的存和取, 遵循的并不是 First in, First out(先入先出) 原则, 而是 First in, Largest out 原则. 直白的翻译, 指的就是先进队列的元素并不一定先出队列, 而是优先级最大的元素最先出队列.

举个例子, 假设当前有一个 priority_queue 容器适配器, 其制定的排序规则是按照元素值从大到小进行排序. 根据此规则, 自然是 priority_queue 中值最大的元素的优先级最高.

priority_queue 容器适配器为了保证每次从队头移除的都是当前优先级最高的元素, 每当有新元素进入, 它都会根据既定的排序规则找到优先级最高的元素, 并将其移动到队列的队头; 同样, 当 priority_queue 从队头移除出一个元素之后, 它也会再找到当前优先级最高的元素, 并将其移动到队头. 基于 priority_queue 的这种特性, 因此该容器适配器有被称为优先级队列.

STL 中, priority_queue 容器适配器的定义如下:

template<typename T,
         typename Container=std::vector<T>,
         typename Compare=std::less<T>>
class priority_queue{
    //......
}

可以看到, priority_queue 容器适配器模板类最多可以传入 3 个参数, 它们各自的含义如下:

• typename T: 指定存储元素的具体类型;
• typename Container: 指定 priority_queue 底层使用的基础容器, 默认使用 vector 容器.
  • 注: 作为 priority_queue 容器适配器的底层容器, 其必须包含 empty(), size(), front(), push_back(), pop_back() 这几个成员函数, STL 序列式容器中只有 vector 和 deque 容器符合条件.
• typename Compare: 指定容器中评定元素优先级所遵循的排序规则, 默认使用 std::less 按照元素值从大到小进行排序, 还可以使用 std::greater 按照元素值从小到大排序, 但更多情况下是使用自定义的排序规则.

其中, std::less 和 std::greater 都是以函数对象的方式定义在头文件中.

创建 priority_queue 的几种方式

由于 priority_queue 容器适配器模板位于头文件中, 并定义在 std 命名空间里, 因此在试图创建该类型容器之前, 程序中需包含以下 2 行代码:

#include <queue>
using namespace std;

创建 priori_queue 容器适配器的方法.

创建一个空的 priority_queue 容器适配器

创建一个空的 priority_queue 容器适配器, 底层采用默认的 vector 容器, 排序方式也采用默认的 std::less 方法:

std::priority_queue<int> values;

使用普通数组或其它容器中指定范围内的数据

可以使用普通数组或其它容器中指定范围内的数据, 对 priority_queue 容器适配器进行初始化:

// 使用普通数组
int values[]={4, 2, 3, 1};
std::priority_queue<int>copy_values(values, values+4);// {4, 2, 3, 1}
// 使用序列式容器
std::array<int, 4>values{ 4, 2, 3, 1 };
std::priority_queue<int>copy_values(values.begin(), values.end());// {4, 2, 3, 1}

注意, 以上 2 种方式必须保证数组或容器中存储的元素类型和 priority_queue 指定的存储类型相同. 另外, 用来初始化的数组或容器中的数据不需要有序, priority_queue 会自动对它们进行排序.

手动指定 priority_queue 使用的底层容器以及排序规则

还可以手动指定 priority_queue 使用的底层容器以及排序规则, 比如:

int values[]{ 4, 1, 2, 3 };

// {1, 2, 3, 4}
std::priority_queue<int, std::deque<int>, std::greater<int> >copy_values(values, values+4);

priority_queue 提供的成员函数

和 queue 一样, priority_queue 也没有迭代器, 因此访问元素的唯一方式是遍历容器, 通过不断移除访问过的元素, 去访问下一个元素.

priority_queue 的排序方式, 及自定义排序

• less 变成大顶堆 (从上层到下层, 堆元素是从大到小, 同层之间随便)
• greater 变成小顶堆 (从上层到下层, 堆元素是从小到大, 同层之间随便)

首先, 无论 priority_queue 中存储的是基础数据类型 (int, double 等), 还是 string 类对象或者自定义的类对象, 都可以使用函数对象的方式自定义排序规则. 例如:

#include<iostream>
#include<queue>
using namespace std;
//函数对象类
template <typename T>
class cmp {
public:
    //重载 () 运算符
    bool operator()(T a, T b) {
        return a > b;
    }
};

int main() {
    int a[] = { 4, 2, 3, 5, 6 };
    priority_queue<int, vector<int>, cmp<int> > pq(a, a+5);//第三个传入参数 cmp 制定自定义的排序方式
    while (! pq.empty()) {
        cout << pq.top() << " ";
        pq.pop();
    }
    return 0;
}

其中 cmp 也可以用 struct 关键字创建:

struct cmp {
    //重载 () 运算符
    bool operater()(T a, T b) {
        return a > b;
    }
}

std::less 和 std::greater 的底层实现方式:

// std::less<T> 的底层实现代码
template <typename T>
struct less {
    //定义新的排序规则
    bool operator()(const T &_lhs, const T &_rhs) const {
        return _lhs < _rhs;
    }
};

// std::greater<T> 的底层实现代码
template <typename T>
struct greater {
    bool operator()(const T &_lhs, const T &_rhs) const {
        return _lhs > _rhs;
    }
};

踩坑记录

比较的规则

priority_queue 默认是大根堆, 即默认从大小排列的, 比较函数中返回 true 的话, 默认就到队尾去了.

比较的优雅写法

如果要对 a, b, c 三个参数进行比较, 容易理解且优雅的写法如下:

template<typename T>
class cmp {
public:
    bool operator()(const T& a, const T& b) {
        if (a.x1 == b.x1 && a.x2 == b.x2) return a.x3 > b.x3;
        if (a.x1 = b.x2) return a.x2 < b.x2;
        return a.x1 > b.x1;
    }
};

这样写真的非常简洁.

比较的坑

暂时不清楚优先队列中的比较是怎么做的, 但是比较需要满足一定的规则, 不能在比较的时候将可变的参数放进去了, 以下就是我的惨痛教训.

template<typename T>
class cmp {
public:
    bool operator()(const T& a, const T& b) {

        auto& a_first = a.first;
        auto& b_first = b.first;

        // 问题就出现在这里, 这里 size 是动态变化的, 所以会导致排序不符合预期
        // 好的做法是可以将数据 push 到优先队列之前提计算出一个不变的 size
        // 记住就是放进去的数据就不要再变动了, 现在的数据结构不支持这种做法
        int a_size = a_first->size();
        int b_size = b_first->size();
        int a_idx = a_first->back();
        int b_idx = b_first->back();
        int a_version = a.second;
        int b_version = b.second;

        if (a_size < b_size) {
            return true;
        } else if (a_size > b_size) {
            return false;
        } else {
            if (a_idx < b_idx) {
                return true;
            } else if (a_idx > b_idx) {
                return false;
            } else {
                return a_version > b_version;
            }
        }
    }
};

class FreqStack {
public:
    int data[20010];                                // 存储栈中的数据, 提前分配内存
    int top = -1;                                   // 栈顶
    unordered_map<list<int>*, int> versionMap;      // 元素下标链的版本
    unordered_map<int, list<int>*> numberToListMap; // 元素对应的

    priority_queue<pair<list<int>*, int>, std::deque<pair<list<int>*, int>>, cmp<pair<list<int>*, int>>> pq;

    FreqStack() {
        // 清零底层数组
        memset(data, 0, sizeof(data));
    }

    void push(int val) {
        cout << "push, val = " << val << ",  top = " << top + 1 << endl;

        list<int>* list1;
        if (numberToListMap.count(val) == 0) {
            list1 = new list<int>();
            numberToListMap[val] = list1;
        } else {
            list1 = numberToListMap[val];
        }

        data[++top] = val;
        list1->push_back(top);
        pq.push(make_pair(list1, ++versionMap[list1]));
    }

    int pop() {

        cout << "pop.........." << endl;
        int ret;
        while(true) {
            auto pair1 = pq.top();
            pq.pop();
            list<int>* list1 = pair1.first;
            int version = versionMap[list1];
            cout << "version = " << version << ", pair1.second = " << pair1.second << endl;
            if (version == pair1.second) {
                int index = list1->back();
                cout << "index = " << index << endl;
                int val = data[index];
                ret = val;
                list1->pop_back();
                if (! list1->empty()) {
                    pq.push(make_pair(list1, ++versionMap[list1]));
                } else {
                    numberToListMap.erase(val);
                    versionMap.erase(list1);
                    delete list1;
                }
                break;
            }
        }

        return ret;
    }
};

/**
 * Your FreqStack object will be instantiated and called as such:
 * FreqStack* obj = new FreqStack();
 * obj->push(val);
 * int param_2 = obj->pop();
 */

参考

• https://blog.csdn.net/qq_43679351/article/details/124825229

本文来自：https://blog.duhbb.com

本文链接地址：C++ priority_queue，英雄不问来路，转载请注明出处，谢谢。

有话想说：那就赶紧去给我留言吧。