Re: Extending Temporary buffer for rvalues

[Christopher Jefferson <caj at cs dot st-andrews dot ac dot uk>]

On 27 Aug 2009, at 11:15, Paolo Carlini wrote:

> .. if we don't have better ideas and we want anyway to complete the
> algorithms for C++0x, I think it would make sense for now to just  
> avoid
> buffering when std::uninitialized_fill_n would be called in the
> _Temporary_buffer constructor.

Unfortunately there are two main problems with that:

1) It's quite a bit slower (around 3 times slower to sort an array of  
vector<int>s of length 1000).
2) It violates the standard. The algorithm with no buffer is O(n. log  
n. log n), we are supposed to achieve O(n log n) if there is "enough  
extra memory available".

While I still don't like it much, I've substantially simplified and  
cleaned my earlier patch and added some description to it. I'm sure  
this is correct, as I'm careful to put *__first back when I've  
initialised the temporary buffer.

I tried just insansating the buffer on first use, the problem is that  
in the case where the buffer isn't as big as the range we are trying  
to sort, different amounts of it get used at each call, making it very  
tricky to ensure each element gets constructed exactly once.

Attachment: tempbuf_diff_2
Description: Binary data

> Paolo.