performance of dynamically allocated move lists

[Rein Halbersma]

Aargh! Both of those examples mutate the container. That's almost always undesirable... Unless the container itself was a temporary being filled by some other overly-generic code, in which case most of the effort spent filling the container was probably wasted because you only needed 2 of the elements. "Thinking generic" can save some time and effort, but it can also be an insidious trap!

This is not a fair comparison. Whenever you want to have the n-least elements with n>=2, you have to do some kind of copying or swapping. Only with the min_element can you simply return a pointer.

[wgarvin]

Aargh! Both of those examples mutate the container. That's almost always undesirable... Unless the container itself was a temporary being filled by some other overly-generic code, in which case most of the effort spent filling the container was probably wasted because you only needed 2 of the elements. "Thinking generic" can save some time and effort, but it can also be an insidious trap!

This is not a fair comparison. Whenever you want to have the n-least elements with n>=2, you have to do some kind of copying or swapping. Only with the min_element can you simply return a pointer.

Not if you write the dumb loop version...

[wgarvin]

There is also boost::auto_buffer that will try a stack-allocated fixed size array, and only if that is exhausted will it to a heap-allocation. So the overhead is simply that of size-checked array-access. I tried it and allocating 128 Move elements up front gave almost identical performance (<0.2% penalty) to the std::array that I currently have (which is also identical to the C-style array, but just provides the iterator interface as a convenience).

That sounds pretty good. You might be able to use fewer elements (80?) and still get the same performance. But I guess it doesn't matter if you waste a bit of stack space -- as long as no time is spent initializing or copying or allocating that space, having a fixed array of 256 (or a boost::auto_buffer of 128) is fine. You mostly only pay for the cache lines you touch.