我想在我的优先队列中找到一个节点,但我没有找到解决方案:( 如果你有解决方案,我很感兴趣。
谢谢帮助。
我想在我的优先队列中找到一个节点,但我没有找到解决方案:( 如果你有解决方案,我很感兴趣。
谢谢帮助。
std::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;
}
};
c
是底层容器。它是作为模板参数传递的类型 Container
,并在 C++ 语言标准中指定,因此保证始终存在。 - Captain Obvlious如果您不关心性能,可以声明一个iterator
来遍历priority_queue
的容器。但在C++中,底层容器被声明为protected
,不能直接访问。
我得到容器迭代器的一种解决方案是声明一个继承自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;
Q.push(4);
Q.push(3);
Q.push(35);
for(vector<int>::iterator p=Q.begin(); p!=Q.end(); p++)
cout << *p << endl;
为了提高效率,例如通过某些关键字查找数据,您可以使用 数据指针
。
假设类 Data
持有您的每个数据项。 Data.key
是搜索的关键字,Data.value
是在 priority_queue
中的优先级。
struct Data{
VALUE_TYPE value;
KEY_TYPE key;
...
...
};
将所有数据存储在单独的集合中,例如数组或链表。
Data data[MAX];
定义一个新的结构体,该结构体存储某个data[i]
的指针。
struct Node{
Data* data;
Node(Data* ptr){data=ptr;}
};
priority_queue
和另一个支持搜索的数据结构,例如 binary search tree
、hash
。这里我使用了 multimap
。Node
的 priority_queue
和一个 multimap
。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]));
}
你可以使用 multimap d
按键获取数据的 指针
。通过使用 priority_queue q
,还可以满足对优先级队列的需求。
以上所有内容都是使用指针完成的。
map
和priority_queue
,模板参数默认为std::less
。 - Captain Obvliouspriority_queue
和 multimap
存储数据的 指针
。因此,我需要编写自己的比较函数。 - konjac
priority_queue
只有两个操作:按给定优先级插入元素和检索具有最高优先级的元素。如果你需要其他操作,那么priority_queue
不是正确的容器选择。 - syamint priority = pq.find() - pg.begin();
- Captain Obvlious