C STL にはツリー コンテナがない

C 標準テンプレート ライブラリ (STL) は「ツリー」コンテナを提供しません。この省略により、「なぜ?」という疑問が生じます。また、適切な代替手段は何ですか?

STL にツリー コンテナがないのはなぜですか?

ツリー データ構造が必要になる理由は 2 つあります:

1.階層オブジェクト表現: ツリー構造を使用して、コード内でツリー状のオブジェクト階層をモデル化します。

2.効率的なアクセス特性: 二分探索ツリーと同様に、順序関係に基づいて要素に迅速にアクセスできるようにします。

ツリー構造の代替

• ]Boost Graph Library: 階層構造を含む任意のグラフを表現するためのStructure.

• 順序付けられた連想コンテナ:

  • std::map および std::multimap: キー順にキーを値にマップします。
  • std::set および std::multiset: 順序付けされた一意の要素のコレクションvalue.

これらのコンテナはバランスの取れたバイナリ ツリーとして効果的に動作し、挿入、削除、検索の効率的な対数アクセス時間を保証します。また、次のような追加の利点も提供します。

• ソートされた順序での要素の定数時間イテレータの走査。
• キーの順序付けのための組み込みの比較ロジック。
• 比較をサポートする任意のキータイプを操作できる汎用インターフェイス演算子.

例:

CEO をルートとし、複数のレベルの部下を含む従業員の階層を保存したい場合は、次のように使用できます。 std::map<:string std::vector>>。ここで、マップ キーは従業員名になり、関連付けられたベクトルは直属の部下の名前を保持します。

結論

一方、C STL では提供されません。ツリーコンテナを直接操作することで、階層表現と効率的なアクセス特性の両方に適した代替手段を提供します。 Boost のグラフ ライブラリは複雑なグラフ構造を処理できますが、順序付けされた連想コンテナは汎用的で確立されたインターフェイスによるツリー状のアクセスを提供します。