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