Speed accessing a std::vector by iterator vs by operator[]/index?
Solution 1
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 question for more.
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 const
keyword in general.
In short, optimisation should not be a concern of yours until two things have happened: 1) you have noticed it runs too slowly and 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 effect on performance!
Solution 2
A simple loop-based benchmark has been fulfilled. I used VS 2010 SP1 (release configuration).
- Use iterators (*it = *it + 1;)
- Use indices (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.
Solution 3
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
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.
Solution 4
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 your platform, 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...
Solution 5
With optimization (-O2) the timings should improve (should be nearly identical).
Related videos on Youtube
Simone Margaritelli
Security researcher, hardcore C/C++ developer , wannabe reverser and coffee addicted.
Updated on August 07, 2020Comments
-
Simone Margaritelli over 3 years
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?
-
Michael Kristofik about 14 yearsWhat did the profiler results show you?
-
Simone Margaritelli about 14 yearsIf i had time and will to profile the code i wouldn't asked here. I'm just wondering if the stl iterator implementations have some sort of access optimization .
-
Björn Pollex about 14 yearsConsider using
boost::ptr_vector
if the vector owns the objects. Otherwise useboost::reference_wrapper
. -
Simone Margaritelli about 14 years@Space_C0wb0y Is 'boost::ptr_vector' (in my case) faster than std::vector ?
-
neuroguy123 about 14 yearsAsked before: stackoverflow.com/questions/776624/…
-
GManNickG about 14 years@Simone: It's safer and easier. You don't have to worry about looping through the vector, regardless of how it's being destructed. (Exceptions, for example.)
-
Ela782 about 9 yearsIf speed is really important, you shouldn't store a pointer to SomeClass, but SomeClass itself. This should boost your performance a lot because you'll eliminate all the cache misses. Other than that, in C++11/14,
for(auto&& e : v)
would most likely be the fastest because the compiler can optimise best. -
underscore_d almost 7 yearsPossible duplicate of What's faster, iterating an STL vector with vector::iterator or with at()?
-
underscore_d almost 7 years@Ela782 I really doubt the range-
for
syntax makes any difference to the generated code, since it is defined precisely as equivalent to a manually written loop using iterators (albeit done right, with a cachedend
and preincrement). -
Ela782 almost 7 years@underscore_d You're correct, the compiler generates the iterator code for the range-for loop.
-
thang over 4 yearsI really wish SO has an option to request for removal of answers. I have the same question. The code I am working with is high performance server side where squeezing a couple % can mean $. It would save me a lot of time if someone's done this benchmark. There are 11 answers. Almost all of them are utterly useless noise that I have to wade through.
-
-
Simone Margaritelli about 14 yearsare you sure that "size - i + 1" for every loop is faster than just a "j--" or better a "--j" ? i think no, so i prefer to have more variables and less clock cicles :P
-
aJ. about 14 yearsI guess these are micro optimizations and as people say, micro optimizations are evil!
-
Dai Doan about 14 years@Simone: I think that is a premature optimization. A compiler could very well be generating optimal code for aJ's example. Again, if you don't profile you won't know.
-
rafak almost 14 yearsAnd why not removing
j!=je
in the test, as the two conditions are identical? -
Michael Krelin - hacker almost 14 yearsrafak, the conditions aren't identical, even though they should coincide. I just preserved original logic, which is somewhat valid - there's nothing wrong with being on the safe side. I'm unlikely to keep both conditions, though, in my code.
-
bobobobo almost 12 yearsI disagree. If using indices instead of iterators is going to give you a performance boost, just use integer indices. You're not losing anything by using indices, and in my opinion it actually looks cleaner (
for( vector<Object>::iterator iter = list.begin() ;
vsfor( int i = 0 ;
) -
AshleysBrain almost 12 years@bobobobo - but you also lose the ability to swap container easily, like I mentioned - you can't use a std::list with an integer index.
-
catalyst294 over 9 years@AshleysBrain hints at a good point; the code you write is not the code that is run. Often times the compiler can do loop optimizations. So the question of iterator vs index probably does not matter since both will generate very similar assembly code anyways.
-
Ponkadoodle about 9 yearsWhat are you compiler flags?
for (int i = 0; i < ARR_SIZE; i++) { tmp = v[i]; }
can easily be optimized to a single statement by any intelligent compiler. In fact, most compilers will notice that you don't even read the variable anywhere. The fact that that code still takes 4 ms suggests that you may be compiling with optimizations completely disabled, which would make your benchmarks very misleading. -
duckduckgo almost 9 yearsi did a simple loop profiling and found iterator is twice slower in my case and it adds up too fast with overall very slow performance. for parsing i do not recommend using iterators however safe they may look
-
Hunter almost 7 yearsIt seems inappropriate to respond to a question like this with "you shouldn't care" without any knowledge of the circumstances.
-
thang over 4 yearsagree with Hunter's sentiment. Doesn't answer the question, and instead gave a snooty "here's how you should do it".
-
probsJustin over 4 yearsI also agree with Hunters comment. This is a largely inappropriate way to offer help and honestly just looks like discouragement from trying to solve a problem.