如何遍历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提供一个迭代器，特别是当它是一个容器类或结构的类。