11

vectorやなどのC++STLコンテナのlist場合、要素の検索と挿入または削除の複雑さは自明です。ただし、mapコンテナの場合、アクセスと挿入の複雑さ/パフォーマンスがO（log（n））であることを読んで知っていても、理由を理解することはできません。私は明らかに必要なほど地図を理解していないので、このトピックに関するいくつかの啓蒙をいただければ幸いです。

4

2 に答える 2

13

マップまたはセットの要素は、ツリー構造に含まれています。ツリーのノードを調べるたびに、検索/挿入しようとしている要素がノードより小さいか大きいかを判断します。これを行う必要がある回数 (適切にバランスの取れたツリーの場合) は、各比較で可能性の半分が破棄されるため、log2(N) です。

于 2012-06-27T21:19:36.450 に答える