私の STL (g++ 4.xx に付属) は赤黒木を使用して、マップなどのコンテナーを実装することを理解しています。STL の内部赤黒ツリーを直接使用することは可能ですか。もしそうなら、どのように？そうでない場合は、なぜ STL が赤黒ツリーを公開しないのですか?
驚いたことに、私はグーグルを使って答えを見つけることができません。
編集:挿入時の余分なアロケーターコンストラクター呼び出しの解決策として、赤黒ツリーを使用して調査しています。この質問を参照してください。私の STL では、マップの実装に赤黒木を使用しています。
実際、答えは非常に単純で、gcc のバージョンに依存しません。sgi の Web サイトから stl ソース コードをダウンロードして、実装を確認し、自分で使用することができます。
たとえば、バージョン 3.2 では、赤黒ツリーの実装が stl_tree.h ファイルにあり、その使用例が stl_set.h にあります。
stl クラスはテンプレート クラスであるため、実装は実際にはヘッダー ファイル内にあることに注意してください。
とのほとんどの STL 実装は赤黒木だsetとmap思いますが、誰かが別のデータ構造を使用してそれらを実装するのを止めるものは何もありません - 私の記憶が正しければ、C++ 標準は RB ツリーの実装を必要としません。
OOP の原則に違反するため、STL はそれを公開しません。基礎となるデータ構造を公開すると、他の誰かがあなたのライブラリを使用した場合に望ましくない動作が発生する可能性があります。つまり、具体的にはsetandの場合、 andのデータ構造mapに準拠するメソッドへのアクセスのみを許可する必要があります。基になる表現を公開すると、ユーザーが 内に重複する可能性があり、これは悪いことです。setmapset
そうは言っても、（私の知る限り）基礎となる赤黒の木を直接使用する方法はありません..それは、あなたがそれをどのように使いたいかによって大きく異なります. 独自の赤黒ツリーを実装することが最善の策である可能性が高く、サードパーティのライブラリ (おそらく Boost?) を確認してください。
使用されるデータ構造が赤黒木になるという保証すら与えられていません(たとえば、AVL 木として少なくとも 1 回実装されており、B-、B*、または B+ 木のようなものはおそらく次のように問題ないでしょう)。良い）。
そのため、内部を理解する唯一の方法は、特定の実装を見て、公開されていない (少なくとも公開しようとしている) ものを利用することです。
理由については、主に抽象化の試みであり、実装の詳細をすべて公開していないためだと思います。