C++ 如何迭代priority_queue？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/4484767/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How to iterate over a priority_queue?
提问by mina70
Can I traverse a standard priority_queueor standard queuein c++ with an iterator (like a vector)? I don't want to use pop because it cause my queue to be dequeued.
我可以使用迭代器（如 a ）遍历C++ 中的标准priority_queue或标准吗？我不想使用 pop，因为它会导致我的队列出队。queuevector
Thanks for any help
谢谢你的帮助
回答by xan
priority_queuedoesn't allow iteration through all the members, presumably because it would be too easy in invalidate the priority ordering of the queue (by modifying the elements you traverse) or maybe it's a "not my job" rationale.
priority_queue不允许遍历所有成员，大概是因为使队列的优先级排序无效（通过修改您遍历的元素）太容易了，或者这可能是“不是我的工作”的理由。
The official work-around is to use a vectorinstead and manage the priority-ness yourself with make_heap, push_heapand pop_heap. Another work-around, in @Richard's answer, is to use a class derived from priority_queueand access the underlying storage which has protectedvisibility.
官方的解决方法是改用 avector并使用make_heap,push_heap和自己管理优先级pop_heap。在@Richard 的回答中，另一个解决方法是使用派生自priority_queue并访问具有protected可见性的底层存储的类。
回答by Richard
You can do it like this - bam! Notice that items are not necessarily in "sorted" order while they are in the queue, at least with regards to a straight-forward iteration of the container.
你可以这样做 - 砰！请注意，项目在队列中时不一定按“排序”顺序排列，至少在容器的直接迭代方面是这样。
#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;
}
回答by moinudin
A queuepurposefully provides a limited interface, which excludes iteration. But since a queueuses a dequeas the underlying container, why not use a dequedirectly?
Aqueue特意提供了一个有限的接口，它排除了迭代。但是既然aqueue使用adeque作为底层容器，为什么不deque直接使用a呢？
#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;
}
Similar answer for a priority queue: no, you cannot. In this case though, a vectoris used by default. In neither case can you access the underlying container to iterate over them. See this questionfor further reading.
优先队列的类似答案：不，你不能。但在这种情况下，vector默认使用a 。在这两种情况下，您都不能访问底层容器来迭代它们。请参阅此问题以进一步阅读。
回答by Lie Ryan
Yes, make a copy of the priority_queue and iterate over that.
是的，复制 priority_queue 并迭代它。
回答by Snooze
#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;
}
回答by Jonathan Henson
I found this after stumbling across your question. There is a very simple way of doing this by writing an implementation inheriting from std::priority_queue. It is all of 14 lines.
我在偶然发现你的问题后发现了这一点。通过编写一个继承自 std::priority_queue 的实现，有一种非常简单的方法可以做到这一点。全是14行。
回答by Bj?rn Pollex
回答by sj755
Queues are totally different from vectors and are used for different purposes. Priority queues are simply sorted deques with no direct access to the back. However, if you desperately want to do this for whatever method, what you can do is pop off the top/front element, add it to a list/array/vector, and then push the element back into your queue for(size_t i = 0; i < q.size(); i++). I took a class in java data structures, and this was the answer to an exam question. Plus it is the only method i can think of.
队列与向量完全不同，用于不同的目的。优先级队列只是排序的双端队列，不能直接访问后面。但是，如果您非常想为任何方法执行此操作，您可以做的是弹出顶部/前端元素，将其添加到列表/数组/向量中，然后将元素推回您的队列 for(size_t i = 0; i < q.size(); i++)。我参加了 Java 数据结构课程，这是一个考试问题的答案。另外，这是我能想到的唯一方法。
回答by HymanCColeman
Many of these answers rely on coding/using many of C++ arcane features. That's ok, fun and funds expensive programmers. A direct solution that is quick, cheap to program but more expensive to run, is:
其中许多答案依赖于编码/使用许多 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;
By the way, it seems perfectly non-sensible to NOT provide an iterator for a priority_queue, especially when it is a container class for a or structure.
顺便说一句，不为priority_queue 提供迭代器似乎是完全不明智的，尤其是当它是一个或结构的容器类时。
回答by AndiDog
For basic purposes, a std::multisetwill give you similar properties but with the ability to iterate:
出于基本目的， astd::multiset将为您提供类似的属性，但具有迭代能力：
- Items sorted, custom
Lesscan be defined - Keys can occur multiple times
- Quick to access and remove first item
- 项目排序，自定义
Less可以定义 - 键可以出现多次
- 快速访问和删除第一项
