Selfappending vector

[cilu]

Right, that is actually even better.

[po0ky]

You could also do this using a second, temporary vector:

I'm sorry but... thats just awfull, slow and sluggish.

[Paul McKenzie]

I'm sorry but... thats just awfull, slow and sluggish.

Did you time it?

And no, you can't tell by eyeballing STL code and determine it is slow and sluggish -- too many have made that mistake, and then are shocked that the code is not sluggish at all (once a release, optimized build is produced).

Edit: For Visual C++, you have to set as your preprocessor _SECURE_SCL=0 to make sure iterators are not checked in the release build. Once you do that and produce a release build, then do timing tests. Don't bother posting debug build timing tests, no one will look at them, as they're meaningless.

Regards,

Paul McKenzie

[po0ky]

Did you time it?

How did you know that?

And no, you can't tell by eyeballing STL code and determine it is slow and sluggish -- too many have made that mistake, and then are shocked that the code is not sluggish at all (once a release, optimized build is produced).

It's as if you are looking over my shoulder.

Edit: For Visual C++, you have to set as your preprocessor _SECURE_SCL=0 to make sure iterators are not checked in the release build. Once you do that and produce a release build, then do timing tests. Don't bother posting debug build timing tests, no one will look at them, as they're meaningless.

o_0... I gues i'm still a real noob...

Well I did the timing again, and my god you are right. Cilu's method is faster.

I wonder if there is an even faster way?

[Paul McKenzie]

It's as if you are looking over my shoulder.

No, not really. A lot of times we get posts from persons who either are just (as I said) eyeballing STL code, and assume "it's slow" because it uses a function object, or a class, or doesn't use pointers all over the place, whatever.

Or we get persons who time debug builds and claim "STL is 10 times slower than when I use pointers". Of course after telling the person to build a release build using the preprocessor _SECURE_SCL=0, then their non-STL code is no faster, and most times, slower than the STL version.

Many programmers believe that if they use a lot of pointers and/or dynamically allocate memory themselves using new[]/delete[] all over the place, that their code is faster than using STL containers and algorithms correctly. The problem is that an overuse of pointers causes the compiler's optimizer to not attempt to optimize the code, due to excessive pointer aliasing by the programmer. Excessive pointer aliasing renders an optimizer practically useless.

With STL, the compiler is well aware of the constructs used, and can optimize the code efficiently (inlining, for example). That's one underlying cause of why "pointered-up" code and STL code that uses little to no pointers seem to be on a par when it comes to speed, with the STL code many times beating the non-STL code.

Well I did the timing again, and my god you are right. Cilu's method is faster.

Not surprising.

Regards,

Paul McKenzie

[OReubens]

well it doesn't surprise me it's faster. But for other reasons.

The original implementation does a potential resize (alloc, copy, dealloc) on each insert.
Additionally, it creates a temporary string on each insert.

The temporary vector solution of Cilu pulls ahead because it avoids the above overhead, but does so at the cost of an additional chunk of memory.
Don't have acces to a compiler atm, , but I'd expect the following to be even faster:

int iSize = vec.size();
vec.resize(iSize*2-1);
for (int i=1; i<iSize;i++)
    vec[iSize-1+i]=vec[iSize-1-i];

[laserlight]

The original implementation does a potential resize (alloc, copy, dealloc) on each insert.

The same amortised expansion happens when std::back_inserter is used though, unless po0ky tested with my suggested modification instead, in which case it might be more like your suggestion. A variant of your suggestion:

const std::vector<std::string>::size_type old_size = strvec.size();
strvec.resize(old_size * 2 - 1);
const std::vector<std::string>::iterator old_end = strvec.begin() + old_size;
std::reverse_copy(strvec.begin(), old_end - 1, old_end);

[po0ky]

A variant of your suggestion:

const std::vector<std::string>::size_type old_size = strvec.size();
strvec.resize(old_size * 2 - 1);
const std::vector<std::string>::iterator old_end = strvec.begin() + old_size;
std::reverse_copy(strvec.begin(), old_end - 1, old_end);

I think we have a winner. This could probably only be faster if the size of the resulting vector would be hard coded.

I have read somewhere that lists are faster in sequential processing, but even with lists I couldn't make this run faster.