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

Question

Suppose I want to sequentially access all the elements in a C++ container, which way is the most efficient one? I illustrated my question in the following example:

std::vector<int> abc;
abc.push_back(3);
abc.push_back(4);
...
...

for(int i=0; i<abc.size(); i++)
{
  abc[i];
}

std::vector<int>::iterator it = abc.begin();
std::vector<int>::iterator itEnd = abc.end();
while(it != itEnd)
{
     (*it);
     it++;
}

In this example, as you can see, two methods are used to access elements in the C++ container, so a natural question is which one is more efficient. Thanks.

Are you trying to pick one for your application to work faster? If so, pick the one that looks better in code, don't worry about speed until you see the difference. — Bartlomiej Lewandowski, Aug 01 '14 at 13:26
http://stackoverflow.com/questions/2524233/speed-accessing-a-stdvector-by-iterator-vs-by-operator-index — acraig5075, Aug 01 '14 at 13:30
For traversing the whole container linearly, for vectors, they are the same. For other data structures, iterators will be at least as fast as other ways. It depends on the data structure. — Neil Kirk, Aug 01 '14 at 13:34
Even if this is a clear case of permature optimization note this: Measuring C++ performance without optimizations enabled has no sense, its a language which heavily depends on compiler optimizations. In fact, in this specific case, I'm sure the generated code is exactly the same for both cases. — Manu343726, Aug 01 '14 at 13:36
@Manu343726 I seriously doubt it. It's not trivial for the compiler to look deep enough inside `size()` for it to realize that it's dealing with a classical array loop. In most cases, at least when I've measured, calling `size` in the loop will definitely make his first loop slower than the second (where he calls `end` outside of the loop). — James Kanze, Aug 01 '14 at 14:05

score 6 · Accepted Answer · answered Aug 01 '14 at 13:34

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

   }

This isn't necessarily a good test. Running the first loop could put the important parts of the container in CPU cache, causing subsequent loops to execute very quickly. This won't match a use case where the container is accessed in the middle of heavy work, the whole of which is looped. — Neil Kirk, Aug 01 '14 at 13:37
If you are worried about that, then test it with the first loop, get the timing. Shut down the app, and then run it the other way. If you use different objects, I have not found this to be a problem. — Brian S, Aug 01 '14 at 13:46
Another thing to note, in my testing length(), size(), empty(), all have different performance outcomes. empty() has been the best performer if you are doing a length() == 0 or size() == 0. — Brian S, Aug 01 '14 at 13:47

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

1 Answers1