如何遍歷priority_queue？

Question

我可以遍歷一個標準priority_queue或標準queue用C++與迭代器（如vector）？我不想使用pop，因爲它導致我的隊列出隊。

感謝您的任何幫助

Answer 1

這是不可能的。你將不得不使用不同的容器，可能deque會爲你提供最好的服務。

Answer 2

A queue有意提供了一個有限的接口，它不包括迭代。但由於queue使用deque作爲基礎容器，爲什麼不直接使用deque？

#include <iostream> 
#include <queue> 
using namespace std; 

int main() { 
    deque<int> q; 
    q.push_back(1); 
    q.push_back(2); 
    q.push_back(3); 
    for(deque<int>::iterator it = q.begin(); it != q.end(); ++it) 
    cout << *it << endl; 
} 

優先級隊列的相似問題：不，你不能。在這種情況下，默認情況下使用vector。在任何情況下，您都不能訪問底層容器來遍歷它們。請參閱this question進一步閱讀。

Answer 3

是的，複製一個priority_queue並迭代它。

Answer 4

隊列與矢量完全不同，用於不同的目的。優先級隊列是簡單排序的deques，沒有直接訪問後端。然而，如果你拼命想爲任何方法執行此操作，可以執行的操作是從頂部/前部元素彈出，將其添加到列表/數組/矢量中，然後將元素重新插入到隊列中（size_t i = 0; i < q.size（）; i ++）。我在java數據結構中學習了一門課，這是考試問題的答案。另外它是我能想到的唯一方法。

Answer 5

你可以這樣做 - 巴姆！請注意，項目在隊列中時不一定處於「排序」順序，至少在容器的直接迭代方面。

#include <queue> 
#include <cstdlib> 
#include <iostream> 
using namespace std; 

template <class T, class S, class C> 
S& Container(priority_queue<T, S, C>& q) { 
    struct HackedQueue : private priority_queue<T, S, C> { 
     static S& Container(priority_queue<T, S, C>& q) { 
      return q.*&HackedQueue::c; 
     } 
    }; 
    return HackedQueue::Container(q); 
} 

int main() 
{ 
    priority_queue<int> pq; 
    vector<int> &tasks = Container(pq); 

    cout<<"Putting numbers into the queue"<<endl; 
    for(int i=0;i<20;i++){ 
     int temp=rand(); 
     cout<<temp<<endl; 
     pq.push(temp); 
    } 

    cout<<endl<<"Reading numbers in the queue"<<endl; 
    for(vector<int>::iterator i=tasks.begin();i!=tasks.end();i++) 
     cout<<*i<<endl; 

    cout<<endl<<"Taking numbers out of the queue"<<endl; 
    while(!pq.empty()){ 
     int temp=pq.top(); 
     pq.pop(); 
     cout<<temp<<endl; 
    } 

    return 0; 
} 

Answer 6

我有同樣的問題，我想迭代優先級隊列沒有出隊（因此摧毀我的隊列）。我通過將我的priority_queue指針重新指向一個指向矢量的指針（我的priority_queue使用vector作爲其容器）來爲我工作。下面是它的樣子：

class PriorityQueue { 
    private: 
    class Element { 
    int x; 
    //Other fields 
    ... 
    .. 
    //Comparator function 
    bool operator()(const Element* e1, const Element* e2) const { 
     // Smallest deadline value has highest priority. 
     return e1->x > e2->x; 
    } 
    }; 
    // Lock to make sure no other thread/function is modifying the queue 
    // Ofcourse we can do our operation w/o lock. if we are sure what is happening in other functions 
    pthread_mutex_t lock; 
    std::priority_queue<Element*, std::vector<Element*>, Element> pq; 

    public: 
    PriorityQueue(); 
    ~PriorityQueue(); 
    //print the all the elements of the queue 
    void print_queue_elements() { 
     std::vector<PriorityQueue::Element*> *queue_vector; 
     //Acquire the lock 
     pthread_mutex_lock(&lock); 
     //recast the priority queue to vector 
     queue_vector = reinterpret_cast<std::vector<PriorityQueue::Element*> *>(&pq); 
     for(std::vector<PriorityQueue::Element*>::iterator it = (*queue_vector).begin(); it != (*queue_vector).end(); it++) { 
      //Assuming Element class has string function 
      printf("My Element %s", (*it)->string); 
      //other processing with queue elements 
     } 
     //Release the lock 
     pthread_mutex_unlock(&lock);  

    } 
    //other functions possibly modifying the priority queue 
    ... 
    .. 
    . 
}; 

