c++ - 如何告诉 std::priority_queue 刷新其排序？

Question

我有一个指向 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;
}

Answer 1

这有点骇人听闻，但没有任何违法之处，它可以完成工作。

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 的简单包装.