C++ STL 优先队列排序不正确

Question

我想要一个 Waypoint* 对象的 vector ，这些对象经过排序，以便距离最短的路点位于队列的顶部。

这是我的比较类:

class WaypointCompare {
    public:
        bool operator()(Waypoint* left, Waypoint* right) const {
            return left->getDistance() < right->getDistance();
        }
};

这是我初始化队列的方式:

std::priority_queue<Waypoint*, std::vector<Waypoint*>, WaypointCompare> queue;

每当我更新航路点的距离时，我的队列似乎没有正确重新排序。就像这个例子一样，距离值最小的 Waypoint 对象不应该在队列的后面(顶部)(索引 10)吗？这是一些队列调试的图像，我已经注意到我认为错误的地方:

我认为这可能与我对 pq 的理解不稳定有关，或者我正在将所有距离初始化为 HUGE_VAL。

Answer 1

Whenever I update the distance of a waypoint, my queue seems to not reorder correctly.

不，不会。如果元素发生变化，队列不会自行重新排序；这样做只会破坏顺序。您需要删除并重新插入任何以影响排序的方式发生变化的元素。