1

マップを塗りつぶす2つの手法を比較しようとしていました.1つはイテレータを使用し、もう1つは使用しませんでした。イテレータを使用すると高速になると聞いたことがありますが、どうすればよいでしょうか?

//With Iterator
map<int, int>::iterator insert = fibHash.begin();
fibHash.insert(begin, pair<int, int> (n, fib_val));

//Without iterator
fibHash.insert(pair<int, int> (n, fib_val));
4

4 に答える 4

4

まず、std::mapこれは順序付けられた構造であるため、要素を任意の位置に配置できないことに注意してください。特定の要素は、厳密な弱い順序関係(特定の条件を満たす以下の関係) に従って、他の要素に対して特定の位置にのみ配置できます。

最初のバリアントは、要素の適切な位置のヒントとして反復子を使用し、挿入が入力反復子の隣で発生した場合にのみ、挿入を高速化します (償却定数時間)。それ以外の場合、複雑さは 2 番目のバリアント (対数) と同じです。

最初のバリアントは、最初の引数をヒントとして使用し、挿入を試みます。ヒントが適切であれば、挿入に適した位置を見つけるために必要な比較は少なくなります。

于 2012-10-06T14:13:39.730 に答える
4

イテレータを提供する最初の形式は、実行時に高速になる可能性がありますが、適切なイテレータを選択した場合に限り、実装でヒントを使用する場合に限ります。送信先のイテレータinsertは単なるヒントです。 aはソートされたコンテナーであるinsertため、必ずしもそこに要素を挿入するとは限りません。むしろ、反復子は、要素を挿入するmap場所を探すときの開始点として、実装によって使用できます。

したがって、適切に選択されたイテレータ (多くの場合そうではない) を渡すと、ヒント イテレータを取るbegin()バージョンを使用して、理論的には、挿入の償却定数時間に近づくことができますが、ヒントのないバージョンでは、探しています。insertでO(log n)挿入します。

于 2012-10-06T14:21:03.390 に答える
-2

イテレーターはデザイン パターンであり、すべてのプログラマーが考慮すべきものです。はい、反復子は実際には高速ではありませんが、クリーンであり、データ構造を安全かつクリーンな方法で「反復」できるため、実際の情報をいじることを心配する必要はありません。

この特定のケースでは、一度に 1 つの値しか挿入していないため、反復子は実際には「最速」のソリューションではありません。たまたま、特定の関数もそれを使用できるというだけです。

最初の例では、データ構造の「先頭」に値を挿入しており、反復子が位置の決定に役立ちます。

2番目のものでは、値を最後またはデフォルトの挿入位置に挿入しているだけなので、そのためのイテレータは本当に必要ありません。

于 2012-10-06T14:20:16.913 に答える