C++ 使用 vector::iterator 或 at() 迭代 STL 向量，哪个更快？

Question

提问by Gal Goldman

In terms of performance, what would work faster? Is there a difference? Is it platform dependent?

在性能方面，什么会更快？有区别吗？是否依赖平台？

//1. Using vector<string>::iterator:
vector<string> vs = GetVector();

for(vector<string>::iterator it = vs.begin(); it != vs.end(); ++it)
{
   *it = "Am I faster?";
}

//2. Using size_t index:
for(size_t i = 0; i < vs.size(); ++i)
{
   //One option:
   vs.at(i) = "Am I faster?";
   //Another option:
   vs[i] = "Am I faster?";
}

Answer 1

采纳答案by tstenner

Why not write a test and find out?

为什么不写一个测试并找出答案？

Edit:My bad - I thought I was timing the optimised version but wasn't. On my machine, compiled with g++ -O2, the iterator version is slightly slowerthan the operator[] version, but probably not significantly so.

编辑：我的错 - 我以为我正在为优化版本计时，但事实并非如此。在我的机器上，用 g++ -O2 编译，迭代器版本比 operator[] 版本稍微慢一点，但可能不是很明显。

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

int main() {
    const int BIG = 20000000;
    vector <int> v;
    for ( int i = 0; i < BIG; i++ ) {
        v.push_back( i );
    }

    int now = time(0);
    cout << "start" << endl;
    int n = 0;
    for(vector<int>::iterator it = v.begin(); it != v.end(); ++it) {
        n += *it;
    }

    cout << time(0) - now << endl;
    now = time(0);
    for(size_t i = 0; i < v.size(); ++i) {
        n += v[i];
    }
    cout << time(0) - now << endl;

    return n != 0;
}

Answer 2

回答by tstenner

Using an iterator results in incrementing a pointer (for incrementing) and for dereferencing into dereferencing a pointer.
With an index, incrementing should be equally fast, but looking up an element involves an addition (data pointer+index) and dereferencing that pointer, but the difference should be marginal.
at()also checks if the index is within the bounds, so it could be slower.

使用迭代器会导致指针递增（用于递增）和解引用为解引用指针。
使用索引，增加应该同样快，但查找元素涉及添加（数据指针+索引）和取消引用该指针，但差异应该是微不足道的。
at()还检查索引是否在范围内，因此它可能会更慢。

Benchmark results for 500M iterations, vector size 10, with gcc 4.3.3 (-O3), linux 2.6.29.1 x86_64:
at(): 9158ms
operator[]: 4269ms
iterator: 3914ms

500M 迭代的基准测试结果，向量大小 10，gcc 4.3.3 (-O3)，linux 2.6.29.1 x86_64
at():: 9158ms
operator[]: 4269ms
iterator: 3914ms

YMMV, but if using an index makes the code more readable/understandable, you should do it.

YMMV，但如果使用索引使代码更具可读性/可理解性，您应该这样做。

Answer 3

回答by xtofl

If you don't need indexing, don't use it. The iterator concept is there for your best. Iterators are very easy to optimize, while direct access needs some extra knowledge.

如果您不需要索引，请不要使用它。迭代器的概念是最好的。迭代器很容易优化，而直接访问需要一些额外的知识。

Indexing is meant for direct access. The brackets and the atmethod do this. atwill, unlike [], check for out of bounds indexing, so it will be slower.

索引用于直接访问。括号和at方法就是这样做的。 at将与不同[]，检查越界索引，因此它会更慢。

The credo is: don't ask for what you don't need. Then the compiler won't charge you for what you don't use.

信条是：不要要求你不需要的东西。然后编译器不会因为你不使用的东西向你收费。

Answer 4

回答by James Hopkin

Since you're looking at efficiency, you should realise that the following variations are potentially more efficient:

由于您正在考虑效率，您应该意识到以下变体可能更有效：

//1. Using vector<string>::iterator:

vector<string> vs = GetVector();
for(vector<string>::iterator it = vs.begin(), end = vs.end(); it != end; ++it)
{
   //...
}

//2. Using size_t index:

vector<string> vs = GetVector();
for(size_t i = 0, size = vs.size(); i != size; ++i)
{
   //...
}

since the end/size function is only called once rather than every time through the loop. It's likely that the compiler will inline these functions anyway, but this way makes sure.

因为 end/size 函数只调用一次，而不是每次循环调用。无论如何，编译器很可能会内联这些函数，但这种方式可以确保。

Answer 5

回答by Mats Fredriksson

As everyone else here is saying, do benchmarks.

正如这里的其他人所说，做基准测试。

Having said that, I would argue that the iterator is faster since at() does range checking as well, i.e. it throws an out_of_range exception if the index is out of bounds. That check itself propbably incurrs some overhead.

话虽如此，我认为迭代器更快，因为 at() 也进行范围检查，即如果索引超出范围，它会抛出 out_of_range 异常。该检查本身可能会产生一些开销。

