C++ 如何在优先级队列中找到值？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/16749723/
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 I can find value in priority queue?
提问by Marc Lamberti
I would like to find a node in my priority queue but I did not find a solution :( If you have a solution, I'm interested.
我想在我的优先级队列中找到一个节点，但我没有找到解决方案 :( 如果您有解决方案，我很感兴趣。
Thx for help.
谢谢你的帮助。
回答by Captain Obvlious
If you really need to search through a std::priority_queueand want to do it efficiently you can derive a new class and add a findmember function. Since you are not adding any additional state you do not have to worry about slicing or other issues since std::priority_queueis not polymorphic.
如果您确实需要搜索 astd::priority_queue并希望有效地进行搜索，您可以派生一个新类并添加一个find成员函数。由于您没有添加任何其他状态，因此您不必担心切片或其他问题，因为std::priority_queue它不是多态的。
#include <queue>
template<
class T,
class Container = std::vector<T>,
class Compare = std::less<typename Container::value_type>
> class MyQueue : public std::priority_queue<T, Container, Compare>
{
public:
typedef typename
std::priority_queue<
T,
Container,
Compare>::container_type::const_iterator const_iterator;
const_iterator find(const T&val) const
{
auto first = this->c.cbegin();
auto last = this->c.cend();
while (first!=last) {
if (*first==val) return first;
++first;
}
return last;
}
};
回答by konjac
If you do not care about the performance, you can declare an iteratorto traverse the priority_queue's container. But in C++, the underlying container is been declared as protected, and can not be accessed directly.
如果不关心性能，可以声明一个iterator来遍历priority_queue的容器。但是在 C++ 中，底层容器被声明为protected，并且不能直接访问。
One of my solution to get the iterator of the container is declaring a new class inheriting from std::priority_queue.
我获取容器迭代器的解决方案之一是声明一个从std::priority_queue.
typedef int Val_TYPE;
typedef vector<Val_TYPE> Container_TYPE;
typedef priority_queue<Val_TYPE, Container_TYPE> pri_queue;
class Queue: public pri_queue{
public:
Container_TYPE::iterator begin(){
return pri_queue::c.begin();
}
Container_TYPE::iterator end(){
return pri_queue::c.end();
}
}Q;
Then you can get the iterator of the container.
然后就可以得到容器的迭代器了。
Q.push(4);
Q.push(3);
Q.push(35);
for(vector<int>::iterator p=Q.begin(); p!=Q.end(); p++)
cout << *p << endl;
In order to be more efficient, for example looking for data by certain keys, you can use pointers to data.
为了更高效，例如通过某些键查找数据，您可以使用pointers to data.
Suppose the class Dataholds each item of your data. Data.keyis the key for search and Data.valueis the priority in priority_queue.
假设该类Data包含数据的每一项。Data.key是搜索的键，Data.value是 中的优先级priority_queue。
struct Data{
VALUE_TYPE value;
KEY_TYPE key;
...
...
};
Store all your data in a separate collection, for example an array or an link list.
将所有数据存储在单独的集合中，例如数组或链接列表。
Data data[MAX];
Define a new struct which stores the pointer for certain one data[i]
定义一个新的结构来存储某个指针的指针 data[i]
struct Node{
Data* data;
Node(Data* ptr){data=ptr;}
};
Use a priority_queueand another data structure support search i.e. binary search tree, hash. Here I use multimap.
使用一个priority_queue和另一个数据结构支持搜索即binary search tree, hash. 我在这里使用multimap.
Maintain a priority_queueof Nodeand a multimapof Nodeat the same time.
同时维护一个priority_queueofNode和一个multimapof Node。
struct cmp1{
bool operator(Node a, Node b){ return a.data->value < b.data->value; }
};
struct cmp2{
bool operator(Node a, Node b){ return a.data->key < b.data->key; }
};
priority_queue<Node, vector<Node>, cmp1> q;
multimap <KEY_TYPE, Node, cmp2> d;
for(int i = 0; i < n; ++i){
q.push(Node(&a[i]));
d.insert(a[i].key, Node(&a[i]));
}
Then you can get data's pointerby key using multimap d. The need for priority_queue is also satisfied by using priority_queue q.
然后您可以pointer使用 multimap 按键获取数据d。使用 priority_queue 也可以满足对 priority_queue 的需求q。
All of the above is just using pointers.
以上所有都只是使用指针。
