c++ - C++ STL が「ツリー」コンテナを提供しないのはなぜですか?

Question

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

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

score 190 · Accepted Answer

ツリーを使用する理由は 2 つあります。

ツリーのような構造を使用して問題をミラーリングしたい場合:
このためにブーストグラフライブラリがあります。

または、ツリーのようなアクセス特性を持つコンテナが必要です。

std::map(およびstd::multimap)
std::set(およびstd::multiset)

基本的に、これら 2 つのコンテナーの特性は、実際にはツリーを使用して実装する必要があるというものです (ただし、これは実際には要件ではありません)。

この質問も参照してください: C ツリーの実装

score 105 · Accepted Answer

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

考慮すべきいくつかの問題:

ノードの子の数は固定ですか、それとも可変ですか?
ノードあたりのオーバーヘッドはどのくらいですか? - つまり、親ポインター、兄弟ポインターなどが必要ですか。
提供するアルゴリズムは? - さまざまな反復子、検索アルゴリズムなど

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

その他の一般的なツリーの実装を次に示します。

score 53 · Accepted Answer

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

C++11 が登場したり消えたりしました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 アルゴリズムで動作させたい場合、事態は複雑になる可能性があります。独自の反復子を作成して、ある程度の互換性を実現することはできますが、アルゴリズムの多くは、階層 (たとえば、範囲の順序を変更するもの) にはまったく意味がありません。階層内で範囲を定義するだけでも、厄介な作業になる可能性があります。

score 53 · Accepted Answer

STL の哲学は、コンテナーの実装方法ではなく、保証に基づいてコンテナーを選択することです。たとえば、コンテナーの選択は、高速なルックアップの必要性に基づいている場合があります。検索が非常に高速である限り、コンテナーは単方向リストとして実装されている可能性があります。これは、とにかく内部に触れていないためです。アクセスにはイテレータまたはメンバー関数を使用しています。コードは、コンテナーの実装方法に拘束されるのではなく、コンテナーの速度、または順序が固定され定義されているかどうか、スペース効率が高いかどうかなどに拘束されます。

score 48 · Accepted Answer

RB ツリーの実装を探している場合は、stl_tree.hも適している可能性があります。

score 13 · Accepted Answer

std::map はred black treeに基づいています。他のコンテナーを使用して、独自の種類のツリーを実装することもできます。

score 9 · Accepted Answer

ある意味では、std::map はツリー (バランスの取れたバイナリツリーと同じパフォーマンス特性を持つ必要があります) ですが、他のツリー機能を公開していません。実際のツリーデータ構造を含めない理由として考えられるのは、stl.xml にすべてを含めないということです。stl は、独自のアルゴリズムとデータ構造を実装する際に使用するフレームワークと見なすことができます。

一般に、必要な基本的なライブラリ機能があり、それがstlにない場合、修正はBOOSTを確認することです。

それ以外の場合は、ツリーのニーズに応じて、たくさんのライブラリがあります。

score 6 · Accepted Answer

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

score 5 · Accepted Answer

これは有望に見え、あなたが探しているもののようです： http://tree.phi-sci.com/

score 5 · Accepted Answer

STL は「すべて」のライブラリではないためです。基本的に、ものを構築するために必要な最小限の構造が含まれています。

score 4 · Accepted Answer

IMO、省略。しかし、STL に Tree 構造を含めないのには十分な理由があると思います。ツリーを維持するには多くのロジックがありますが、これはメンバー関数としてベースTreeNodeオブジェクトに書き込むのが最適です。TreeNodeSTL ヘッダーにラップされると、さらに厄介になります。

例えば：

template <typename T>
struct TreeNode
{
  T* DATA ; // data of type T to be stored at this TreeNode

  vector< TreeNode<T>* > children ;

  // insertion logic for if an insert is asked of me.
  // may append to children, or may pass off to one of the child nodes
  void insert( T* newData ) ;

} ;

template <typename T>
struct Tree
{
  TreeNode<T>* root;

  // TREE LEVEL functions
  void clear() { delete root ; root=0; }

  void insert( T* data ) { if(root)root->insert(data); } 
} ;

score 3 · Accepted Answer

ここでの回答を読むと、一般的な名前の理由は、ツリーを反復処理できない、またはツリーが他の STL コンテナーと同様のインターフェイスを想定しておらず、そのようなツリー構造で STL アルゴリズムを使用できないことです。

それを念頭に置いて、STL のようなインターフェイスを提供し、既存の STL アルゴリズムで可能な限り使用できる独自のツリーデータ構造を設計しようとしました。

私の考えでは、ツリーは既存の STL コンテナーに基づいている必要があり、コンテナーを非表示にしてはならないので、STL アルゴリズムで使用できるようにする必要があります。

ツリーが提供しなければならないもう 1 つの重要な機能は、トラバースイテレータです。

これが私が思いついたものです: https://github.com/cppfw/utki/blob/master/src/utki/tree.hpp

テストは次のとおりです: https://github.com/cppfw/utki/blob/master/tests/unit/src/tree.cpp

c++ - C++ STL が「ツリー」コンテナを提供しないのはなぜですか?

15 に答える 15

Related

Reference