C++ STL priority_queue优先队列

C++ priority_queue

priority_queue

• C++ priority_queue
• • 创建priority_queue
  • • 构造函数
    • operator=
  • 元素访问
  • • top
  • 容量
  • • empty
    • size
  • 修改器
  • • push
    • emplace
    • pop
    • swap
  • 非成员函数
  • • std::swap(std::priority_queue)
  • 示例

类模板：

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

• 定义于头文件 <queue>
• priority_queue 是容器适配器，它提供常数时间的（默认）最大元素查找，对数代价的插入与释出。
• 可用用户提供的 Compare 更改顺序，例如，用 std::greater 将导致最小元素作为 top() 出现
• 用 priority_queue 工作类似管理某些随机访问容器中的堆，优势是不可能突然把堆非法化。

创建priority_queue

构造函数

用法：

std::priority_queue<int> c1;
 
    std::priority_queue<int> c2(c1);
 
    std::deque<int> deq {3, 1, 4, 1, 5};
    std::priority_queue<int> c3(deq);
           

operator=

• 赋值给容器适配器

定义：

priority_queue& operator=( const priority_queue& other );
priority_queue& operator=( priority_queue&& other );
           

用法：

priority_queue<int> s1;
priority_queue<int> s2;

s1 = s2;
s1 = std::move(s2);
           

元素访问

top

• 访问栈顶元素

定义：

reference top();
const_reference top() const;
           

用法：

std::priority_queue<int> s;
    s.push( 2 );
    s.push( 6 );
    s.push( 51 );

	std::cout << s.top() << std::endl;		// 51
           

容量

empty

• 检查底层的容器是否为空

• 返回值

  若底层容器为空则为 true ，否则为 false 。

size

• 返回容纳的元素数

修改器

push

• 向栈顶插入元素

// 等效地调用 c.push_back(value)
void push( const value_type& value );

// 等效地调用 c.push_back(std::move(value))
void push( value_type&& value );
           

emplace

• 于顶原位构造元素

template< class... Args >
void emplace( Args&&... args );
           

pop

• 删除栈顶元素
• 无返回值

swap

• 交换内容

非成员函数

std::swap(std::priority_queue)

• 特化 std::swap 算法

template< class T, class Container >
void swap( std::priority_queue<T,Container>& lhs,
           std::priority_queue<T,Container>& rhs );
           

示例

#include <functional>
#include <queue>
#include <vector>
#include <iostream>
 
template<typename T> void print_queue(T& q) {
    while(!q.empty()) {
        std::cout << q.top() << " ";
        q.pop();
    }
    std::cout << '\n';
}
 
int main() {
    std::priority_queue<int> q;
 
    for(int n : {1,8,5,6,3,4,0,9,7,2})
        q.push(n);
 
    print_queue(q);
 
    std::priority_queue<int, std::vector<int>, std::greater<int> > q2;
 
    for(int n : {1,8,5,6,3,4,0,9,7,2})
        q2.push(n);
 
    print_queue(q2);
 
    // 用 lambda 比较元素。
    auto cmp = [](int left, int right) { return (left ^ 1) < (right ^ 1); };
    std::priority_queue<int, std::vector<int>, decltype(cmp)> q3(cmp);
 
    for(int n : {1,8,5,6,3,4,0,9,7,2})
        q3.push(n);
 
    print_queue(q3);
 
}

// 输出：
// 9 8 7 6 5 4 3 2 1 0 
// 0 1 2 3 4 5 6 7 8 9 
// 8 9 6 7 4 5 2 3 0 1