我想制作一个对象的优先级队列,特别是一对(int,int)。队列应包含分配有优先级的对。
#include <iostream>
#include <queue>
using namespace std;
class saPair{
public:
int s;
int a;
double priority;
saPair(int s, int a, double priority){
this->s = s;
this->a = a;
this->priority = priority;
}
};
// the priority menmber variable determines the priority in the queue
// highest priority pair of (int, int) stays on the top
bool operator< (const saPair& x, const saPair& y) {
return x.priority < y.priority;
}
int main()
{
priority_queue<saPair> pq;
pq.push(saPair(0,0, 0.3));
pq.push(saPair(0,1, 0.1));
pq.push(saPair(0,3, 0.5));
pq.push(saPair(0,3, 5));
cout << pq.top().a << endl;
pq.pop();
cout << pq.top().a << endl;
pq.pop();
cout << pq.top().a << endl;
}
如您所见,对 (0,3) 具有最高优先级,因此它位于顶部。但是我的实现的问题是,如果我再次添加具有不同优先级的 (0,3) 对,我会向队列中添加一个新元素,而不是替换已经存在的 (0,3) 对的优先级。
我觉得我为我的需求选择了错误的数据结构。我尝试通过为 < 运算符定义一个具有操作重载的新 saPair(int, int) 类来获取键值。但即使那样似乎也不能正常工作..
关于如何进行的任何建议?或修改
最佳答案
您似乎需要对您的容器进行多键访问:您希望按优先级对其进行排序(或者至少有一个按优先级的二进制堆,如 priority_queue
),并且您希望对值是唯一的,所以你也需要一对值(value)查找。
在标准库中没有默认的解决方案,但制作你自己的应该不会太难。
我建议简单地存储一个额外的 std::set<saPair>
检查该对是否已经在您的容器中。这样你就可以保留你的 priority_queue
事情就是这样,实现起来也不会费太多功夫。
不要忘记添加 operator<
至 saPair
虽然(或将其替换为 std::pair
),否则 std::set
将无法使用它。
另一种选择是手动检查您的 priority_queue
每次添加一对。虽然渐近地比 std::set
差解决方案,这在实践中可能会更快,并且会为您节省一些空间。但是,我认为如果使用 std::set
,代码会更清晰。 .
还有一个解决方案是 boost::multi_index
,这使您可以轻松构建所需的任何多索引容器。但是我认为它不会让您利用不需要按优先级进行强排序这一事实,因此它不会像 priority_queue
这样的线性连续布局。
关于C++使用对象的优先级队列,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43176305/