如何强制重组一个priority_queue？

Question

我有一个 priority_queue，其中包含一个带有一些对象的 vector。

std::priority_queue<std::shared_ptr<Foo>, std::vector<std::shared_ptr<Foo>>, foo_less> foo_queue;

它有一个 foo_queue 函数，可以排序 priority_queue。

现在，在 priority_queue 之外，我想更改一些必须影响 priority_queue 排序的对象值。

我的问题是：

我如何设置某种“刷新”来触发 priority_queue 到运行 foo_queue() 以便保持它一直在订购？

Answer 1

使用标准堆算法和一个向量。当您想要更改键时，从中找到并删除该值底层向量并在向量上调用 make_heap。修改密钥然后把它推回堆上。所以成本是向量的线性搜索找到值并调用 make_heap （我认为也是线性的）。

#include <iostream>
#include <vector>
#include <algorithm>

template <class T, class Container = std::vector<T>,
          class Compare = std::less<T> >
class my_priority_queue {
protected:
    Container c;
    Compare comp;
public:
    explicit my_priority_queue(const Container& c_  = Container(),
                            const Compare& comp_ = Compare())
        : c(c_), comp(comp_)
    {
        std::make_heap(c.begin(), c.end(), comp);
    }
    bool empty()       const { return c.empty(); }
    std::size_t size() const { return c.size(); }
    const T& top()     const { return c.front(); }
    void push(const T& x)
    {
        c.push_back(x);
        std::push_heap(c.begin(), c.end(), comp);
    }
    void pop()
    {
        std::pop_heap(c.begin(), c.end(), comp);
        c.pop_back();
    }
    void remove(const T& x)
    {
        auto it = std::find(c.begin(), c.end(), x);
        if (it != c.end()) {
            c.erase(it);
            std::make_heap(c.begin(), c.end(), comp);
        }
    }
};

class Foo {
    int x_;
public:
    Foo(int x) : x_(x) {}
    bool operator<(const Foo& f) const { return x_ < f.x_; }
    bool operator==(const Foo& f) const { return x_ == f.x_; }
    int get() const { return x_; }
    void set(int x) { x_ = x; }
};

int main() {
    my_priority_queue<Foo> q;

    for (auto x: {7, 1, 9, 5}) q.push(Foo(x));
    while (!q.empty()) {
        std::cout << q.top().get() << '\n';
        q.pop();
    }

    std::cout << '\n';

    for (auto x: {7, 1, 9, 5}) q.push(Foo(x));
    Foo x = Foo(5);
    q.remove(x);
    x.set(8);
    q.push(x);
    while (!q.empty()) {
        std::cout << q.top().get() << '\n';
        q.pop();
    }
}

如何强制重组一个priority_queue？

How to force reorganization of a priority_queue?

c++11

priority-queue