7

我std::map用来存储很多元素（元素对），我有一个“小”的疑问。在 my或std::map上迭代所有元素更有效的是什么？iteratorreverse_iterator

4

6 回答 6

32

根据记录，取消引用reverse_iteratorstd::map和std::set容器的速度是使用-O3 gcc 3.4.6 和 MSVC 在 Intel/AMD 处理器上的两倍iterator（在 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;
}
于 2010-03-31T00:09:50.793 回答
14

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

于 2009-05-20T17:44:39.857 回答
2

除非您分析了您的代码并发现存在显着差异，否则我不会担心它。

“过早的优化是万恶之源。” ——唐纳德·克努斯

于 2009-05-20T17:49:37.087 回答
1

很可能没有区别。std::reverse_iterator 只是一个模板 shim，它在编译时将 ++'s 转换为 --'s。

对于向量或其他连续存储容器，前向迭代器与缓存的交互可能比反向迭代器稍微好一点（你不太可能检测到它），但对于基于树的容器，它不会产生任何影响完全不同——不会有任何可利用的参考位置。

于 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 回答