首页 > C++教程 > STL(标准模板库)
阅读:3,013
C++ queue和priority_queue,STL queue和priority_queue
queue 和 priority_queue 都是容器适配器,要使用它们,必须包含头文件 <queue>。
queue 可以用 list 和 deque 实现,默认情况下用 deque 实现。
queue 的定义如下:
priority_queue 可以用 vector 和 deque 实现,默认情况下用 vector 实现。
priority_queue 默认的元素比较器是 less <T>。也就是说,在默认情况下,要放入 priority_queue 的元素必须是能用“<”运算符进行比较的,而且 priority _queue 保证以下条件总是成立:对于队头的元素 x 和任意非队头的元素 y,表达式“x<y”必为 false。
priority_queue 定义如下:
和 set/multiset 不同,priority_queue 是使用“堆排序”技术实现的,其内部并非完全有序,但却能确保最大元素总在队头。因此,priority_queue 特别适用于“不停地在一堆元素中取走最大的元素”这种情况。priority_queue 插入和删除元素的复杂度都是 O(log(n))。虽然用 set/multiset 也能完成此项工作,但是 priority_queue 比它们略快一些。
priority_queue 队头的元素只能被查看或者修改,不能被删除。
priority_queue的用法示例如下。
9.8 9.8 5.4 3.2
3.2 5.4 9.8 9.8
pq2 的排序规则和 pq1 相反,因此元素出队的顺序也相反。
queue
queue 就是“队列”。队列是先进先出的,和排队类似。队头的访问和删除操作只能在队头进行,添加操作只能在队尾进行。不能访问队列中间的元素。queue 可以用 list 和 deque 实现,默认情况下用 deque 实现。
queue 的定义如下:
template < class T, class Cont = deque<T> >
class queue{
...
};
priority_queue
priority_queue 是“优先队列”。它和普通队列的区别在于,优先队列的队头元素总是最大的——即执行 pop 操作时,删除的总是最大的元素;执行 top 操作时,返回的是最大元素的引用。priority_queue 可以用 vector 和 deque 实现,默认情况下用 vector 实现。
priority_queue 默认的元素比较器是 less <T>。也就是说,在默认情况下,要放入 priority_queue 的元素必须是能用“<”运算符进行比较的,而且 priority _queue 保证以下条件总是成立:对于队头的元素 x 和任意非队头的元素 y,表达式“x<y”必为 false。
priority_queue 定义如下:
template < class T, class Container = vector <T>, class Compare = less<T> >
class priority_queue{
...
};
和 set/multiset 不同,priority_queue 是使用“堆排序”技术实现的,其内部并非完全有序,但却能确保最大元素总在队头。因此,priority_queue 特别适用于“不停地在一堆元素中取走最大的元素”这种情况。priority_queue 插入和删除元素的复杂度都是 O(log(n))。虽然用 set/multiset 也能完成此项工作,但是 priority_queue 比它们略快一些。
priority_queue 队头的元素只能被查看或者修改,不能被删除。
priority_queue的用法示例如下。
#include <queue> #include <iostream> using namespace std; int main() { priority_queue<double> pq1; pq1.push(3.2); pq1.push(9.8); pq1.push(9.8); pq1.push(5.4); while(!pq1.empty()) { cout << pq1.top() << " "; pq1.pop(); } //上面输出 9.8 9.8 5.4 3.2 cout << endl; priority_queue<double,vector<double>,greater<double> > pq2; pq2.push(3.2); pq2.push(9.8); pq2.push(9.8); pq2.push(5.4); while(!pq2.empty()) { cout << pq2.top() << " "; pq2.pop(); } //上面输出 3.2 5.4 9.8 9.8 return 0; }程序的输出结果是:
9.8 9.8 5.4 3.2
3.2 5.4 9.8 9.8
pq2 的排序规则和 pq1 相反,因此元素出队的顺序也相反。
所有教程
- socket
- Python基础教程
- C#教程
- MySQL函数
- MySQL
- C语言入门
- C语言专题
- C语言编译器
- C语言编程实例
- GCC编译器
- 数据结构
- C语言项目案例
- C++教程
- OpenCV
- Qt教程
- Unity 3D教程
- UE4
- STL
- Redis
- Android教程
- JavaScript
- PHP
- Mybatis
- Spring Cloud
- Maven
- vi命令
- Spring Boot
- Spring MVC
- Hibernate
- Linux
- Linux命令
- Shell脚本
- Java教程
- 设计模式
- Spring
- Servlet
- Struts2
- Java Swing
- JSP教程
- CSS教程
- TensorFlow
- 区块链
- Go语言教程
- Docker
- 编程笔记
- 资源下载
- 关于我们
- 汇编语言
- 大数据
- 云计算
- VIP视频