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

StackOverflow https://stackoverflow.com/questions/205945

  •  03-07-2019
  •  | 
  •  

質問

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

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

役に立ちましたか？

解決

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

ツリーのような構造を使用して問題を反映したいとします。
このために私たちは ブーストグラフライブラリ

または、私たちが持っているこれのために、ツリーのようなアクセス特性を持つコンテナが必要です

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

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

他のヒント

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

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

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

その他の汎用ツリーの実装をいくつか示します。
- カスパー・ピーターズのツリー.hh
- アドビの森
- コア::ツリー

STLの哲学は、コンテナの実装方法ではなく、保証に基づいてコンテナを選択することです。たとえば、コンテナの選択は、高速検索の必要性に基づいている場合があります。あなたが気にするすべてのために、コンテナは一方向リストとして実装されるかもしれません-検索が非常に高速である限り、あなたは満足するでしょう。これは、内部構造に何も触れず、アクセスにイテレーターまたはメンバー関数を使用しているためです。コードは、コンテナの実装方法ではなく、コンテナの速度、固定および定義された順序があるかどうか、スペース上で効率的かどうかなどに拘束されます。

  

＆quot;オブジェクトの階層をツリーとして保存します＆quot;

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アルゴリズムで動作させたい a>、それから物事は複雑になるかもしれません。独自のイテレータを構築して互換性を実現することもできますが、多くのアルゴリズムは階層（たとえば、範囲の順序を変更するもの）に対して意味をなさないだけです。階層内の範囲を定義することは面倒なビジネスになる可能性があります。

RBツリーの実装を探している場合は、 stl_tree.h もあなたに適しているかもしれません。

std :: mapは、赤黒の木に基づいています。他のコンテナを使用して、独自のタイプのツリーの実装を支援することもできます。

ある意味では、std :: mapはツリー（バランスの取れたバイナリツリーと同じパフォーマンス特性を持つ必要があります）ですが、他のツリー機能を公開しません。実際のツリーデータ構造を含めない背後にある可能性のある推論は、おそらくstlにすべてを含めないだけの問題でした。 stlは、独自のアルゴリズムとデータ構造の実装に使用するフレームワークと見なすことができます。

一般に、必要な基本的なライブラリ機能があり、それがstlにない場合、修正はブースト。

それ以外の場合、束があります。 //www.codeproject.com/KB/architecture/treedata_class.aspx "rel =" nofollow noreferrer ">ライブラリ out そこ、必要に応じてあなたのツリー。

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

STLは「すべて」ではないためとしょうかん。基本的に、物事を構築するために必要な最小限の構造が含まれています。

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

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

例：

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); } 
} ;

stlツリーがない理由はいくつかあると思います。主にツリーは再帰的なデータ構造の形式であり、コンテナー（リスト、ベクター、セット）のように、正確な選択が難しい複雑な微細構造を持っています。また、STLを使用して基本的な形式で非常に簡単に構築できます。

有限ルートツリーは、クラス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、およびLarsenの古典的な論文を参照してください。また、それらを結合できる例、および列挙に使用する方法についてはConnesおよびKriemerの論文を参照してください）。彼らの役割は、単に他の特定の操作を促進することであると考えるのは正しくありません。むしろ、データ構造としての基本的な役割のため、これらのタスクを容易にします。

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

ツリー上のイテレータを検討してください。おそらく、イテレータの単純なスタック、ノード、およびその親、つまりルートまで実現されます。 

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

ただし、好きなだけ持つことができます。集合的に「ツリー」を形成します。しかし、すべての矢印がルートに向かう方向に流れる場合、このコツリーはイテレータを介して単純なイテレータおよびルートに向かって反復できます。ただし、すべてのインスタンスを追跡することを除いて、他のイテレータは認識されず、前後に移動することも、イテレータのアンサンブルを削除することもできません。

ツリーは信じられないほど便利で、多くの構造を持っているため、明確に正しいアプローチをとることは深刻な課題です。私の見解では、これがSTLに実装されていない理由です。さらに、過去には、人々が宗教的になり、独自のタイプのインスタンスを含むコンテナのタイプのアイデアに挑戦するのを見てきました-しかし、彼らはそれに直面しなければなりません-それはツリータイプが表すものです-それは空の（小さな）ツリーのコレクション。現在の言語では、 container＆lt; B＆gt; のデフォルトコンストラクターが B などのヒープ（または他の場所）にスペースを割り当てない場合、チャレンジなしで許可されます。

もしこれが良い形で標準になったなら、私は喜んでいるでしょう。

すべてのSTLコンテナはイテレータで使用できます。イテレータやツリーを作成することはできません。「正しい」方法でツリーを通過できないからです。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top