3

標準では、範囲が既にソートされている場合、範囲から 4 つの順序付けられた連想コンテナー ( map、multimap、set、multiset) をすべて[first, last)線形に構築することが規定されています (23.4.4.2:5 など)。N = last - first

ただし、範囲 (たとえば、同じタイプのコンテナー) を既存のコンテナーにマージする場合、23.2.4:8 テーブル 102 では、コンテナーへのinsert範囲のマージ[i, j)が複雑N log(a.size() + N)であるとのみ指定されていN = distance(i, j)ます。これは、ヒント付き挿入を使用していることを示しているようです。

for (auto it = a.begin(); i != j; ++i)
    it = next(a.insert(it, *i));

a.insert(i, j)は、正確なヒントの割合に応じて、厳密に よりも複雑であり、よりも効率的である可能性N log(a.size() + N)があります ( のような些細な場合を除くN == 0)。が最初は空の場合、すべてのヒントが正しいため、linearです。a

これは標準の欠陥ですか、それともこのケースをカバーする他の言語 (または機能) がありますか? 実際には、実装は順序付き連想コンテナを別のコンテナにマージするために最適化されていますか?

この質問に刺激を与えてくれたhttps://stackoverflow.com/a/11362162/567292の功績。

4

1 に答える 1

1

後者の場合、標準は、連想コンテナーのマージの最悪の場合の保証された実行時パフォーマンスのみを指定しており、可能であればより高速なパフォーマンスのショートカットを見つけることは実装に任せていると思います。他の言語とは異なり、C++ 仕様はまさにそれ、つまり仕様であることに注意してください。「参照」実装はありません。したがって、特定のパフォーマンス基準のみを満たす実装を作成することも、指定されたパフォーマンス基準を超える機能を実装することを決定することもできます。結局のところ、仕様は、特定のアルゴリズムが実装される方法で「最小限の」パフォーマンス保証を提供するように設計されています。

そうは言っても、すべての要素に対して常にヒントを使用すると、最悪の場合のパフォーマンスは、ヒントを使用せずに単純に挿入した場合の 2 倍遅くなります。したがって、常にヒンティングを使用することが万能薬であるとは限りません。

于 2012-07-06T14:46:15.307 に答える