如何告诉 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 函子的行为会导致您的外部副本的顺序与存储在 priority_queue 内的 Compare 副本的顺序不同。
• 您不完全理解这些警告的含义。

您始终可以编写自己的容器适配器来包装堆算法。 priority_queue只不过是make/push/pop_heap的一个简单包装器。

Answer 2

如果您需要保留有序集合，您可以考虑以下解决方案：使用 std::set 并更新值，删除该项目，更新其值并将其放回集合中。这将为您提供更新一项的 O(log n) 复杂度，这是在通常的堆结构中所能做到的最好的复杂度（假设您可以通过 sift-up-sift-down 过程访问其内部以进行质量）。
std::set 的唯一缺点是初始化包含 n 个项目的集合的时间。 （O(n log n) 而不是 O(n)）。

Answer 3

基于http://www.sgi.com/tech/stl/priority_queue.html 看起来没有办法做到这一点，无需清空并重新插入。

如果您愿意放弃priority_queue（但仍然想要堆），那么您可以使用向量以及make_heap、push_heap 和 pop_heap。请参阅 priority_queue 页面中的注释部分。

Answer 4

这是一个老问题，但当我想自己做这个时，我对任何答案都不完全满意。不需要任何黑客攻击。 std::priority_queue 包含合法且惯用地执行此操作的所有机制。

std::priority_queue 有两个非常有用的数据成员：c（底层容器）和comp（比较谓词）。

同样有用的是，该标准要求 Container 模板类型必须是 SequenceContainer 的模型，而其迭代器是 RandomAccessIterator 的模型。

这很有用，因为 std::make_heap 的 Iter 参数类型具有相同的 RandomAccessIterator 模型要求。

这是一种冗长的说法，std::priority_queue 是堆的包装器，因此 std::make_heap(std::begin(c), std::end(c) ), comp) 必须是有效的表达式。

“坏”消息是 c 和 comp 受到保护。这实际上是个好消息，原因有两个：

1. 您不能意外破坏堆。

2. 如果您从 std::priority_queue 派生，您可以有意修改堆。

因此，诀窍是从 std::priority_queue 派生优先级队列，在成员函数中，以您喜欢的任何方式改变内部堆 c，然后调用 std ::make_heap(std::begin(c), std::end(c), comp); 将其转回有效堆。

从 STL 容器继承通常不是一个坏主意

嗯，是的，但是……

对于年轻人和/或粗心的人来说，这可能是一个坏主意，原因有两个。缺乏多态析构函数和切片风险。

1. 多态析构函数

通过指向其基类的指针来拥有 std 容器实际上没有合理的用例。集装箱重量轻（当里面没有任何东西时）并且移动成本低廉。您也许能够想到用例，但我可以保证无论您打算做什么，都可以通过将容器封装在另一个堆分配的对象中来更好地完成。在设计良好的代码中，这永远不应该成为一个问题。无论如何，从 priority_queue 模板类私有继承可以消除这种风险。

2. 切片

当然，当我们传递继承的对象时，存在切片的风险。这里的答案是从priority_queue基类私有继承，然后在派生类中使用using来仅导出我们希望共享的基类接口部分。

下面的示例已更新以显示这一点。

下面是一个来自真实项目的例子。

要求：
保留必须通知客户端更改的主题队列。按该主题最早收到通知的时间戳对队列进行排序。不允许重复的主题名称。

这是一个工作演示：

#include <queue>
#include <string>
#include <chrono>
#include <cassert>
#include <iostream>

using topic_type = std::string;
using timestamp_clock = std::chrono::system_clock;
using timestamp_type = timestamp_clock::time_point;

struct notification {
    topic_type topic;
    timestamp_type timestamp;
};

bool topic_equals(const notification& l, const topic_type& r) {
    return l.topic == r;
}
bool topic_equals(const topic_type& l, const notification& r) {
    return l == r.topic;
}

bool age_after(const notification& l , const notification& r) {
    return l.timestamp > r.timestamp;
}

bool age_after(const notification& l , const timestamp_type& r) {
    return l.timestamp > r;
}

bool age_after(const timestamp_type& l , const notification& r) {
    return l > r.timestamp;
}

struct greater_age
{
    template<class T, class U>
    bool operator()(const T& l, const U& r) const {
        return age_after(l, r);
    }
};

template<class T>
struct pending_queue_traits;

template<>
struct pending_queue_traits<notification>
{
    using container_type = std::vector<notification>;
    using predicate_type = greater_age;
    using type = std::priority_queue<notification, container_type, predicate_type>;
};

class pending_notification_queue
: private pending_queue_traits<notification>::type
{
    using traits_type = pending_queue_traits<notification>;
    using base_class = traits_type::type;

public:


    // export the constructor
    using base_class::base_class;

    // and any other members our clients will need
    using base_class::top;
    using base_class::pop;
    using base_class::size;

    bool conditional_add(topic_type topic, timestamp_type timestamp = timestamp_clock::now())
    {
        auto same_topic = [&topic](auto& x) { return topic_equals(topic, x); };
        auto i = std::find_if(std::begin(c), std::end(c), same_topic);
        if (i == std::end(c)) {
            this->push(notification{std::move(topic), std::move(timestamp)});
            return true;
        }
        else {
            if (timestamp < i->timestamp) {
                i->timestamp = std::move(timestamp);
                reorder();
                return true;
            }
        }
        return false;
    }

private:
    void reorder() {
        std::make_heap(std::begin(c), std::end(c), comp);
    }
};

// attempt to steal only the base class...
void try_to_slice(pending_queue_traits<notification>::type naughty_slice)
{
    // danger lurks here
}
int main()
{
    using namespace std::literals;

    auto pn = pending_notification_queue();

    auto now = timestamp_clock::now();
    pn.conditional_add("bar.baz", now);
    pn.conditional_add("foo.bar", now + 5ms);
    pn.conditional_add("foo.bar", now + 10ms);
    pn.conditional_add("foo.bar", now - 10ms);

    // assert that there are only 2 notifications
    assert(pn.size() == 2);
    assert(pn.top().topic == "foo.bar");
    pn.pop();
    assert(pn.top().topic == "bar.baz");
    pn.pop();

    // try to slice the container. these expressions won't compile.
//    try_to_slice(pn);
//    try_to_slice(std::move(pn));

}

Answer 5

stl 的容器不提供尽可能快的可更新优先级队列。

@Richard Hodges：make_heap 的复杂度为 O(n)，并且 push_heap 函数不会告诉您所提供的元素存储在哪里，从而可以快速更新单个元素不可能（你需要 O(n) 才能找到它）。

我实现了一个高性能的可更新优先级队列（更新成本为 O(log n)，是使用 std::set 的两倍）并使其可用 在 github 上。

这是您通常使用它的方式：

better_priority_queue::updatable_priority_queue<int,int> pQ;
pQ.push(0, 30);   // or pQ.set(0, 30)
pQ.push(1, 20);
pQ.push(2, 10);

pQ.update(2, 25); // or pQ.set(2, 25)

while(!pQ.empty())
    std::cout << pQ.pop_value().key << ' ';

// Outputs: 0 2 1