// <queue>
template < class T, class Container = vector<T>,
    class Compare = less<typename Container::value_type> > class priority_queue;

优先级队列(Priority queue)是一个容器适配器(Container adaptor)类型,被特别设计使其第一个元素总是容器所包含的元素中按特定的严格弱序排序规则排序后最大的一个。

 

  • T

    容器所包含的元素的类型。

    在类模板内部,使用其别名为 value_type 的成员类型。

    Container

    底层的用于存储元素的容器的类型。

    Compare

    一个二元谓词,以两个元素为参数返回一个 bool 值。

    可以是函数指针(Function pointer)类型或函数对象(Function object)类型。

  • priority_queue 的定义使得它类似一个堆(Heap),该堆只能获得它的最大堆元素(在 priority_queue 中即为队列头)。

    priority_queue 通常被实现为容器适配器,即使用一个特定容器类的封装对象作为它的底层容器。priority_queue 提供了一系列成员函数用于操作它的元素,只能从容器“后面”提取(Pop)元素,该元素也可认为是 priority_queue 的“顶部(Top)”。

    用来实现优先级队列的底层容器必须满足顺序容器的所有必要条件。同时,它还必须提供以下语义的成员函数:

    • front()
    • push_back()​
    • pop_back()

    为了使内部始终保持堆结构,底层容器必须支持随机访问迭代器。这样,容器适配器内部就可以在适当的时候自动调用算法函数 std::make_heapstd::push_heapstd::pop_heap

    满足上述条件的标准容器有 std::vector 及 std::deque,如果未特别指定 priority_queue 的底层容器,标准容器 std::vector 将被使用。

    Any sequence container with random access iterator and supporting operations front(), push_back() and pop_back() can be used to instantiate priority_queue. In particular, vector and deque can be used.

    C++编程语言国际标准:ISO/IEC 14882:2011

  • 成员类型 定义
    value_type 第一个模板参数 T
    container_type 第二个模板参数 Container
    size_type Container::size_type
    reference Container::reference
    const_reference Container::const_reference
  • (constructor) 创建 priority_queue
    (destructor) 释放 priority_queue
    operator= 赋值操作

    Element access:

    top 访问顶部元素

    Capacity:

    empty 判断是否为空
    size 返回有效元素个数

    Modifiers:

    push 在容器顶部插入元素
    pop 移除容器顶部的元素
    emplace C++11 在容器顶部放置插入元素
    swap 交换容器的内容
  • std::swap 交换两个优先级队列的内容
  • std::uses_allocator<std::priority_queue>  C++11 特例化 std::uses_allocator 类型特征
  • 综合 1

    下面这个例子简单地介绍了 priority_queue 的常用使用方法:

    #include <iostream>
    #include <queue>
    #include <functional>
    
    namespace ClassFoo {
    using namespace std;
    
    void PriorityQueueExample1() {
        priority_queue<int,vector<int>,greater<int> > foo1;
        priority_queue<int,vector<int> >foo2;
        int a[]={1,3,4,2,5,0,6};
        for(int i=0;i<7;i++)
        {
            foo1.push(a[i]);
            foo2.push(a[i]);
        }
        cout<<"foo1:";
        while(!foo1.empty())
        {
            cout<<foo1.top()<<" ";
            foo1.pop();
        }
        cout << endl;
        cout << "foo2:";
        while(!foo2.empty())
        {
            cout<<foo2.top()<<" ";
            foo2.pop();
        }
        cout << endl;
    }
    }
    int main()
    {
        ClassFoo::PriorityQueueExample1();
        return 0;
    }

    输出

    foo1:0 1 2 3 4 5 6 
    foo2:6 5 4 3 2 1 0