如何告诉std :: priority_queue刷新其顺序？ [英] How to tell a std::priority_queue to refresh its ordering?

问题描述

我有一个指向结构城市的指针的优先级队列。我修改了这些指针指向的优先级队列之外的对象，并希望告诉优先级队列根据新值对自身进行重新排序。

I have a priority queue of pointers to a struct city. I modify the objects pointed by these pointers outside the priority queue, and want to tell the priority queue to "reorder" itself according to the new values.

我该怎么办？

示例：

#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;
}

推荐答案

这有点骇人听闻，但是没有任何违法行为，并且可以完成工作。

This is a bit hackish, but nothing illegal about it, and it gets the job done.

std::make_heap(const_cast<city**>(&cities.top()),
               const_cast<city**>(&cities.top()) + cities.size(),
               Compare());

更新：

在以下情况下请勿使用此技巧：

Do not use this hack if:

• 基础容器不是 vector 。


• 比较函子具有以下行为：导致您的外部副本与存储在 priority_queue 中的比较的顺序不同。


• 您不完全理解这些警告的含义。

• The underlying container is not vector.
• The Compare functor has behavior that would cause your external copy to order differently than the copy of Compare stored inside the priority_queue.
• You don't fully understand what these warnings mean.

您始终可以编写自己的容器适配器来包装堆 priority_queue 不是ng，但围绕 make / push / pop_heap 进行简单包装。

You can always write your own container adaptor which wraps the heap algorithms. priority_queue is nothing but a simple wrapper around make/push/pop_heap.

这篇关于如何告诉std :: priority_queue刷新其顺序？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！