Answer 6

回答by Brian R. Bondy

I would guess the first variant is faster.

我猜第一个变体更快。

But it's implementation dependent. To be sure you should profile your own code.

但它依赖于实现。确保您应该分析自己的代码。

Why profile your own code?

为什么要分析自己的代码？

Because these factors will all vary the results:

因为这些因素都会改变结果：

Which OS
Which compiler
Which implementation of STL was being used
Were optimizations turned on?
... (other factors)

哪个操作系统
哪个编译器
正在使用哪种 STL 实现
是否开启优化？
...（其他因素）

Answer 7

回答by user541686

It depends.

这取决于。

The answer is much more subtle than the existing answers show.

答案比现有答案显示的要微妙得多。

atis always slower than iterators or operator[].
But for operator[]vs. iterators, it depends on:

at总是比迭代器或operator[].
但是对于operator[]vs. 迭代器，它取决于：

How exactlyyou're using operator[].
Whether your particular CPU has index registers(ESI/EDIon x86).
How much othercode also uses the same index passed to operator[].
(e.g., are you indexing through multiple arrays in lockstep?)

您究竟是如何使用operator[].
您的特定 CPU 是否具有索引寄存器（ESI/EDI在 x86 上）。
有多少其他代码也使用传递给operator[].
（例如，您是否以锁步方式对多个数组进行索引？）

Here's why:

原因如下：

If you do something like
```
std::vector<unsigned char> a, b;
for (size_t i = 0; i < n; ++i)
{
    a[13 * i] = b[37 * i];
}
```
Then this code will likely be much slower than the iterator version, since it performs a multiplicationoperationat each iteration of the loop!
Similarly, if you do something like:
```
struct T { unsigned char a[37]; };
std::vector<T> a;
for (size_t i = 0; i < n; ++i)
{
    a[i] = foo(i);
}
```
Then this will probably alsobe slower than the iterator version, because sizeof(T)is not a power of 2, and therefore you are (again) multiplying by 37each time you loop!
If your CPU has index registers, then your code can perform as well or even better with indices rather than with iterators, if using the index register frees up another registerfor use in the loop. This is notsomething you can tell just by looking; you'd have to profile the code and/or disassemble it.
If multiple arrays can share the same index, then the code only has to increment oneindex instead of incrementing multiple iterators, which reduces writes to memory and thus generally increases performance. However, if you're only iterating over a single array, then an iterator may very well be faster, since it avoids the need to add an offset to an existing base pointer.

如果你做类似的事情
```
std::vector<unsigned char> a, b;
for (size_t i = 0; i < n; ++i)
{
    a[13 * i] = b[37 * i];
}
```
那么这段代码可能会比迭代器版本慢得多，因为它在循环的每次迭代中执行乘法运算！
同样，如果您执行以下操作：
```
struct T { unsigned char a[37]; };
std::vector<T> a;
for (size_t i = 0; i < n; ++i)
{
    a[i] = foo(i);
}
```
那么这可能也比迭代器版本慢，因为sizeof(T)它不是 2 的幂，因此37每次循环时你（再次）乘以！
如果您的 CPU 具有索引寄存器，那么您的代码可以使用索引而不是迭代器来执行，甚至更好，如果使用索引寄存器释放另一个寄存器以供在循环中使用。这不是你光看就能知道的；您必须分析代码和/或反汇编它。
如果多个数组可以共享同一个索引，那么代码只需要增加一个索引而不是增加多个迭代器，这样可以减少对内存的写入，从而提高性能。但是，如果您只迭代单个数组，那么迭代器可能会更快，因为它避免了向现有基指针添加偏移量的需要。

In general, you should prefer iteratorsto indices, and indices to pointers, until and unless you face a bottleneck that profiling shows it will be beneficial to switch, because iterators are general-purposeand already likely to be the fastest approach; they don't require the data to be randomly-addressable, which allows you to swap containers if necessary. Indices are the next preferred tool, as they still don't require direct access to the data -- they are invalidated less frequently, and you can e.g. substitute a dequefor a vectorwithout any problems. Pointers should be a last resort, and they will only prove beneficial if iterators aren't already degenerating to potiners in release mode.

一般来说，你应该更喜欢迭代器而不是索引，索引而不是指针，直到并且除非你面临瓶颈，分析表明切换将是有益的，因为迭代器是通用的并且已经可能是最快的方法；它们不要求数据是可随机寻址的，这允许您在必要时交换容器。索引是下一个首选工具，因为它们仍然不需要直接访问数据——它们失效的频率较低，并且您可以例如用 a 替换dequeavector没有任何问题。指针应该是最后的手段，并且只有当迭代器在发布模式下还没有退化为指针时，它们才会被证明是有益的。

Answer 8

回答by adammonroe

