向量索引访问与迭代器访问的效率 [英] Efficiency of vector index access vs iterator access

问题描述

我有问题通过使用索引访问（使用operator []）或使用迭代器来纠正我对访问元素的效率的理解。

I have question to correct my understanding of efficiency of accessing elements of a vector by using index access (with operator []) or using an iterator.

我的理解是迭代器比索引访问更有效。
（我认为 vector :: end（）比 vector :: size（） ）。

My understanding is "iterator" is more efficient than "index access". (also I think vector::end() is more efficient than vector::size()).

现在我写了示例代码测量它（在Windows 7下使用Cygwin，使用g ++ 4.5.3）

Now I wrote sample code measure it (under Windows 7 using Cygwin, with g++ 4.5.3)

索引访问循环版本（以前标为随机访问）：

The index access loop version (formerly labeled as random access):

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 命令来测量。数字为：

I am surprised to see that the "index access" version is much quicker. I used the time command to "measure". The numbers were :

结果使用 g ++ source.cpp b $ b索引访问

results using g++ source.cpp (no optimizations) index access

real 800ms

real 800ms

迭代器访问

real 2200ms

real 2200ms

这些数字有意义吗？ （我重复运行多次）我想知道什么细节，我错过了为什么我错了...

Do these numbers make sense? (I repeated the runs multiple times) And I wondered what details I miss and why I am mistaken...

结果使用g ++ -O2
索引访问，时间实际：〜200ms

results using g++ -O2 index access, time real: ~200ms

迭代器访问，时间real：〜200ms

iterator access, time real: ~200ms

我在不同平台上重复测试（amd64 w / g ++和power7 w xlC），看到我使用优化代码的示例程序有相似的执行时间。

I repeated tests on different platform (amd64 w/ g++ and power7 w xlC) and see that all the time I used optimized code the example programs have similar execution time.

编辑更改代码以添加值（ value + = * iter ），而不是仅使用分配。添加有关编译器选项的详细信息。添加了使用-O2的新数字。
* edit2 已将标题更正为迭代器效率为访问效率。

edit changed code to add values ( value += *iter ) instead of just using assignment. Added details about compiler options. Added new numbers for using -O2. *edit2 changed title correcting "iterator efficiency" to "accesses efficiency".

推荐答案

没有看到测试工具，编译器选项以及
如何测量时间，很难说任何东西。另外，一个好的编译器可以
能够消除一种情况或另一种情况下的循环，因为循环有
对返回的值没有影响。仍然，根据
的实现，我不会惊讶我看到迭代器显着
比索引快（反之亦然）。

Without seeing the test harnesses, the compiler options, and how you measured the time, it's hard to say anything. Also, a good compiler may be able eliminate the loop in one case or the other, since the loop has no effect on the value returned. Still, depending on the implementation, it wouldn't surprise me to see iterators significantly faster than indexing (or vice versa).

关于你的理解，没有什么固有的
类型的迭代器及其性能。你可以编写正向迭代器
，它们非常快或非常慢，就像你可以写入随机访问
迭代器一样，这些迭代器非常快或非常慢。在全球范围内，支持随机存取迭代器的数据类型
结构可能比不具有
更好的局部性，这可能有利于
随机存取迭代器;但是这真的不够能够使
任何合理的概括。

With regards to your "understanding", there's nothing inherent about the type of iterator and its performance. You can write forward iterators which are very fast, or very slow, just as you can write random access iterators which are very fast or very slow. Globally, the types of data structures which will support random access iterators are likely to have better locality than those which don't, which might work in favor of random access iterators; but that's really not enough to be able to make any reasonable generalizations.

这篇关于向量索引访问与迭代器访问的效率的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！