如何迭代priority_queue？

Question

我可以使用迭代器（如 vector）遍历 C++ 中的标准 priority_queue 或标准 queue 吗？我不想使用 pop，因为它会导致我的队列出队。

感谢您的帮助

Answer 1

队列有目的地提供有限的接口，其中排除了迭代。但既然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;
}

对于优先级队列的类似答案：不，你不能。但在本例中，默认使用向量。在这两种情况下，您都无法访问底层容器来迭代它们。请参阅此问题以进一步阅读。

Answer 2

#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 3

是的，复制priority_queue并对其进行迭代。

Answer 4

这是不可能的。您必须使用不同的容器，可能是 deque 将为您提供最好的服务。

Answer 5

我在偶然发现你的问题后发现了这一点。有一种非常简单的方法可以通过编写继承自 std::priority_queue 的实现来实现此目的。全部是14行。

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

Answer 6

队列与向量完全不同，并且用于不同的目的。优先级队列只是排序的双端队列，无法直接访问后面。但是，如果您迫切希望对任何方法执行此操作，您可以做的就是弹出顶部/前面的元素，将其添加到列表/数组/向量中，然后将该元素推回到队列中 for(size_t i = 0; q.size();我参加了 Java 数据结构课程，这是考试问题的答案。而且这是我能想到的唯一方法。

Answer 7

其中许多答案依赖于编码/使用许多 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提供迭代器似乎完全不明智，特别是当它是 or 结构的容器类时。

Answer 8

大多数现有答案要么建议使用不同的数据结构，要么执行一系列 O(log n) 操作（n 是优先级队列的大小）。有些人甚至建议复制该结构。

该操作可以相对于元素数量以线性时间执行，前提是：

• 底层容器是向量，并且
• 不需要按排序顺序遍历元素。

如果满足这些条件，则可以使用以下代码：

#include <iostream>
#include <queue>

int main()
{
    using T = int;
    std::priority_queue<T, std::vector<T>, std::less<T>> q;
    
    q.emplace(1); q.emplace(16); q.emplace(5); q.emplace(42); q.emplace(3);
    
    const T* base = &q.top(); // root of the binary heap
    for(size_t i = 0; i<q.size(); i++)
        std::cout << *(base+i)<<" ";
    std::cout << std::endl; // outputs "42 16 5 1 3"

    return 0;
}

这种方法的优点是不更改所使用的数据结构：如果二进制堆适合您的应用程序，则使用多重集是没有意义的。而且它结构紧凑，实现起来很简单，不会改变原始对象，也不需要额外的内存。最后，它的运行时间为O(n)，而不是常见的O(n log n)。

Answer 9

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 10

出于基本目的， std::multiset将为您提供类似的属性，但具有迭代能力：

• 项目已排序，可以定义自定义 Less
• 键可以出现多次
• 快速访问和删除第一个项目

Answer 11

制作副本并迭代 - 由 @lie-ryan 建议

#include <iostream>
#include <queue>

using namespace std;
void make_copy(priority_queue<int, vector<int>> pq, vector<int> &arr)
{
    arr = {}; // if it was not empty , make it :)
    while (!pq.empty())
    {
        arr.push_back(pq.top());
        pq.pop();
    }
}
int main()
{
    priority_queue<int, vector<int>> q;
    q.push(1);
    q.push(2);
    q.push(3);
    vector<int> arr;
    make_copy(q, arr); // this will copy all elements of q to arr :)
    for (auto &x : arr)
    {
        cout << x << " ";
    }
}

Answer 12

我自己也有同样的疑问。我发现要了解优先级队列底层的数据结构非常困难，甚至可能是不可能的。就我而言，这是一个对象向量。

但是，我最终使用了标准模板库堆。它几乎和优先级队列一样简单（它需要两条指令来推送和弹出，而 pq 则需要 1 条指令），否则行为似乎是相同的
和
如果我不修改它，我可以获取底层数据结构。

Answer 13

如果你想以复杂度（logN）的有序方式推送项目。但如果还想按升序迭代元素，您可以使用 set。
集合通常被实现为二叉搜索树。

集合是可迭代的（开始、结束、rbegin、rend 等）

Answer 14

我遇到了同样的问题，我想迭代优先级队列而不出队（因此破坏了我的队列）。我通过将priority_queue指针重新转换为指向向量的指针（因为我的priority_queue使用向量作为其容器）使其对我有用。它是这样的：

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 15

priority_queue 不允许迭代所有成员，大概是因为很容易使队列的优先级排序无效（通过修改您遍历的元素），或者这可能是“不是我的工作”理由。

官方的解决方法是使用 vector 并使用 make_heap、push_heap 和 pop_heap 自行管理优先级代码>.在 @Richard 的回答中，另一个解决方法是使用从 priority_queue 派生的类并访问具有 protected 可见性的底层存储。

Answer 16

你可以这样做 - 砰！请注意，项目在队列中时不一定按“排序”顺序，至少对于容器的直接迭代而言是如此。

#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;
}