c++ - c++ stl map.find() で使用されるアルゴリズムは?

Question

map が Red-Black Tree を実装していることは知っていました。

だから私map.find()は二分探索アルゴリズムが実装されていると思います

よろしいですか？私はこのようなマップを使用しました：

std::map<int,MyObject>

Answer 1

ライブラリ標準では、特定の実装は指定されておらず、動作とパフォーマンス特性の要件のみが指定されています。特に、find()実際には二分探索のようなものが必要な対数時間を取らなければなりません。

赤黒木、またはその他のバランスの取れた検索木は、一般的な実装です。