C++ 通过迭代器与通过运算符 []/索引访问 std::vector 的速度？

Speed accessing a std::vector by iterator vs by operator[]/index?

提问by Simone Margaritelli

Say, I have a

说，我有一个

std::vector<SomeClass *> v;

in my code and I need to access its elements very often in the program, looping them forward and backward .

在我的代码中，我需要在程序中经常访问它的元素，向前和向后循环它们。

Which is the fastest access type between those two ?

这两者之间哪个是最快的访问类型？

Iterator access:

迭代器访问：

std::vector<SomeClass *> v;
std::vector<SomeClass *>::iterator i;
std::vector<SomeClass *>::reverse_iterator j;

// i loops forward, j loops backward
for( i = v.begin(), j = v.rbegin(); i != v.end() && j != v.rend(); i++, j++ ){
    // some operations on v items
}

Subscript access (by index)

下标访问（按索引）

std::vector<SomeClass *> v;
unsigned int i, j, size = v.size();

// i loops forward, j loops backward
for( i = 0, j = size - 1; i < size && j >= 0; i++, j-- ){
    // some operations on v items
}

And, does const_iterator offer a faster way to access vector elements in case I do not have to modify them?

并且， const_iterator 是否提供了一种更快的方式来访问向量元素，以防我不必修改它们？

采纳答案by AshleysBrain

The performance difference is likely negligable or none (the compiler might optimise them to be identical); you should worry about other things, like whether your program is correct (a slow but correct program is better than a fast and incorrect program). There are other advantages to using iterators though, such as being able to change the underlying container to one with no operator[]without modifying your loops. See this questionfor more.

性能差异可能可以忽略不计或没有（编译器可能会将它们优化为相同）；您应该担心其他事情，例如您的程序是否正确（缓慢但正确的程序比快速但不正确的程序要好）。但是，使用迭代器还有其他优点，例如能够在operator[]不修改循环的情况下将底层容器更改为一个容器。请参阅此问题了解更多信息。

const_iterators will most likely have none, or negligable, performance difference compared to ordinary iterators. They are designed to improve the correctness of your program by preventing modifying things that shouldn't be modified, not for performance. The same goes for the constkeyword in general.

与普通迭代器相比，const_iterators 很可能没有或可以忽略不计的性能差异。它们旨在通过防止修改不应该修改的内容来提高程序的正确性，而不是为了性能。const一般来说，关键字也是如此。

In short, optimisation should not be a concern of yours until two things have happened: 1) you have noticed it runs too slowlyand 2) you have profiled the bottlenecks. For 1), if it ran ten times slower than it could, but is only ever run once and takes 0.1ms, who cares? For 2), make sure it's definitely the bottleneck, otherwise optimising it will have nearly no measurable effecton performance!

简而言之，在发生以下两件事之前，优化不应该成为您的关注点：1) 您注意到它运行得太慢，以及 2)您已经分析了瓶颈。对于 1)，如果它的运行速度比它可以慢十倍，但只运行一次并且只需要 0.1 毫秒，谁在乎？对于 2)，确保它绝对是瓶颈，否则优化它对性能几乎没有可衡量的影响！

回答by borx

A simple loop-based benchmark has been fulfilled. I used VS 2010 SP1 (release configuration).

一个简单的基于循环的基准测试已经完成。我使用了 VS 2010 SP1（发布配置）。

1. Use iterators (*it = *it + 1;)
2. Use indices (vs[i] = vs[i] + 1;)

1. 使用迭代器 (*it = *it + 1;)
2. 使用索引（vs[i] = vs[i] + 1;）

In several billions of iterations the second approach turned out to be a bit faster, by 1%. The result (indices are slightly faster than iterators)is reproducible but the difference, as I said, is very small.

在数十亿次迭代中，结果证明第二种方法快了 1%。结果（索引比迭代器稍快）是可重现的，但正如我所说，差异非常小。

回答by Joris Timmermans

If speed matters, then you should have time and will to run a profiler on it and see which works best in your case.

如果速度很重要，那么您应该有时间并愿意在其上运行分析器，看看哪个最适合您的情况。

If it doesn't matter, then you are performing premature optimization and should STOP doing it.

如果没关系，那么您正在执行过早的优化，应该停止这样做。

回答by r0ng

I had a test yesterday, use [] vs iterator, the code is create a vector with some elements and remove some elements from the vector. This is the code uses operator [] to access elements

我昨天做了一个测试，使用 [] vs 迭代器，代码是创建一个包含一些元素的向量并从向量中删除一些元素。这是使用运算符 [] 访问元素的代码

  TimeSpent([](){
    std::vector<int> vt = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
    for (int i = int(vt.size()) - 1; i >= 0; i--)
    {
      if (vt[i] % 2 == 0)
      {
        //cout << "removing " << vt[i] << endl;
        vt.erase(vt.begin() + i);
      }
    }
  });

The following code is about access vector elements by using iterator

以下代码是关于使用迭代器访问向量元素

  TimeSpent([](){
    std::vector<int> vt = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
    for (std::vector<int>::iterator num = vt.begin(); num != vt.end();)
    {
      if (*num % 2 == 0)
      {
        num = vt.erase(num);
      }
      else
      {
        ++num;
      }
    }
  });

