向量索引访问与迭代器访问的效率

Question

我有问题要通过使用索引访问(使用operator [])或使用迭代器来纠正我对访问向量元素的效率的理解.

我的理解是"迭代器"比"索引访问"更有效.(我认为vector::end()也比效率更高vector::size()).

现在我编写了示例代码测量它(在Windows 7下使用Cygwin,使用g ++ 4.5.3)

索引访问循环版本(以前标记为随机访问):

int main()
{
  std::vector< size_t > vec ( 10000000 );
  size_t value = 0;

  for( size_t x=0; x<10; ++x )
  {
    for ( size_t idx = 0; idx < vec.size(); ++idx )
    {
      value += vec[idx];
    }
    return value;
  }
}

迭代器循环代码是这样的:

    for (std::vector< size_t >::iterator iter = vec.begin(); iter != vec.end(); ++iter) {
        value = *iter;
    }

我很惊讶地看到"索引访问"版本更快.我用time命令"测量".数字是:

结果使用g++ source.cpp (无优化)索引访问

真正的800ms

迭代器访问

真正的2200ms

这些数字有意义吗？(我多次重复跑步)我想知道我错过了什么细节以及为什么我错了......

结果使用g ++ -O2索引访问,时间实际:~200ms

迭代器访问,时间真实:~200ms

我在不同平台上重复测试(amd64 w/g ++和power7 w xlC)并且看到我一直使用优化代码,示例程序具有相似的执行时间.

编辑更改的代码以添加值(value += *iter)而不是仅使用赋值.添加了有关编译器选项 添加了使用-O2的新数字.*edit2更改了标题,将"迭代器效率"更正为"访问效率".

Answer 1

如果没有看到测试工具,编译器选项以及如何测量时间,就很难说出来.此外,一个好的编译器可能能够在一种情况下消除循环,因为循环对返回的值没有影响.尽管如此,根据实现情况,看到迭代器明显快于索引(反之亦然)并不会让我感到惊讶.

关于你的"理解",迭代器的类型及其性能并不是固有的.您可以编写非常快或非常慢的正向迭代器,就像您可以编写非常快或非常慢的随机访问迭代器一样.在全球范围内,支持随机访问迭代器的数据结构类型可能比不支持随机访问迭代器的数据结构具有更好的局部性,这可能有利于随机访问迭代器; 但这真的不足以做出任何合理的概括.