異なるSTLコンテナの複雑さ（パフォーマンス）の比較はどこにありますか？

Question

挿入/プッシュイレース/ポップなどのすべてのSTLコンテナの複雑さの違いを示す比較を見つけるために私はかなり時間を捜しました。私は何も見つかりませんでした。私のSTL本のすべてではありません。何かヒント？

もちろん、私は親指のいくつかのルールを知っています。しかし定義はどこですか？

Answer 1

complexity.htmlから

http://www.sgi.com/tech/stl/complexity.html

http://www.sgi.com/tech/stl/table_of_contents.html

で試してみてください：

基本的に、正確に本物の ため漸近 アルゴリズムの複雑さの概念を定義する することは困難ですの代わりにコンピュータハードウェア抽象機械モデル。したがって、私たちは、次のガイドラインのため を解決：時間O（F（n）を）実行したのは、アルゴリズムAの場合

1. 、任意 長く持つマシン上 正しい 対応するアルゴリズムA」が存在しなければなりませんpointerとsize_t型のように、 AとA 'は実際には 実際のハードウェア上で同じ操作シーケンス を実行します。 （簡単な場合 及びA「は同じであろう。 住所がが が有界であるという知識を用いて簡略化されていてもよい他の 場合において）十分 大きいサイズnの入力の場合、A」はせいぜい を取る必要があります時間Cf（n）、Cは定数であり、 サイズの両方とは独立した である。 （ポインタ、size_tの、およびptrdiff_tの 操作は、それらの サイズとは無関係 一定の時間がかかると推定される。）
2. すべてのコンテナまたはイテレータ複雑仕様は 償却複雑さを指します。個別の 操作は、 より長くかかる場合があります。しかし、同じ 容器やイテレータの操作のいずれか十分に長い シーケンスは、対応する合計指定された運用コストの として最も限り になります。
3. アルゴリズムでは、最悪ケースまたは平均ケースのいずれかを指定します。 パフォーマンスを識別します。別段の記載が、平均ない限り そのコンテナ要素がより 可能容器の大きさよりも値が、独立して均一に分布している そのコンテナ要素を有する有限の種類から選択 であると仮定する。
4. 操作fの複雑仕様はFによって呼び出される操作 はせいぜい 指定されたランタイムを必要とすることを前提としています。 起動動作が遅くなると予想する場合に指定 より、対数因子以下でない場合にはアルゴリズム は、一般に適切なままです。

5. 操作が、現在のSTLの ファンクションFで想定されているよりも高価な場合、Fは追加コストに最も比例して で減速します。 に失敗した操作は、このプロパティを満たしていれば、 を明示的にします。

   これを正確にするには、サイズmの 入力に対して時間f（m）を使用するようにFが指定されているとします。 Fは、入力サイズnの に指定された実行時間gk（n）の操作Gk、 を使用します。 Fが各Gkが予想よりも遅い h（n）よりも遅い コンテキストで使用される場合、Fは最大で ファクタh（m）だけ減速します。これは、現在のアルゴリズムの がこれまでに適用されていないために保持されます。 操作Gkは、入力よりもかなり大きく入力 より大きくなります。

Answer 2

ISO C++標準は、必要なアルゴリズム及び容器アクセス方法の複雑さを規定します。それ以外の場合（明示的に記述されていない場合）は、すべての賭けはオフであり、ライブラリ実装者は自由に独自の実装を行うことができます。

たとえば、マップとセットが赤黒のツリーを使用して実装されていると仮定できますが、その必要はありません。多くのアルゴリズムは、特定のイテレータカテゴリ（ランダムアクセスイテレータなど）にオーバーロードされたり特殊化されたり、特殊なハードウェア（XMMレジスタなど）で実行するよう最適化されていることもあります。

std :: listのスプライスにO（1）の複雑さ=>長さがO（n）ある必要があるなど、操作がどれほど費用がかかるかを論理的に仮定しなければならないことがあります。

私はN. Josuttis氏 C++ Standard Library - Tutorial And Reference から本を持っているし、すべてのこれらの側面は、そこにも覆われています。

よろしく、
Ovanes

Answer 3

STL上でこの報告書を見て、ブーストと配列コンテナのパフォーマンスここでは複雑さの比較表があり

http://landenlabs.com/code/perf-stl/perf-stl.html