Speed Accessing a Std::Vector by Iterator VS by Operator[]/Index

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

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!

What's faster, iterating an STL vector with vector::iterator or with at()?

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;
}

Efficiency of vector index access vs iterator access

Without seeing the test harnesses, the compiler options, and how you
measured the time, it's hard to say anything. Also, a good compiler may
be able eliminate the loop in one case or the other, since the loop has
no effect on the value returned. Still, depending on the
implementation, it wouldn't surprise me to see iterators significantly
faster than indexing (or vice versa).

With regards to your "understanding", there's nothing inherent about the
type of iterator and its performance. You can write forward iterators
which are very fast, or very slow, just as you can write random access
iterators which are very fast or very slow. Globally, the types of data
structures which will support random access iterators are likely to have
better locality than those which don't, which might work in favor of
random access iterators; but that's really not enough to be able to make
any reasonable generalizations.

c++ speed comparison iterator vs index

What you have to understand is that matrix operations are VERY well-understood, and compilers are VERY good at doing optimizations of the things that are involved in matrix operations.

Consider C = AB, where C is MxN, A is MxQ, B is QxN.

double a[M][Q], b[Q][N], c[M][N];
for(unsigned i = 0; i < M; i++){
  for (unsigned j = 0; j < N; j++) {
    double temp = 0.0;
    for (unsigned k = 0; k < Q; k++) {
      temp += a[i][k]*b[k][j];
    }
    c[i][j] = temp;
  }
}

(You would not believe how tempted I was to write the above in FORTRAN IV.)

The compiler looks at this, and notices that what is really happening is that he is walking through a and c with a stride of 1 and b with a stride of Q. He eliminates the multiplications in the subscript calculations and does straight indexing.

At that point, the inner loop is of the form:

temp += a[r1] * b[r2];
r1 += 1;
r2 += Q;

And you have loops around that to (re)initialize r1 and r2 for each pass.

That is the absolute minimum computation you can do to do a straightforward matrix multiplication. You cannot do any less than that, because you have to do those multiplications and additions and index adjustments.

All you can do is add overhead.

That's what the iterator and std::inner_product() approach does: it adds metric tonnes of overhead.

What is the most efficient way of accessing elements in a C++ container?

The best bet to figure this stuff out is to do something like 1 million loops and test it. Compilers vary. Make sure to test it in release mode.

I use ACE, but here is an example of how I get the time difference.

  // Log how long each module takes.
      ACE_Time_Value    lSendStart;
      ACE_Time_Value    lDifference;

       // Start keeping track of how long this takes
      lSendStart = ACE_OS::gettimeofday();

      // Figure out how long we took.
      lDifference = ACE_OS::gettimeofday() - lSendStart;
       // Log how long we took
      PLALOG_INFO( mLogger, ACE_TEXT( "doProcessing took ") <<lDifference.sec () << ACE_TEXT( "seconds(s) and ") << (lDifference.usec ()) <<
                    ACE_TEXT(" micro second(s) to process." ), "" );

So Get the start time, loop it a million times, get the difference, then do the same loop the other way.

Another thing I have found, if you can use the auto from c++11, you will generally find a faster loop then the historic for loop like you have shown.

   std::vector<std::string> lNameList; 
   // fill in vector
   for(auto& lSection : lNameList)
   {
      // lSection is not a string
      // DO something with it

   }

Use of iterators over array indices

I presume you are talking about when using a vector, right?

The main advantage is that iterator code works for all stl containers, while the array indexing operator [] is only available for vectors and deques. This means you are free to change the underlying container if you need to without having to recode every loop. It also means you can put your iteration code in a template and it will work for any container, not just for deques and vectors (and arrays of course).

index , pointer , iterator , which is better ? when it comes to vectors

An iterator or pointer will have the same performance on most implementations -- usually a vector iterator is a pointer. An index needs to calculate a pointer each time, but the optimizer can sometimes take care of that. Generally though, as another commenter said, there's no sense in optimizing this for performance.

All of that said, I would probably go with an iterator since it's easier to change to another type of container if need be.

Unsigned int or iterator when using vector?

The main reason to use iterators is not performance, but less possibilities for mistakes and more expressive code. Compare this

unsigned int i = 0;
while (i != myVector.size())
{
    doSomething(myVector[i]);
    i += 2;
}

or

unsigned int start = myVector.size() + 42;

for (unsigned int i = start; i != myVector.size(); ++i){
    doSomething(myVector[i]);
}

with

for (const auto& e : myVector) {
     doSomething(e);
}

Range based for loops makes using iterators as simple as it can get (you dont even see the iterators, but they are used behind the scenes). When you manually manage the index there are millions of ways to get it wrong, with iterators there are maybe 2 or 3.

For your performance comparison: As vectors store their element in contiguous memory, vector iterators can be plain pointers. What you think is overhead is mainly syntactic sugar to enable you to write nicer code. Hence its not a big surprise that you dont see much difference.

PS

i used it a lot i am kinda confident of not making too much mistakes

Using an integer to iterate an array is from the last century. Its unsafe, it leads to hard to detect bugs and can easily invoke undefined behaviour. Write code to express what you want to do, not to instruct your processor. If you want to do something for each element of a vector you should a range based for loop or the older std::for_each:

std::for_each(myVector.begin(),myVector.end(),doSomething);

It has not any of the downsides of manually using an index (did you spot the mistakes in the above loops?) and has the advantage of looking the same no matter what container myVector actually is or what type of element it contains, or what doSomething actually is (it can be a free function, a functor, a lambda, your choice).

---

Related Topics