Re: Benchmarks: STL's string vs. C string

Jyrki Saarinen wrote:
Niklas Holsti <niklas.holsti@xxxxxxxxxxxxxxx> wrote:

Perhaps STL keeps track of the length of each string object, so that the catenation operator does not have to scan for the final null byte of the destination string, and can just copy the source string into the right position.

In your test, the strcat loop has a quadratic complexity in the number of iterations because the "buffer" string grows by a fixded amount on each iteration, so the scan for the final null grows longer in proportion to the iteration number.

If STL knows the length of "stlBuffer", each iteration of the STL loop takes the same time and the overall loop has linear complexity in the number of iterations.

This was the reason, indeed. Not being programmed C strings for a while,
I didn't think of this at all. I had the intuition that strcat() has some wisdom about the terminating byte in the buffer, which is of course more than ridiculous.. :)

Anyway, the point of this little excercise was to prove Dijkstra's claim about STL being 50x slower in string concatenation, false.

Such a claim is meaningless, because the outcome of such a comparison depends very much on how the C and std:string version of the test are implemented, the compiler being used and last but not least which standard library implementation is being used (the C++ standard does not dictate how the standard library is to be implemented, multiple implementations do exist). It is easy to prove that the std:string is faster than C style string manipulation, or the other way around.