iterator vs reverse_iterator

Question

我std::map用来存储很多元素(元素对),我有一点"怀疑".更重要的是有效地遍历我所有的元素std::map,iterator或reverse_iterator？

Answer 1

为了记录在案,提领reverse_iterator上std::map和std::set容器是慢一倍的使用iterator-既-O3 GCC 3.4.6和MSVC在Intel/AMD处理器(几乎3倍于PPC架构一样慢.)同样适用于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;
}

Answer 2

真的有关系吗？这些是您必须尝试避免恕我直言的微优化的类型.此外,即使迭代时间因地图中的大量元素而发生变化,您尝试迭代这样一个大地图的所有元素这一事实意味着您很可能选择了错误的数据结构.