What's faster, iterating an STL vector with vector::iterator or with at()?
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?";
}
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.
Benchmark results for 500M iterations, vector size 10, with gcc 4.3.3 (-O3), linux 2.6.29.1 x86_64:at()
: 9158msoperator[]
: 4269msiterator
: 3914ms
YMMV, but if using an index makes the code more readable/understandable, you should do it.
2021 update
With modern compilers, all options are practically free, but iterators are very slightly better for iterating and easier to use with range-for loops (for(auto& x: vs)
).
Code:
#include <vector>
void iter(std::vector<int> &vs) {
for(std::vector<int>::iterator it = vs.begin(); it != vs.end(); ++it)
*it = 5;
}
void index(std::vector<int> &vs) {
for(std::size_t i = 0; i < vs.size(); ++i)
vs[i] = 5;
}
void at(std::vector<int> &vs) {
for(std::size_t i = 0; i < vs.size(); ++i)
vs.at(i) = 5;
}
The generated assembly for index()
and at()
is identical godbolt, but the loop setup for iter()
is two instructions shorter:
iter(std::vector<int, std::allocator<int> >&):
mov rax, QWORD PTR [rdi]
mov rdx, QWORD PTR [rdi+8]
cmp rax, rdx
je .L1
.L3: ; loop body
mov DWORD PTR [rax], 5
add rax, 4
cmp rax, rdx
jne .L3
.L1:
ret
index(std::vector<int, std::allocator<int> >&):
mov rax, QWORD PTR [rdi]
mov rdx, QWORD PTR [rdi+8]
sub rdx, rax
mov rcx, rdx
shr rcx, 2
je .L6
add rdx, rax
.L8: ; loop body
mov DWORD PTR [rax], 5
add rax, 4
cmp rdx, rax
jne .L8
.L6:
ret
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 slower than the operator[] version, but probably not significantly so.
#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;
}