c++ - stl set で stl c++ プライオリティ キューを使用できますか?

Question

私の質問は、セットでもあるキュー (PriorityQueue) の実装はありますか?と同じです。ただし、これは c++ と stl に関するものです。

stlをコンテナクラスに設定してstlプライオリティキューを利用することは可能ですか? そうでない場合、プライオリティ キューと共に使用してセットにすることができる代替コンテナ クラスはありますか?

Answer 1

の指定でstd::priority_queueは、「一意のメンバーシップ」は許可されていません。優先キューに一意のメンバーシップが必要な場合は、必要ありませんstd::priority_queue。

一意のメンバーシップを持つ優先キューの実装が必要な場合は、メンバーを並べ替えられた順序で保持するため、std::set すでにそれを実行しています。

Answer 2

これは可能な限り最も効率的な実装ではないかもしれませんが、次のようなことができます。(ここでは、std::priority_queue の正確なインターフェイスに合わせようとしているわけではなく、比較演算子、基になるコンテナー、または std::set アロケーターを変更することに関心がないことに注意してください)。

複製がプッシュされたときにスローするのではなく、この実装はプッシュが成功したふりをするだけです。

template<class T>
class UniquePriorityQueue
{
public:
    typedef typename std::priority_queue<T>::size_type size_type;

    void push(const T& v)
    {
        auto i = membership_.insert(v);
        if(i.second)
        {
            queue_.push(v);
        }
    }

    void pop(void)
    {
        membership_.erase(queue_.top());
        queue_.pop();
    }

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

    bool empty() const
    {
        return queue_.empty();
    }

    size_type size() const 
    {
        return queue_.size();
    }

private:
    std::priority_queue<T> queue_;
    std::set<T> membership_;
};

実装されている機能を駆動するメイン...

int main()
{
    UniquePriorityQueue<int> q;
    q.push(1);
    q.push(1);
    q.push(8);
    q.push(4);
    q.push(2);
    q.push(8);
    q.push(5);
    q.push(7);

    assert(q.size() == 6);
    assert(q.top() == 8);
    q.pop();

    assert(q.top() == 7);
    q.pop();

    assert(q.top() == 5);
    q.pop();

    assert(q.top() == 4);
    q.pop();

    assert(q.top() == 2);
    q.pop();

    assert(q.top() == 1);
    q.pop();

    assert(q.empty());  
}