c++ - std::mapでのメモリ割り当て

Question

さまざまなC++辞書の実装（マップ、辞書、ベクトルなど）についてレポートを作成しています。

std :: mapを使用した挿入の結果は、パフォーマンスがO（log n）であることを示しています。パフォーマンスにも一貫したスパイクがあります。何が原因なのか100％わかりません。それらはメモリ割り当てが原因だと思いますが、これを証明するための文献やドキュメントを見つけることができませんでした。

誰かがこの問題を解決したり、私を正しい方向に向けたりできますか？

乾杯。

Answer 1

あなたは正しいです：それはO（log n）の複雑さです。しかし、これはマップのソートされた性質によるものです（通常はバイナリツリーベース）。

http://www.sgi.com/tech/stl/UniqueSortedAssociativeContainer.htmlも参照してください。挿入に関する注記があります。挿入を行う場所を示唆できる場合、最悪のケースはO（log n）と償却O（1）です。

マップは通常、二分木に基づいており、良好なパフォーマンスを維持するにはバランスをとる必要があります。観察している負荷スパイクは、おそらくこのバランシングプロセスに対応しています

Answer 2

STLに関しては、経験的なアプローチは厳密には必要ありません。標準がstd::map挿入などの操作の最小限の複雑さを明確に指示している場合、実験しても意味がありません。

実験を続行する前に、最小限の複雑さの保証を認識できるように、標準を読むことをお勧めします。もちろん、テストしているSTL実装にはバグがある可能性があります。しかし、人気のあるSTLはかなりよくデバッグされた生き物であり、非常に広く使用されているので、私はそれを疑うでしょう。

Answer 3

私の記憶が正しければ、std::mapはバランスの取れた赤黒木です。std :: mapが、基になるツリーのバランシングが必要であると判断した場合、スパイクの一部が発生する可能性があります。また、新しいノードが割り当てられると、OSは割り当て部分の間にいくつかのスパイクに寄与する可能性があります。