It really depends on what you are doing, but if you have to keep re-declaring the iterator, Iterators become MARGINALLY SLOWER. In my tests, the fastest possible iteration would be to declare a simple * to your vectors array and Iterate through that.

这实际上取决于您在做什么，但是如果您必须不断重新声明迭代器，则迭代器会变得略慢。在我的测试中，最快的迭代是向您的向量数组声明一个简单的 * 并迭代它。

for example:

例如：

Vector Iteration and pulling two functions per pass.

向量迭代并每次传递两个函数。

vector<MyTpe> avector(128);
vector<MyTpe>::iterator B=avector.begin();
vector<MyTpe>::iterator E=avector.end()-1;
for(int i=0; i<1024; ++i){
 B=avector.begin();
   while(B!=E)
   {
       float t=B->GetVal(Val1,12,Val2); float h=B->GetVal(Val1,12,Val2);
    ++B;
  }}

Vector Took 90 clicks (0.090000 seconds)

Vector 花费了 90 次点击（0.090000 秒）

But if you did it with pointers...

但是如果你用指针来做...

for(int i=0; i<1024; ++i){
MyTpe *P=&(avector[0]);
   for(int i=0; i<avector.size(); ++i)
   {
   float t=P->GetVal(Val1,12,Val2); float h=P->GetVal(Val1,12,Val2);
   }}

Vector Took 18 clicks (0.018000 Seconds)

Vector 花了 18 次点击（0.018000 秒）

Which is roughly equivalent to...

这大致相当于...

MyTpe Array[128];
for(int i=0; i<1024; ++i)
{
   for(int p=0; p<128; ++p){
    float t=Array[p].GetVal(Val1, 12, Val2); float h=Array[p].GetVal(Val2,12,Val2);
    }}

Array Took 15 clicks (0.015000 seconds).

Array 需要 15 次点击（0.015000 秒）。

If you eliminate the call to avector.size(), the time becomes the same.

如果消除对 avector.size() 的调用，时间将变得相同。

Finally, calling with [ ]

最后，用 [ ] 调用

for(int i=0; i<1024; ++i){
   for(int i=0; i<avector.size(); ++i){
   float t=avector[i].GetVal(Val1,12,Val2); float h=avector[i].GetVal(Val1,12,Val2);
   }}

Vector Took 33 clicks (0.033000 seconds)

Vector 花了 33 次点击（0.033000 秒）

Timed with clock()

用时钟（）计时

Answer 9

回答by Mostaaf

You can use this test code and compare results! Dio it!

您可以使用此测试代码并比较结果！迪奥！

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


struct AAA{
    int n;
    string str;
};
int main() { 
    const int BIG = 5000000; 
    vector <AAA> v; 
    for ( int i = 0; i < BIG; i++ ) { 
        AAA a = {i, "aaa"};
        v.push_back( a ); 
    } 

    clock_t now;
    cout << "start" << endl; 
    int n = 0; 
    now = clock(); 
    for(vector<AAA>::iterator it = v.begin(); it != v.end(); ++it) { 
        n += it->n; 
    } 
   cout << clock() - now << endl; 

    n = 0;
    now = clock(); 
    for(size_t i = 0; i < v.size(); ++i) { 
        n += v[i].n; 
    } 
    cout << clock() - now << endl; 

    getchar();
    return n != 0; 
}

Answer 10

回答by Zorglub

The first one will be faster in debug mode because index access creates iterators behind the scene, but in release mode where everything should be inlined, the difference should be negligible or null

第一个在调试模式下会更快，因为索引访问会在幕后创建迭代器，但在所有都应该内联的发布模式下，差异应该可以忽略不计或为空

C++ 使用 vector::iterator 或 at() 迭代 STL 向量，哪个更快？

提问by Gal Goldman

采纳答案by tstenner

回答by tstenner

回答by xtofl

回答by James Hopkin

回答by Mats Fredriksson

回答by Brian R. Bondy

回答by user541686

It depends.

这取决于。

The answer is much more subtle than the existing answers show.

答案比现有答案显示的要微妙得多。

回答by adammonroe

回答by Mostaaf

回答by Zorglub

相关推荐

最近更新

标签

C++ 使用 vector::iterator 或 at() 迭代 STL 向量，哪个更快？

提问by Gal Goldman

采纳答案by tstenner

回答by tstenner

回答by xtofl

回答by James Hopkin

回答by Mats Fredriksson

回答by Brian R. Bondy

回答by user541686

It depends.

这取决于。

The answer is much more subtle than the existing answers show.

答案比现有答案显示的要微妙得多。

回答by adammonroe

回答by Mostaaf

回答by Zorglub

相关推荐

C++ 错误 LNK2019：未解析的外部符号

C++ 如何删除 const_iterator 的常量性？

一劳永逸地理解 C 和 C++ 中 f() 和 f(void) 之间的区别

在 C++ 中绘制图形和图表的免费简单方法？

相关推荐

最近更新

标签