現在因爲我使用的是reinterpret_cast，所以人們可以爭論類型安全。但在這種情況下，我確信所有其他訪問/更改隊列的函數（所有這些都是安全的）..我覺得這比將整個隊列的內容複製到其他容器更好。

我實際上期待static_cast工作..因爲priority_queue是容器上的適配器（在我們的例子中是向量），但它沒有，我不得不使用reinterpret_cast。

Answer 7

我發現這個後，你的問題磕磕絆絆。通過編寫一個從std :: priority_queue繼承的實現有一個非常簡單的方法。這是14條線。

http://www.linuxtopia.org/online_books/programming_books/c++_practical_programming/c++_practical_programming_189.html

Answer 8

priority_queue不允許迭代通過所有成員，大概是因爲這將是無效太容易了隊列的優先級排序（通過修改你穿越元素）或也許這是一個「不是我的工作「的基本原理。

官方的解決辦法是使用vector，而不是和管理優先內斯自己與make_heap，push_heap和pop_heap。在理查德的回答中，另一個解決方法是使用來自priority_queue的類，並訪問具有protected可見性的基礎存儲。

Answer 9

我自己也有同樣的問題。我發現到達優先級隊列底層的數據結構是非常困難的，也許是不可能的。在我的情況下，這是一個對象的矢量。

但是，我結束了使用標準模板庫堆。它幾乎與優先級隊列一樣簡單（它需要兩條指令來推送和彈出，而對於pq則爲1），否則行爲似乎是相同的 和 如果我不能獲取底層數據結構修改它。

Answer 10

#include <queue> 
#include <iostream> 

int main() { 
    std::priority_queue<int> pq; 

    pq.push_back(1); 
    pq.push_back(2); 
    pq.push_back(3); 

    std::priority_queue<int> temp = pq; 

    while (!temp.empty()) { 
     std::cout << temp.top() << std::endl; 
     temp.pop(); 
    } 

    return 0; 
} 

Answer 11

C++ priority_queue沒有提供一個.begin（）指針（就像向量一樣），您可以使用它來遍歷它。

如果您想遍歷優先級隊列以搜索它是否包含值，那麼可以創建包裝優先級隊列並使用散列集來跟蹤隊列中的內容。

class MyPriorityQueue { 

    MyPriorityQueue() {} 

    void push(int item) { 
    if (!contains(item)){ 
     pq_.push(item); 
     set_.emplace(item); 
    } 
    } 
    void pop() { 
    if (!empty()) { 
     int top = pq_.top(); 
     set_.erase(top); 
     pq_.pop(); 
    } 
    } 
    int top() { return pq_.top(); } 
    bool contains(int item) { return set_.find(item) != set_.end(); } 
    bool empty() const { return set_.empty(); } 

private: 
    std::priority_queue<int> pq_; 
    std::unordered_set<int> set_; 
}; 

Answer 12

許多這些答案依賴於編碼/使用許多C++的神祕功能。沒關係，有趣並且資助昂貴的程序員。一個直接的解決方案，快速，廉價的計劃，但更昂貴的運行，是：

// 
// Only use this routine when developing code, NOT for production use!! 
// 
// Note. _pq is in private for a class that uses the priority queue 
// and listQueue is a public method in that same class. 
// 
void listQueue() { 

    // allocate pointer to a NEW container 
    priority_queue<int>* new_pq = new priority_queue<int>; 

    while (!_pq->empty()) { 

     int el = _pq->top(); 

     cout << "(" << el << ")" << endl; 

     new_pq->push(el); 

     _pq->pop(); 

    } // end while; 

    // remove container storage 
    delete(_pq); 

    // viola, new container same as the old 
    _pq = new_pq; 

} // end of listQueue; 

順便說一句，它似乎完全不理智的不是一個priority_queue提供一個迭代器，特別是當它是一個容器類或結構的類。