Is a for-loop or iterator a faster way to traverse a string?

Question

I have a string.

std::string strLine;

I can traverse the string chars using a if loop

for (int i = 0; strLine[i]; i++)

Another way i can do is using string iterator

string::iterator it;
for (it = strLine.begin(); it < strLine.end(); it++)

Which is a faster and flexible way to iterate ?

This question already has an answer here, https://stackoverflow.com/questions/2113216/which-is-more-efficient-a-for-each-loop-or-an-iterator — Sdp, Apr 29 '20 at 03:50
I don't think `std::string` is guaranteed to be null terminated so your for loop might not work. You should use `for(int i = 0; i < strLine.size(); ++i)` EDIT: strLine is null terminated since c++11 — Brady Dean, Apr 29 '20 at 03:50
@eerorika Ah ok, I tried to verify that before I posted but I missed it. It would make sense because of `c_str`. — Brady Dean, Apr 29 '20 at 03:53
@BradyDean Prior to C++11, calling `c_str` was guaranteed to return pointer to null terminated string, but there was no guarantees otherwise. — eerorika, Apr 29 '20 at 03:56
@eerorika So did the pre-c++11 implementations just stick a null at the end when `c_str` was called? I'd imagine it would be easier just to implement it with a c string anyways — Brady Dean, Apr 29 '20 at 04:02
@BradyDean libstdc++ did. I don't know if they were the only one. It's marginally cheaper to only do it on call to `c_str` instead of on every construction even when the `c_str` was never called I guess. — eerorika, Apr 29 '20 at 04:21
@user997112 No, use strings I say. For performance critical stuff we nowadays got stringview and whatnot. — nada, Apr 29 '20 at 06:38
@faressalem Yes, [here](https://stackoverflow.com/q/40127965/4850111) is a relevant SO question discussing its performance. — nada, Apr 30 '20 at 08:29

cigien · Answer 1 · 2020-04-29T15:29:04.053

There are some issues with the example loops you've shown. Here's some common ways of iterating over a string:

// index based loop
for (auto i = 0u; i < strLine.size(); ++i)
  cout << strLine[i];

// iterator based loop
for (auto i = strLine.begin(); i != strLine.end(); ++i)
  cout << *i;

// range-for loop
for (auto &c: s)
  cout << c;

All these versions have the same performance, since the compiler will generate basically the same code for all of them.

Inspired by @farassalem's answer with a benchmark, I added the following lines before running the same tests:

cout << "warming up for tests ...\n";
cout << strLine << endl;
cout << "warmed up for tests ...\n";

and you get essentially the same performance for all 3 versions:

warming up for tests ...
This is a string!
warmed up for tests ...
This is a string!
index-based loop CPU time: 0.003 ms
index-based loop real time: 0.003264 ms
This is a string!
iterator-based loop CPU time: 0.003 ms
iterator-based loop real time: 0.003131 ms
This is a string!
range-for based loop CPU time: 0.002 ms
range-for based loop real time: 0.002728 ms

You should still pay close attention to how you benchmark before taking the results too seriously.

Thanks for pointing out :D Can you please see [this](https://stackoverflow.com/q/61510370/11024053) question? — faressalem, Apr 29 '20 at 19:45

faressalem · Accepted Answer · 2020-04-30T16:31:33.580

Check out this code printing a string This is a string!: LIVE

    cpu_time_start = clock();
    real_time_start = chrono::high_resolution_clock::now();

    for (auto i = 0u; i < strLine.size(); ++i)
        cout << strLine[i];
    cout << endl;

    cpu_time_end = clock();
    real_time_end = chrono::high_resolution_clock::now();
    cout << "index-based loop CPU time: " << 1000.0 * (cpu_time_end-cpu_time_start) / CLOCKS_PER_SEC << " ms\n"
         << "index-based loop real time: "<< chrono::duration<double, milli>(real_time_end-real_time_start).count() << " ms\n";

    //---------------------------------------------------------------------

    // get start time, same as above 
    for (auto i = strLine.begin(); i != strLine.end(); ++i)
        cout << *i;
    cout << endl;
    // get end time and print 

    //---------------------------------------------------------------------

    // get start time, same as above
    for (auto &c: strLine)
        cout << c;
    cout << endl;
    // get end time and print

EDIT :

Thanks to @cigien, He pointed out to a more accurate way for benchmarking by warming up, It seems that they are a little bit close to each other in performance in terms of the time of execution, and if you change the order of loops in the code, it appears that any could be slightly faster than the other, I think that's due to caching, but yet I don't think that the compiler will produce the same code for them. You can warm up by just printing out the string first before printing by iteration. And maybe a more accurate way to compare them is to test each loop in one program on its own.

This is the output when compiled with g++ -Wall -std=c++17 -O2.

warming up for tests ...
This is a string!
warmed up for tests ...
This is a string!
index-based loop CPU time: 0.008 ms
index-based loop real time: 0.005986 ms
This is a string!
iterator-based loop CPU time: 0.004 ms
iterator-based loop real time: 0.003417 ms
This is a string!
range-for based loop CPU time: 0.003 ms
range-for based loop real time: 0.002755 ms

I'll leave this part of the OLD ANSWER for people to know what happened:

OLD OUTPUT !

This is a string!
index-based loop CPU time: 0.054 ms
index-based loop real time: 0.054416 ms
This is a string!
iterator-based loop CPU time: 0.005 ms
iterator-based loop real time: 0.004291 ms
This is a string!
range-for based loop CPU time: 0.004 ms
range-for based loop real time: 0.004308 ms

It looks that the range-for loop and the iterator-based loop are very close in performance in terms of the time of execution and both execute about 10x faster than the index-based loop. Try larger length strings for more accurate results and run it many times and take the average.

You could also try compiling it on Compiler Explorer, I don't think the same code will be generated.

Is a for-loop or iterator a faster way to traverse a string?

2 Answers2

Linked