c++ - 高级优先队列

Question

我正在寻找C++中优先级队列的实现。除了 STL优先队列中的基本功能外，它还需要以下方法：

1. 推送时可以删除所有相同的元素（由函数确定）（类似于集合）
2. 它可以过滤掉一些元素（由另一个函数确定）。

您对如何实施它有一些建议吗？

Answer 1

您可以std::set用作没有重复的优先级队列。top可以通过 找到该元素rbegin()。渐近复杂度与二叉堆相同：top根据标准要求O(1) rbegin、 O(lg n )push和 O(lg n ) pop。不过，常数会更高。

至于过滤器，我建议您使用自定义方法（无论如何这是一个好主意）包装std::set一个类，该方法为您运行过滤谓词。push

Answer 2

只需包装一个priority_queue：

#include <set>
#include <queue>

// Default predicate allows all objects through
template <typename T>
struct allow_any {
    bool operator()(T const&) const {
        return true;
    }
};

// F is a callable type for the filtering predicate -- either a
// function pointer, or a class having an operator()(T const&).
template <typename T, typename F = allow_any<T> >
class filtering_priority_queue {
public:
    explicit filtering_priority_queue(F f) : allow(f) {}

    void push(T x) {
        if (allow(x) && s.find(x) == s.end()) {
            q.push(x);
            s.insert(x);
        }
    }

    T const& top() const {
        return q.top();
    }

    void pop() {
        s.erase(top());
        q.pop();
    }

private:
    std::set<T> s;
    std::priority_queue<T> q;
    F allow;
};