[c++] C ++ STLはなぜ "ツリー"コンテナを提供しないのですか?



5 Answers

おそらく、ブースト中にツリーコンテナがないのと同じ理由が考えられます。 このようなコンテナを実装するには多くの方法があり、それを使用するすべての人を満足させる良い方法はありません。

考慮すべきいくつかの問題:
- ノードの子の数は固定か可変か
- ノードあたりのオーバーヘッドはどれくらいですか? - つまり、親ポインタ、兄弟ポインタなどが必要ですか?
- 提供するアルゴリズムは? - 異なるイテレータ、検索アルゴリズムなど

結局のところ、問題は、誰にも十分に役立つツリーコンテナが、それを使用しているほとんどの人々を満足させるにはあまりにも重すぎるということになります。 強力なものを探しているのであれば、 Boost Graph Libraryは本質的にはツリーライブラリが使えるもののスーパーセットです。

他の一般的なツリーの実装を次に示します。
- キャスパー・ピーターズのtree.hh
- アドビの森
- core::tree

Question

C ++ STLはなぜ "ツリー"コンテナを提供しないのですか?代わりに使用するのに最適なものは何ですか?

私は、パフォーマンスの強化としてツリーを使用するのではなく、ツリーとしてオブジェクトの階層を保存したい...




すべてのSTLコンテナは、1つの反復メカニズムを持つ「シーケンス」として外部表現されています。 木はこのイディオムに従わない。







私はstl木がないいくつかの理由があると思う。 主にツリーは、コンテナ(リスト、ベクトル、集合)と同様に、正しい選択を難しくする非常に異なる細かい構造を持つ再帰的なデータ構造の一種です。 また、STLを使用して基本形式で構築するのも非常に簡単です。

有限ルート木は、値Aまたはペイロードを有するコンテナ、例えばクラスAのインスタンス、および場合によってはルート(サブ)ツリーの空集合であると考えることができる。 サブツリーの空の木は葉のようですが。

template<class A>
struct unordered_tree : std::set<unordered_tree>, A
{};

template<class A>
struct b_tree : std::vector<b_tree>, A
{};

template<class A>
struct planar_tree : std::list<planar_tree>, A
{};

イテレータの設計などについて少し考えなければならず、ツリー間で定義して効率的な製品と副産物の操作(元のstlはよく書かれなければならない)が必要です。デフォルトの場合、ペイロードは実際には空です。

樹木は多くの数学的構造において重要な役割を果たしています(Butcher、Grossman and Larsenの古典的論文、ConnesとKriemerの論文の例を挙げています。 彼らの役割は単に他の特定の操作を容易にすることであると考えることは正しくありません。 むしろそれらはデータ構造としての基本的な役割のためにそれらのタスクを容易にする。

しかし、木に加えて「共木」もあります。 上記のすべてのツリーには、ルートを削除するとすべてが削除されるというプロパティがあります。

ツリー上のイテレータを考えてみましょう。イテレータの単純なスタックとして、ノードへ、そしてその親へ、ルートまで実現されるでしょう。

template<class TREE>
struct node_iterator : std::stack<TREE::iterator>{
operator*() {return *back();}
...};

しかし、あなたは好きなだけ多くを持つことができます。 集合的にそれらは「ツリー」を形成するが、すべての矢印がルートに向かう方向に流れる場合、このコツリーは、イテレータを些細なイテレータおよびルートに向かって反復することができる。 ただし、他のイテレーターは認識されていないため、前後にナビゲートすることはできません。イテレーターのアンサンブルは、すべてのインスタンスを追跡する以外は削除できません。

木は信じられないほど有用であり、構造がたくさんあるため、これは決定的に正しいアプローチを得るためには深刻な課題です。 私の見解では、これがSTLに実装されていない理由です。 さらに、過去には、人々が宗教的になり、自分のタイプのインスタンスを含むコンテナのタイプのアイデアを見つけました - しかし、彼らはそれに直面しなければなりません - つまり、ツリータイプを表しています。おそらく空の(小さい)木の集まりです。 現在の言語では、 container<B>デフォルトのコンストラクターがcontainer<B>のヒープ上(または他の場所)にスペースを割り当てない限り、チャレンジせずに許可されます。

これが良い形で標準への道を見つけたなら、私は1人に喜んでもらえます。




"オブジェクトの階層をツリーとして保存したい"

C ++ 11が出て行ってしまいましたが、アイデアは出てきましたが(まだhere参照)、 std::treeを用意する必要はありませんでした。 おそらく、これを追加していない理由は、既存のコンテナの上に自分自身を構築することが自明であるからです。 例えば...

template< typename T >
struct tree_node
   {
   T t;
   std::vector<tree_node> children;
   };

単純なトラバーサルは再帰を使用します...

template< typename T >
void tree_node<T>::walk_depth_first() const
   {
   cout<<t;
   for ( auto & n: children ) n.walk_depth_first();
   }

階層を維持したいが、それをSTLアルゴリズムで動作させたい場合、事態が複雑になる可能性があります。 独自のイテレータを作成して互換性を得ることもできますが、アルゴリズムの多くは単に階層に意味をなさない(たとえば、範囲の順序を変更するもの)。 階層内の範囲を定義することも、面倒なビジネスになる可能性があります。







Related



Tags

c++ c++   stl   tree