7

私はstd::map多くの要素（要素のペア）を格納するために使用していますが、「少し」疑問があります。私のstd::map、iteratorまたはですべての要素を反復するのに、より効率的なものは何reverse_iteratorですか？

4

6 に答える 6

32

記録として、とコンテナーの逆参照reverse_iteratorは、 Intel/AMD プロセッサーで -O3 gcc 3.4.6 と MSVC の両方を使用した場合の2 倍遅くなります (PPC アーキテクチャーではほぼ 3 倍遅くなります) 。これは、逆参照されるツリー ノードの直後にあるツリー ノード を実際に指しているためであり、余分な作業が必要になります。反復子は、はるかに緩やかな違いを示します ( PPC では最大 30% しか遅くなく、Intel/AMD では事実上区別できません)。ちなみに、反復子はor反復子よりも約 20 倍高速です。std::mapstd::setiteratorconst_reverse_iteratorconst_iteratorreverse_iterator std::vectorreverse_iteratorstd::vectorstd::mapstd::set

#include <set>
#include <vector>
#include <stdio.h>
#ifdef _WIN32
#include <sys/timeb.h>
#else
#include <sys/time.h>
#endif
#include <time.h>

#define CONTAINER std::set< int >

double
mygettime(void) {
# ifdef _WIN32
  struct _timeb tb;
  _ftime(&tb);
  return (double)tb.time + (0.001 * (double)tb.millitm);
# else
  struct timeval tv;
  if(gettimeofday(&tv, 0) < 0) {
    perror("oops");
  }
  return (double)tv.tv_sec + (0.000001 * (double)tv.tv_usec);
# endif
}


int main() {
  int i, x = 0;
  CONTAINER bla;
  for (i = 0; i < 10000; bla.insert(bla.end(), i++)) ;

  double t1 = mygettime();

  for (i = 0; i < 100; ++i) {
    for (CONTAINER::iterator it = bla.begin(); it != bla.end(); ++it) {
      x ^= *it;
    }
  }

  printf("forward: %f\n", mygettime() - t1);

  double t2 = mygettime();

  for (i = 0; i < 100; ++i) {
    for (CONTAINER::reverse_iterator it = bla.rbegin(); it != bla.rend(); ++it) {
      x ^= *it;
    }
  }

  printf("reverse: %f\n", mygettime() - t2);

  return 0;
}
于 2010-03-31T00:09:50.793 に答える
14

それは本当に重要ですか？これらは、私見を回避するために試みなければならないマイクロ最適化のタイプです。また、マップ内の非常に多くの要素の反復時間が変更された場合でも、そのような大きなマップのすべての要素を反復しようとしているという事実は、おそらく間違ったデータ構造を選択したことを意味します。

于 2009-05-20T17:44:39.857 に答える
2

コードのプロファイルを作成し、大きな違いがあることがわかっていない限り、私はそれについて心配する必要はありません。

「時期尚早の最適化はすべての悪の根源です。」-ドナルド・クヌース

于 2009-05-20T17:49:37.087 に答える
1

おそらく違いはありません。std :: reverse_iteratorは、コンパイル時に++を-に変換する単なるテンプレートシムです。

ベクトルまたは他の隣接するストレージコンテナの場合、順方向イテレータは逆方向イテレータよりもキャッシュとの相互作用がわずかに優れている可能性がありますが（検出できる可能性は低いです）、ツリーベースのコンテナの場合は何も行われません。違いはまったくありません。悪用する参照の局所性はありません。

于 2009-05-20T17:50:00.017 に答える
0

reverse_iteratorを使用するのは意味がないと思います。直感に反します。

それはコードを理解するのを難しくします、誰かがコードを見て「wtf」に行くでしょう。理由を説明するためにコメントを付ける必要がある場合、それはおそらく最初から良いコードではないことを意味します。

于 2009-05-20T17:50:16.023 に答える
-1

反復の必要性について疑問に思っています。Map はキーと値のペアを保持し、通常はルックアップに使用します。何らかの理由でマップを反復処理する必要がある場合 (マップ内に含まれるポインターを削除する場合など)、std::for_eachを使用できます。マイクロ最適化を忘れて、コードの可読性を向上させることができます。

于 2009-05-20T17:59:04.273 に答える