C++で順序付けされたツリー

Question

C++ STLには、明らかに順序付けられたツリーデータ構造がありません。 hereを参照してください。 Boostには順序木もありませんが、データが挿入されて順序付けされた "un"オーダーのものがあります。Property Tree私は命令が記憶に関係なくであることを望む。

プロパティツリーの追加ページには、これが概念的にはboost :: ptree構造であることが記載されています。

struct ptree 
{ 
    data_type data;       // data associated with the node 
    list< pair<key_type, ptree> > children; // ordered list of named children by insertion 
}; 

私は注文を追跡するためにブーストを拡張したいと考えています。

これは正しい方法ですか？

class ordered_ptree : public boost::property_tree::ptree { 
public: 
    ordered_ptree(int id) : _id{id}{}; 

protected: 
    int _id; 
}; 

Answer 1

は（あなたの質問にコメントから、私はあなたがPythonのOrderedDictような何かをしたい理解しますが、アカウントにキーの相対的な順序を取る。）

標準ライブラリの（またはブーストの）コンテナのどれも正確ではないので、あなたが望むものであれば、std::mapを拡張したいかもしれません（特に、すべてのインターフェースが必要でない場合）。

は、あなたが今、内部

template< 
    typename Key, 
    typename Value, 
    class Compare=std::less<Key>, 
    class Alloc=std::allocator<pair<const Key, Value> > 
class ordered_map 
{ 
    // This needs to be filled. 
}; 

で始まる言って、あなたは挿入カウンタを保持することができます：0に初期化し、各挿入でインクリメントされ

std::size_t m_ins_count; 

。

内部的には、新しいキーは元のキーのstd::pair秒と挿入カウントになります。 binary search treesの標準プロパティのみ（挿入カウントである）第二pair項目によって異なるキーを持つノードは、

1. を使用すると、異なるキー
の順序を保持することを意味し、インオーダー徒歩で連続になることを暗示します
2. もし操作が同じキー項目を横断
3. 対数時間であるキー
4. 内線形時間を挿入する順序を（償却）されている保持

ので、内部的に、あなたは（lex_compare<Compare>が挿入インデックスで、その後、与えられたファンクタで最初の比較）

typedef 
     std::map< 
      std::pair<Key, std::size_t>, 
      Value, 
      lex_compare<Compare>, 
      std::allocator<std::pair<std::pair<Key, std::size_t>,  Value> > 
     internal_map_t; 

のようなものを持っていると思います。

---

今、あなたは（最低限の）インターフェースを選択し、「外の世界」のキーと、ツリーの「内面の世界」のキー+挿入インデックスのペアを変換することによって、それを実装することができます。

イテレータインターフェイスも提供する予定がある場合は、std::mapのイテレータを変更するだけでよいので、boost iterator libraryが便利です。