c++ - 迭代器与反向迭代器

Question

我正在使用 std::map 来存储很多元素(元素对)，我有一个“小”疑问。在我的 std::map、iterator 或 reverse_iterator 上迭代所有元素哪个更有效？

Answer 1

根据记录，在 std::map 和 std::set 容器上取消引用 reverse_iterator 是 < strong>比使用 iterator 慢两倍——在 Intel/AMD 处理器上同时使用 -O3 gcc 3.4.6 和 MSVC(在 PPC 架构上慢近 3 倍)同样适用于 const_reverse_iterator 与 const_iterator。这是因为 reverse_iterator 实际上 指向紧跟在要取消引用的树节点之后的树节点，因此需要额外的工作。 std::vector 迭代器表现出更温和的差异(reverse_iterator 在 PPC 上仅慢 ~30%，在 Intel/AMD 上几乎无法区分。)顺便说一句，std::vector 迭代器比 std::map 或 std::set 迭代器快大约 20 倍。

#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;
}