我有一个指向 struct city
的指针的优先级队列。我在优先级队列之外修改了这些指针指向的对象,并想告诉优先级队列根据新值“重新排序”自己。
我该怎么办?
例子:
#include <iostream>
#include <queue>
using namespace std;
struct city {
int data;
city *previous;
};
struct Compare {
bool operator() ( city *lhs, city *rhs )
{
return ( ( lhs -> data ) >= ( rhs -> data ) );
}
};
typedef priority_queue< city *, vector< city * >, Compare > pqueue;
int main()
{
pqueue cities;
city *city1 = new city;
city1 -> data = 5;
city1 -> previous = NULL;
cities.push( city1 );
city *city2 = new city;
city2 -> data = 3;
city2 -> previous = NULL;
cities.push( city2 );
city1 -> data = 2;
// Now how do I tell my priority_queue to reorder itself so that city1 is at the top now?
cout << ( cities.top() -> data ) << "\n";
// 3 is printed :(
return 0;
}
最佳答案
这有点骇人听闻,但没有任何违法之处,它可以完成工作。
std::make_heap(const_cast<city**>(&cities.top()),
const_cast<city**>(&cities.top()) + cities.size(),
Compare());
更新:
如果出现以下情况,请勿使用此 hack:
- 底层容器不是
vector
. Compare
仿函数的行为会导致您的外部拷贝与Compare
的拷贝不同的顺序。存储在priority_queue
中.- 您并不完全理解这些警告的含义。
您始终可以编写自己的容器适配器来包装堆算法。 priority_queue
只不过是对 make/push/pop_heap
的简单包装.
关于c++ - 如何告诉 std::priority_queue 刷新其排序?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5810190/