C++效率掌握之STL库：优先级队列priority

admin管理员组

文章数量:1443078

C++效率掌握之STL库：优先级队列priority

本篇是 STL 库专题之 priority_queue 和 deque，书接上文

1.priority_queue

priority_queue 的主要特征可总结为：

1. 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的，简单来说就是取出元素的顺序默认是从大到小的
2. 此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)
3. 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue 提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部
4. 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作：
5. empty()：检测容器是否为空
6. size()：返回容器中有效元素个数
7. front()：返回容器中第一个元素的引用
8. push_back()：在容器尾部插入元素
9. pop_back()：删除容器尾部元素
10. 标准容器类 vector 和 deque 满足这些需求。默认情况下，如果没有为特定的priority_queue 类实例化指定容器类，则使用 vector
11. 需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数 make_heap、push_heap 和 pop_heap 来自动完成此操作

1.1 priority_queue函数

优先级队列默认使用 vector 作为其底层存储数据的容器，在 vector 上又使用了堆算法将vector 中元素构造成堆的结构，因此 priority_queue 就是堆，所有需要用到堆的位置，都可以考虑使用 priority_queue

本文标签： C效率掌握之STL库优先级队列priority