admin管理员组文章数量:1623803
priority_queue 的基本用法
priority_queue 简介
参考:std::priority_queue - cppreference
priority_queue 是容器适配器,它提供常数时间的(默认)最大元素查找,对数代价的插入与释出。
可用用户提供的 Compare 更改顺序,例如,用 std::greater 将导致最小元素作为 top() 出现。
用 priority_queue 工作类似管理某些随机访问容器中的堆,优势是不可能突然把堆非法化。
priority_queue 的初始化
// 规定数据类型,默认底层容器为 vector,默认的比较器为 less
// 此时优先队列也就维护了一个大顶堆
// 相当于 priority_queue<int, vector<int>, less<int>>
priority_queue<int> queue1;
// 规定数据类型,底层容器,比较器
priority_queue<int, vector<int>, greater<int>> queue2;
常用方法案例
先声明一个 priority_queue 对象,默认传入的容器是 vector,默认的比较器是 less 比较器。
priority<int> queue;
// 此时 queue 中没有元素
- push
queue.push(1);
queue.push(2);
// 此时 queue 中有两个元素,为 {1,2}
- pop
queue.pop();
// 由于默认比较器是 less,pop会弹出堆顶元素,也就是弹出队列中的最大元素。
// 此时 queue 中有一个元素,为 {1}
- top
queue.top();
// 获取堆顶元素,也就是队列中的最大元素,因为队列中只有一个元素 1,所以会返回 1。
- empty
queue.empty();
// 判断队列是否为空,返回值为 bool 类型。由于 queue 中还有一个元素,所以会返回 true。
- size
queue.size();
// 获取队列中元素的个数,由于 queue 中还有一个元素,所以会返回 1。
- swap
方法的参数声明时传入的模板参数需要跟调用对象声明时一致或者兼容
// 申请另外一个 priority_queue 对象,
// 参数声明时传入的模板参数需要跟调用对象声明时一致或兼容
// 比如
// priority_queue<int> queue1;
// priority_queue<int> queue2;
// 这个情况,可以执行 queue1.swap(queue2) 方法。
// 但是
// priority_queue<int, vector<int>, greater<int>> queue1;
// priority_queue<int, vector<int>, less<int>> queue2;
// 这个情况,是不能执行 queue1.swap(queue2) 或者 queue2.swap(queue1) 方法的
// 是因为这两个队列的模板类型不一样,
// queue1 的比较器是 greater,而 queue2 的比较器是 less
priority_queue<int> queue2;
queue.swap(queue2);
// 此时由于执行了 swap 方法,将 queue 中的元素变为 queue2 中的元素,而 queue2 中没有元素
// 所以当前 queue 中没有元素。
- emplace
原地构造一个元素并插入队列
queue.emplace(3);
// 这时 queue 有一个元素,为 {3}
测试不同的比较器
- less(维护大顶堆)
priority_queue<int, vector<int>, less<int>> queue_less;
queue_less.push(4);
queue_less.push(3);
queue_less.push(2);
queue_less.push(1);
while (!queue_less.empty()) {
int top = queue_less.top();
cout << top << "\t";
queue_less.pop();
}
// 输出结果
// 4 3 2 1
- greater(维护小顶堆)
priority_queue<int, vector<int>, greater<int>> queue_greater;
queue_greater.push(1);
queue_greater.push(2);
queue_greater.push(3);
queue_greater.push(4);
while (!queue_greater.empty()) {
int top = queue_greater.top();
cout << top << "\t";
queue_greater.pop();
}
// 输出结果
// 1 2 3 4
- 自定义比较器
// 定义一个比较器
auto cmp = [](int val1, int val2) { return val1 < val2; };
priority_queue<int, vector<int>, decltype(cmp)> queue_cmp(cmp);
queue_cmp.push(1);
queue_cmp.push(2);
queue_cmp.push(3);
queue_cmp.push(4);
while (!queue_cmp.empty()) {
int top = queue_cmp.top();
cout << top << "\t";
queue_cmp.pop();
}
// 输出结果
// 4 3 2 1
- 重写仿函数
struct cmp {
bool operator() (int val1, int val2) { return val1 < val2; }
};
priority_queue<int, vector<int>, cmp> queue_cmp;
queue_cmp.push(1);
queue_cmp.push(2);
queue_cmp.push(3);
queue_cmp.push(4);
while (!queue_cmp.empty()) {
int top = queue_cmp.top();
cout << top << "\t";
queue_cmp.pop();
}
// 输出结果
// 4 3 2 1
- 重写 < 运算符
struct Node {
int val;
bool operator<(const Node node) const {
return this->val < node.val;
}
};
priority_queue<Node> queue_node;
queue_node.push(Node{1});
queue_node.push(Node{2});
queue_node.push(Node{3});
queue_node.push(Node{4});
while (!queue_node.empty()) {
Node node = queue_node.top();
cout << node.val << "\t";
queue_node.pop();
}
// 输出结果
// 4 3 2 1
如有不正确的地方,还望指出。
本文标签: priorityqueue
版权声明:本文标题:c++ priority_queue 的基本用法 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/dianzi/1728895801a1178389.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论