迭代器 vs 反向迭代器

Question

迭代器 vs 反向迭代器

c++performancestlstdmap

7

我正在使用std::map来存储大量元素（元素对），但我有一个“小”疑问。在我的std::map上迭代所有元素，哪种方式更有效：使用iterator还是reverse_iterator？

- Miguel Angel

6个回答

14

这真的重要吗？在我看来，这些是你必须避免的微观优化类型。此外，即使在映射中有非常多的元素时迭代时间发生变化，你尝试迭代这么大的映射的事实意味着你很可能选择了错误的数据结构。

- Naveen

好的，你是对的。我想用运算符“<<”将所有元素打印到我的类中，但如果打印整个std::map，时间消耗太大了。最好不要这样做。谢谢。 - Miguel Angel

2

除非您对代码进行了分析并发现存在显著差异，否则我不会太担心这个问题。

"过早优化是万恶之源。" - 高德纳

- Paul Sonier

1

可能不会有任何区别。std::reverse_iterator只是一个模板shim，在编译时将++转换为--。

对于向量或其他连续存储容器，前向迭代器可能与缓存交互得更好，比反向迭代器稍微好一点（不太可能检测到），但对于基于树的容器，它不会有任何区别——没有可利用的参考局部性。

- Drew Hall

1

不是真的，它不仅仅是一个模板垫片。顺便说一下，set/map反向迭代器比正向迭代器慢2到3倍。 - vladr

0

我认为使用reverse_iterator没有意义，这是违反直觉的。

这会使代码更难理解，有人会看着代码说“什么鬼”; 如果你需要添加注释来解释为什么，那么这可能意味着它本身就不是好的代码。

- Max

-1

我在思考迭代的必要性。Map保存键值对，通常用于查找。如果您仍然需要迭代Map以某些原因（例如删除Map中包含的指针等），则可以使用std::for_each。忘记微小的优化，您可以尝试提高代码的可读性。

- aJ.

1

首先，我没有对你进行 -1 操作，但是 std::map 被设计成可迭代的。如果你只使用键值对，那么你可能会使用哈希映射（如 std::unordered_map）。如果你需要键值对和有序迭代，请放心使用 std::map。 - smerlin

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- vladr · Accepted Answer

顺便说一下，在使用 std::map 和 std::set 容器上解除引用 reverse_iterator 会比使用 iterator 慢两倍，无论是在 -O3 gcc 3.4.6 还是 MSVC 上，而且在 Intel/AMD 处理器上几乎慢了 3 倍（在 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;
}