c++ - `list を呼び出していない::end()` 非効率？

Question

C++ プログラミングの本で、std::listイテレータについて次のように述べています。

for (iterator = list.start(); iterator != list.end(); iterator++)

list.end()ずっと電話していては効率が悪いのではないですか？最後を別の変数に保存する方がよいでしょうか、それとも C++ コンパイラ (つまり g++) がこれを自動的に処理しますか?

Answer 1

list::end()一定の時間の複雑さを持つべきであり、特にリンクされたリストの場合、おそらく非常に効率的であることを意味します.

アルゴリズムで許可されている場合は、値を保存する方がわずかに効率的です (繰り返しますが、特にリンクされたリストの場合、差が大きくなる可能性は低いです)。

ああ、そして効率を自分でテストすることについてのSteve Jessopの答えを読んでください!

Answer 2

への呼び出しがstd::list<T>::end()大きな効率の問題になる可能性は低く、おそらく単一の値を読み取るだけです。ただし、変数を格納することによって、変更することを意図していないというヒントをコンパイラに与えることができます。他のコンテナの場合、もう少し複雑なベースアドレスの読み取りに加えて、計算が含まれる場合があります。まだ劇的なことは何もありませんが、おそらく避ける価値があります.

ただし、ループのセマンティックも変更される可能性があることに注意してください。ループの本体が要素を追加する可能性がある場合、前の端が移動する可能性があります。興味深いことに、コンテナーに要素を挿入するときに が変更される可能性があるかどうかを示す特定の要件が標準に見つかりませんstd::list<T>::end()(変更される実装と変更されない実装を想像できます。ほとんどの場合、変更されません。けれど）。リストを変更するときにも動作を保証したい場合はlist.end()、すべての反復で呼び出すことをお勧めします。

iterator++ところで、の代わりに を使用することについて、より大きなパフォーマンス上の懸念があります++iterator。特に、これは実際に著者が本で使用したものです。それでも、これは結果を保存するのと同じようなマイクロ最適化ですが、実行するのlist.end()は簡単です。

Answer 3

違いはほとんどありません。

標準コンテナ関数はインライン化されるため、顕著な関数呼び出しのオーバーヘッドは発生しません。残っているのは、オプティマイザーが、比較を実行するために厳密には必要ではない不要なオーバーヘッドを回避するのに十分スマートであるかどうかです。たとえば、実際に一時オブジェクトを作成し、現在の位置フィールドに入力してから、そのフィールドを読み戻しますか?それとも、リストの値とリストの先頭にある値list::iteratorの間のポインター比較として比較が終了しますか?iterator

不必要なオーバーヘッドがある場合でも、イテレータをインクリメントする場合と比較して無視できる場合があり、ループ本体と比較するとさらに無視できる場合があります。

推測よりも信頼性の高いテストを行うことができます。最適化を有効にすることを忘れないでください。最適化を行わずにパフォーマンスをテストすることは、Blake がウォームアップ トラックからバスまでより速く歩く場合、Blake は Bolt よりも速くなければならないと言っているようなものです。

Answer 4

一般的に、いいえ、非効率的ではありません。end()通常、インライン関数であり、コンパイラはそれが行うことを行うための適切なコードを生成します。もっと言えば、何と比べて非効率なの？はい、結果を保持する変数を作成するコードを追加できます。これは、単純に を呼び出すよりも少し速いかもしれませんend()。このような変更が、遅すぎるプログラムを要件を満たすプログラムに変えるのに十分な速度の違いをもたらすとは考えにくいです。

Answer 5

実際には、STL コンテナーの場合、container::end()非常に安価です。実際、C++ 標準は、いくつかのクラスのいくつかのメソッド (すべてではないにしても) に対してアルゴリズムの複雑さを義務付けcontainer::end()ており、常に一定時間です。

また、コンパイラはこれらのメソッドを自由にインライン化できるため、本質的に発生する可能性のあるオーバーヘッドをすべて取り除くことができます。一定時間内にリストの末尾を取得する方法は、リストを保存する以外に考えられないため、list.end()呼び出しはフィールド アクセスになる可能性があります。x86 プラットフォームでは、スタックに保存するよりもコストがかかりません。

走行距離は他のコレクションによって異なる場合がありますlist.end()が、ボトルネックにならない安全な賭けです.

Answer 6

時期尚早の最適化は悪ですが、良い習慣はそうではありません。ループ終了条件が変更されることを予期しない場合、つまりコンテナーを変更しない場合は、次のパターンを使用できます。

for (mylist::iterator it = alist.begin(), finish = alist.end();  it != finish;  ++it)

コンテナーが変更されていないと判断できない場合、コンパイラーがこの最適化を行うことはほとんどありません。

これにより測定可能なタイミングの違いが生じる可能性は低いことに注意してください。ただし、問題になることはありません。

Answer 7

マイクロ最適化が必要な場合は、はい。

一般に、呼び出しlist.end()によってパフォーマンスが大幅に低下することはなく、おそらく問題にはなりません。呼び出しごとに同じ値を返したり、インライン化されたりする場合があります。遅くはありませんが、少し時間がかかります。

絶対にスピードが必要な場合は、 を使用しますfor (iterator = list.start(), end = list.end; iteration != end; ++iterator)。これにより、終了イテレータがキャッシュされ (および pre-inc が実行され)、呼び出しが繰り返されることはありません。

2 番目のタイプは通常は不要ですが、.end()コストがかかる場合やループが非常に大きい場合は便利です。