挿入/プッシュ消去/ポップなどのすべてのSTLコンテナの複雑さの違いを示す比較を見つけるために、私はかなり長い間グーグル検索しましたが、何も見つかりませんでした。また、私の STL ブックのすべてではありません。ヒントはありますか？
もちろん、いくつかの経験則は知っています。しかし、定義はどこにありますか？
24188 次
3 に答える
3
で試してみてください
http://www.sgi.com/tech/stl/complexity.html
http://www.sgi.com/tech/stl/table_of_contents.html
Complexity.htmlから：
基本的に、抽象マシンモデルではなく、実際のコンピューターハードウェアに対して漸近アルゴリズムの複雑さの概念を正確に定義することは困難です。したがって、次のガイドラインを採用します。
- アルゴリズムAの実行時間がO（f（n））であるためには、AとA'が本質的に同じ一連の操作を実行するように、任意に長いポインターとsize_tタイプのマシンで正しい対応するアルゴリズムA'が存在する必要があります。実際のハードウェアで。（単純な場合、AとA'は同じになります。他の場合、アドレスが制限されているという知識でAが簡略化されている可能性があります。）十分に大きいサイズnの入力の場合、A'は最大でCf（n）、ここで、Cは定数であり、nとアドレスサイズの両方に依存しません。（ポインター、size_t、およびptrdiff_tの操作は、サイズに関係なく一定の時間がかかると想定されています。）
- すべてのコンテナーまたはイテレーターの複雑さの仕様は、償却された複雑さを参照しています。個々の操作には、指定よりも時間がかかる場合があります。ただし、同じコンテナまたはイテレータでの十分に長い一連の操作には、指定された操作コストの対応する合計と同じくらいの時間がかかります。
- アルゴリズムは、最悪の場合または平均的な場合のパフォーマンスを指定し、どちらを識別します。特に明記されていない限り、平均は、コンテナ要素がコンテナのサイズよりも可能な値を持つ有限型から選択され、コンテナ要素が独立して均一に分布していることを前提としています。
- 操作fの複雑さの仕様は、fによって呼び出される操作が最大で指定されたランタイムを必要とすることを前提としています。ただし、呼び出された操作が予想される場合に指定されたものよりも遅い対数係数以下である場合、アルゴリズムは一般に適切なままです。
現在のSTLの関数Fが想定するよりも操作のコストが高い場合、Fは追加コストに比例して遅くなります。このプロパティを満たさない将来の操作は、それを明示的にします。
これを正確にするために、サイズmの入力に時間f（m）を使用するようにFが指定されていると仮定します。Fは、入力サイズnで実行時間gk（n）を指定して、操作Gkを使用します。各Gkが予想よりも最大でh（n）倍遅い状況でFを使用すると、Fは最大でh（m）倍遅くなります。これは、現在のアルゴリズムのいずれも、mよりも大幅に大きい入力に操作Gkを適用しないためです。
于 2009-06-26T13:20:22.093 に答える
1
STL、Boost、およびアレイ コンテナーのパフォーマンスに関するこのレポートをご覧ください。
于 2013-09-18T11:14:48.817 に答える
1
ISO C++ 標準は、必要に応じて、アルゴリズムの複雑さとコンテナ アクセス メソッドを定義します。それ以外の場所 (明示的に述べられていない場合) はすべて無効であり、ライブラリの実装者は自由に独自の実装を行うことができます。
たとえば、マップとセットは赤黒木を使用して実装されていると想定できますが、そうする必要はありません。多くのアルゴリズムはオーバーロードされているか、特定のイテレーター カテゴリ (ランダム アクセス イテレーターなど) に特化しており、場合によっては、特別なハードウェア (XMM レジスターやいくつかの操作を並列で実行するなど) から実行するように最適化されることさえあります。
std::list のスプライスは O(1) の複雑さを持つ必要がある => 長さは O(n) であるなど、他の要件のために、操作にかかるコストを論理的に想定する必要がある場合があります。
私は N. Josuttis C++ Standard Library - Tutorial And Referenceの本を持っており、 これらすべての側面が十分にカバーされています。
よろしく、
オバネス
于 2009-06-26T14:22:46.943 に答える