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

Question

我有问题纠正我通过使用索引访问（使用运算符[]）或使用迭代器访问向量元素的效率的理解。

我的理解是“迭代器”比“索引访问”更有效率。 （我认为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 ++ -02 索引访问，时间真：〜200ms的

迭代器访问，真实时间：〜200毫秒

我重复不同的平台上测试（AMD64瓦特/ g ++以及POWER7瓦特方xIC）和看到，我使用的所有时间优化的代码的示例方案也有类似的执行时间。

编辑更改代码以添加值（value += *iter）而不是仅使用赋值。增加了关于编译器选项添加了使用-O2的新号码。 * edit2将标题改为“迭代器效率”改为“访问效率”。

Answer 1

没有看到测试线束，编译器选项以及您如何测量时间，很难说什么。此外，一个好的编译器可以在一种情况下或另一种情况下消除循环，因为循环具有 对返回的值没有影响。尽管如此，依赖于 的实现，我不会惊讶地发现迭代器显着地比索引更快（反之亦然）。

关于“理解”，关于迭代器类型及其性能没有任何内在的含义。您可以编写快速或非常慢的转发迭代器 ，就像您可以编写非常快或非常慢的迭代器一样。在全球范围内，将支持随机访问迭代器的数据类型可能比没有访问迭代器的数据类型具有更好的局部性，这可能有利于 随机访问迭代器;但这实在不足以使 有任何合理的概括。

Answer 2

通过优化，两个代码应该（近似）相同。尝试-O2。

如果不进行优化并添加调试信息，您的测量结果将非常具有误导性。

Answer 3

当我用-O2（Linux，GCC 4.6.1）编译这两个程序时，它们的运行速度同样快。

然后：你的第一个程序是使用迭代器，它使用指数不。这些是不同的概念。

你的第二个程序实际上是使用随机访问迭代器，因为那是std::vector<T>::iterator。对std::vector的限制是这样设计的，即迭代器可以被实现为一个简单的指针到一个vector封装的动态数组中。

begin应该和size一样快。 std::vector的典型实现中两者之间的唯一区别在于end可能需要计算begin() + size()，但size也可以实现为（大致）end() - begin()。不过，编译器可能会优化循环。

Answer 4

在第一个示例中，您使用value = vec[idx];取消引用每个单独的项目，这会导致每次访问元素时计算偏移量element_size * index。由于矢量是由连续的内存块中排列的元素组成的，所以矢量迭代器通常只是作为一个简单的指针来实现，所以迭代遍历一个矢量（就像在第二个例子中一样）只需要将指针前进一个元素每次迭代后。然而，如果启用优化（尝试-O2或-O3），则编译器可能会优化第一个示例中的循环，类似于第二个示例，从而使性能几乎相同。

Answer 5

实际上，我发现迭代器更快。尝试重构你的迭代循环，类似于下面的东西，你可能会看到这个问题，以及：

#include <ctime> 
#include <vector> 
#include <iostream> 
using namespace std; 

int main() 
{ 
    std::vector<size_t> vec (1000000); 
    size_t value = 0; 
    srand (time(NULL)); 
    clock_t start,stop; 
    int ncycle = 10000; 

    start = std::clock(); 
    for(size_t x=0; x<ncycle; ++x) { 
    for (size_t idx = 0; idx < vec.size(); ++idx) 
     vec[idx] += rand(); 
    } 
    stop = std::clock(); 
    cout << start << " " << stop << endl; 
    cout << "INDEX: " << (double((stop - start))/CLOCKS_PER_SEC)/ncycle << " seconds per cycle" << endl; 

    start = std::clock(); 
    for(size_t x=0; x<ncycle; ++x) { 
    for (std::vector<size_t>::iterator iter = vec.begin(), end = vec.end(); iter != end; ++iter) 
     *iter += rand(); 
    } 
    stop = std::clock(); 
    cout << "ITERATOR: " << (double((stop - start))/CLOCKS_PER_SEC)/ncycle << " seconds per cycle" << endl; 
} 

结果在我的电脑下面，显示出迭代器有一个微弱的领先优势：

INDEX: 0.012069 seconds per cycle 
ITERATOR: 0.011482 seconds per cycle 

你应该注意我使用了rand（）;这可以防止编译器优化出它可以在编译时计算出来的东西。编译器对于内在数组来说似乎比使用向量要容易得多，并且这会误导性地给出数组相对于向量的优势。

我用“icpc -fast”编译了上面的代码。当使用迭代器（ala指针）时，slavik正确地做了关于必须对指数进行计算与递增计算的说法。