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

52,142

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).

  1. Use iterators (*it = *it + 1;)
  2. 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).

Share:
52,142

Related videos on Youtube

Simone Margaritelli
Author by

Simone Margaritelli

Security researcher, hardcore C/C++ developer , wannabe reverser and coffee addicted.

Updated on August 07, 2020

Comments

  • Simone Margaritelli
    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
      Michael Kristofik about 14 years
      What did the profiler results show you?
    • Simone Margaritelli
      Simone Margaritelli about 14 years
      If 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
      Björn Pollex about 14 years
      Consider using boost::ptr_vector if the vector owns the objects. Otherwise use boost::reference_wrapper.
    • Simone Margaritelli
      Simone Margaritelli about 14 years
      @Space_C0wb0y Is 'boost::ptr_vector' (in my case) faster than std::vector ?
    • neuroguy123
      neuroguy123 about 14 years
    • GManNickG
      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
      Ela782 about 9 years
      If 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
      underscore_d almost 7 years
    • underscore_d
      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 cached end and preincrement).
    • Ela782
      Ela782 almost 7 years
      @underscore_d You're correct, the compiler generates the iterator code for the range-for loop.
    • thang
      thang over 4 years
      I 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
    Simone Margaritelli about 14 years
    are 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.
    aJ. about 14 years
    I guess these are micro optimizations and as people say, micro optimizations are evil!
  • Dai Doan
    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
    rafak almost 14 years
    And why not removing j!=je in the test, as the two conditions are identical?
  • Michael Krelin - hacker
    Michael Krelin - hacker almost 14 years
    rafak, 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
    bobobobo almost 12 years
    I 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() ; vs for( int i = 0 ; )
  • AshleysBrain
    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
    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
    Ponkadoodle about 9 years
    What 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
    duckduckgo almost 9 years
    i 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
    Hunter almost 7 years
    It seems inappropriate to respond to a question like this with "you shouldn't care" without any knowledge of the circumstances.
  • thang
    thang over 4 years
    agree with Hunter's sentiment. Doesn't answer the question, and instead gave a snooty "here's how you should do it".
  • probsJustin
    probsJustin over 4 years
    I 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.