STLはどのようなツリー実装ですか？

私はSTLでvectorが動的配列の実装を表していることを知っています。したがって、listはリンクリスト（二重リンクリスト）の実装を表します。私はsetがツリーに似た実装を持っていることを知っています。前述したようにアルゴリズムの複雑さを見ると、セット内の組み込み関数の大部分は、複雑さがo（1）またはo（log n）です。このツリーはBalanced TreeやRed-Black Treeのような他の種類のツリーとして実装されていますか？そのようなツリー構造が選ばれた理由は？STLはどのようなツリー実装ですか？

出典

2012-04-29 Invictus

本当にSTLを意味するのですか、それとも単にSTL "C++標準ライブラリ"と間違っていますか？ – Griwes

標準では、実装に制限はありません（複雑さの保証を除く）。

つまり、実装に依存します。通常は赤黒のツリーです（例：/usr/include/c++/x.y.z/bits/stl_tree.h、x.y.zはGCCの特定のバージョンです）。

出典

2012-04-29 19:41:04

私はstd :: setを使用していて、その中に値を挿入しています。ツリーの種類に特有のものを作成するのはやめてください。実際に実装に依存するのでしょうか？ – Invictus

@Ritesh：あなたの要点はわかりませんが、実際は実装に依存しています。 –

C++標準の文脈における "実装依存"は、コンパイラ/ライブラリのベンダが実装方法を決定することを意味します。 @Riteshを使用してライブラリを書く方法とは関係ありません。 – Mat

STLはどのようなツリー実装ですか？

答えて

関連する問題