c++ - 高度な優先キュー

Question

C++での優先キューの実装を探しています。STL優先キューの基本機能に加えて、次のメソッドが必要です。

1. 押すと（関数によって決定される）すべての同じ要素を削除できます（セットと同様）
2. 一部の要素を除外できます（別の関数によって決定されます）。

それを実装する方法についていくつかの提案がありますか？

Answer 1

std::set重複せずにプライオリティキューとしてご利用いただけます。要素はtopから見つけることができますrbegin()。漸近的複雑度は、バイナリ ヒープの場合と同じです: O(1) 、 O(lg n )および O(lg n )topの標準要件に従います。ただし、定数は高くなります。rbeginpushpop

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