c++ - STLはどのようなツリー実装に設定されていますか？

Question

vectorSTLでは動的配列の実装を表していることを私は知っています。listリンクリスト（二重リンクリスト）の実装も同様です。私はそれsetがtreeに似た実装を持っていることを知っています。前述のようにアルゴリズムの複雑さを見ると、集合内の組み込み関数のほとんどは複雑さo（1）またはo（log n）です。それで、このツリーはバランスツリーまたは赤黒木などの他の種類のツリーとして実装されますか？もしそうなら、なぜそのようなツリー構造が選択されたのですか？

Answer 1

この規格は、実装に制限を課していません（複雑さの保証を除く）。

言い換えれば、それは実装に依存します。通常、これは赤黒木です（たとえば、特定のGCCバージョンは/usr/include/c++/x.y.z/bits/stl_tree.hどこにありますかを参照してください）。x.y.z