Speed accessing a std::vector by iterator vs by op

问题:

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?

回答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!

回答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.

回答3:

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.

回答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...

回答5:

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.

回答6:

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.

回答7:

In terms of speed, I think might be almost same. 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 ?

回答8:

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

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.

回答9:

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

回答10:

You are not only prematurely optimizing, you are micro-optimizing. This is an evil almost as bad as the former (the difference being that very, very, very rarely it is actually necessary to micro-optimize). Put the two together and you've got a recipe for disaster.

If you run a profiler and find this area of code is a bottleneck then you will need to optimize. You don't optimize by trying to reduce your loop from taking 23 clock cycles to 22. You optimize by finding ways to reduce the O() of your algorithm. But until you run a profiler you should be paying more attention to design than any other concern.

回答11:

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

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:-

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

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

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

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

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