C++で反復可能な優先度キューを実装する

Question

プロジェクトの優先度キューを実装する必要がありますが、STLのpriority_queueはすべての要素を反復処理してランダムに削除する必要があるため表示されません。

私たちはSTLのsetを使って、これをクラスにラップしてADTにすることを考えています。

もっとスマートな解決策がありますか？

はどのように我々はそれがとてもsetの公開メンバ関数の一部が公に使用することができますすることができますか？私たちは、イテレータに興味を持っている、など

はどうやらSTLを導出するための仮想デストラクタの不足のは賢明ではありません：/

---

新コード：だから

#ifndef PRIORITYQUEUE_H_ 
#define PRIORITYQUEUE_H_ 

#include <set> 

template<typename T, template<typename X> class impl_type = std::set> 
class PriorityQueue { 
    typedef impl_type<T> set_type; 
    typedef typename set_type::iterator iterator; 
public: 
    void push(const T& x) { 
     insert(x); 

    } 

    void pop() { 
     erase(begin()); 
    } 

    const T& top() const { 
     return *begin(); 
    } 
}; 

#endif /* PRIORITYQUEUE_H_ */ 

、我々が現在持っていますこの。コンパイラは、インサート文句はありませんが、それはerase(begin())とreturn *begin()文句を言うん：

there are no arguments to 'begin' that depend on a template parameter, so a declaration of 'begin' must be available

これはなぜですか？

Answer 1

std::vector,std::make_heap,std::push_heapおよびstd::pop_heapを使用して、独自の優先度キューを実装できる必要があります。これはどのようにstd::priority_queueが実装されていますか？ランダム要素を削除するときにデータ構造を修正するには、std::make_heapに再度電話する必要があります。

要素を順番に反復処理する必要がありますか？基礎となるstd::vectorを注文するアルゴリズムはstd::sort_heapです。

Answer 2

本当に優先キューが必要ですか？あなたはすべての項目を反復処理し、ランダムに取り外す必要

- あなたはソートそれ初めに、その後、ソートされたリストを保持する必要がある場合>リンクリスト

を、新しい項目を挿入し、使用の挿入ソート（新しい項目を挿入します正しい場所に）。

Answer 3

STLの設定は、あなたが望むものを作るために使用できるはずですが、私は要件のリストが少し奇妙に見えることに注意する必要があります。あなたは新しいタイプを定義することができます。

template<typename T, template<typename X> class impl_type = std::set> class prio_queue { 
    typedef impl_type<T> set_type; 
    typedef typename set_type::iterator iterator; 
    // etc 
public: 
    // Forward the set's members 
    T& top() { 
     return *begin(); 
    } 
    // etc 
}; 

Answer 4

私は標準ライブラリ使用組成物中に他のコンテナアダプタの一部で設定された例に従う、基礎となるコンテナテンプレートパラメータの種類になるだろう。それはあまりにも柔軟性の高い学校プロジェクトなので、既存のコンテナの1つでコンポジションを使用し、必要に応じてそこから構築することから始めます。