Tested by calling them by this function separately

通过此函数分别调用它们进行测试

void TimeSpent(std::function<void()> func)
{
  const int ONE_MIL = 10000;
  long times = ONE_MIL;
  std::chrono::steady_clock::time_point start = std::chrono::steady_clock::now();
  while (times > 0)
  {
    func();
    --times;
  }
  std::chrono::steady_clock::time_point end = std::chrono::steady_clock::now();
  cout << "time elapsed : " << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() << endl;
}

Tested environment is visual studio 2013 pro. version 4.5.51650
The results are :
operator[] : 192
iterator : 212
Summary: when we access the vector container, operator [] is faster than iterator.

测试环境是visual studio 2013 pro。version 4.5.51650
结果是：
operator[] : 192
iterator : 212
总结：当我们访问vector容器时，operator[]比iterator快。

回答by Péter T?r?k

I believe that vector iterators are implemented as pointers internally (in a good STL implementation), so in general there should be negligible performance difference between the two idioms. But if you want to know how these perform on yourplatform, why don't you measure it with a little test program? I don't think it would take more than 5 minutes to measure execution time of e.g. 1 million iterations with both variants...

我相信向量迭代器在内部实现为指针（在一个好的 STL 实现中），所以一般来说，这两种习语之间的性能差异应该可以忽略不计。但是如果你想知道这些在你的平台上的表现，为什么不用一个小测试程序来衡量呢？我认为用两种变体测量例如 100 万次迭代的执行时间不会超过 5 分钟......

回答by Brian Neal

As always, it depends. Normally I wouldn't think you'd see any kind of difference, but only you can determine that by profiling your code. Some compilers implement vector iterators as raw pointers, and some don't. Also, in debug builds, some compilers may be using a checked iterator, which may be slower. But in production mode it may not be any different. Profile it and see.

与往常一样，这取决于。通常我不会认为您会看到任何差异，但只有您可以通过分析您的代码来确定。有些编译器将向量迭代器实现为原始指针，有些则没有。此外，在调试版本中，某些编译器可能会使用已检查的迭代器，这可能会更慢。但在生产模式下，它可能没有任何不同。配置文件并查看。

回答by Jay

With optimization (-O2) the timings should improve (should be nearly identical).

通过优化（-O2），时间应该会有所改善（应该几乎相同）。

回答by aJ.

In terms of speed, I think might be almostsame. Better, you can profile and check anyway.

在速度方面，我认为可能几乎相同。更好的是，您无论如何都可以进行概要分析和检查。

At least you can reduce the number of variables used :)

至少你可以减少使用的变量数量:)

for( i = 0; i < size ; i++){
    // some operations on v items
    v[i];
    v[size-i+1];
}

About const_iterator: Pls refer my Q: Are const_iterators faster ?

关于const_iterator：请参考我的问题：A re const_iterators 更快吗？

回答by Michael Krelin - hacker

I'd go for iterators, but what I would optimize is calling end()in the loop and would change preincrement to postincrement. I.e. I'd

我会选择迭代器，但我要优化的是end()在循环中调用并将前增量更改为后增量。即我会

std::vector<SomeClass *> v;
std::vector<SomeClass *>::iterator i,ie;
std::vector<SomeClass *>::reverse_iterator j,je;

// i loops forward, j loops backward
for( i=v.begin(),ie=v.end(), j=v.rbegin(),je=v.rend(); i!=ie && j!=je; ++i,++j ){
    // some operations on v items
}

And I don't think it's premature microoptimization, it's just writing better code. Much less evil than calling every attempt to write efficient code premature microoptimization and substituting thinking with profiling.

而且我不认为这是过早的微优化，它只是编写更好的代码。比调用每次编写高效代码的尝试都过早地进行微优化并用分析代替思考要少得多。

回答by rajatkhanduja

I was confused about something similar and wrote a program to test the performance : https://github.com/rajatkhanduja/Benchmarks/blob/master/C%2B%2B/vectorVsArray.cpp

我对类似的事情感到困惑并编写了一个程序来测试性能：https: //github.com/rajatkhanduja/Benchmarks/blob/master/C%2B%2B/vectorVsArray.cpp

Here's the relevant observations for reading/writing to vector<int> of size 1m using g++ (without any optimization flags), on Linux-i686 (64-bit machine) with 7.7 GB RAM:-

以下是在具有 7.7 GB RAM 的 Linux-i686（64 位机器）上使用 g++（没有任何优化标志）读取/写入大小为 1m 的 vector<int> 的相关观察：-

Time taken to write to vector using indices. : 11.3909 ms

使用索引写入向量所需的时间。: 11.3909 毫秒

Time taken to read from vector using indices, sequentially. : 4.09106 ms

使用索引顺序读取向量所花费的时间。: 4.09106 毫秒

Time taken to read from vector using indices, randomly. : 39 ms

使用索引从向量中随机读取所花费的时间。: 39 毫秒

Time taken to write to vector using iterators (sequentially). : 24.9949 ms

使用迭代器（按顺序）写入向量所花费的时间。: 24.9949 毫秒

Time taken to read from vector using iterators (sequentially). : 18.8049 ms

使用迭代器（按顺序）从向量中读取所花费的时间。: 18.8049 毫秒