simplifying _Temporary_buffer

[Christopher Jefferson]

A few algorithms related to sorting and partitioning use a temporary  
buffer, allocated on the fly.

I've been trying to transform the algorithms which use  
_Temporary_buffer to allow move-only types, but have been finding this  
very difficult. The main difficulty comes from the fact that it isn't  
possible to setup the buffer by copying values into it at the start,  
as happens at present.

I would like to suggest a radical simplification which makes the code  
much simpler and shorter.

At the moment _Temporary_buffer begins by trying to allocate enough  
room for a copy of the whole input array, if this fails (which  
means ::operator new failed), it repeatedly tries to allocate smaller  
blocks of memory. I would like to change this, so if allocating all  
requested memory fails, we immediately stop. Note in this case the  
algorithm still works, but it is slower.

It is very hard to guess what effect this would have -- I would  
suggest that if ::operator new fails, we should probably not be trying  
to allocate extra bits of memory. I do not know how often this would  
effect people in practice -- I had to try very hard to make this code  
trigger, and cannot get it to trigger on a 64-bit processor at all.

If we do not make this simplifying assumption, I believe (although  
there may be better coders than I) that the stable_sort and  
stable_partition code will have to slow down slightly (~8%) on small  
arrays.

Does anyone know they have ever been in a low-memory environment where  
this code was useful?

In summation, the current variable-sized _Temporary_buffer code gets  
messy and slow with move-only types, there are 3 choices I can see:

1) Have to code paths, some (possibly all) buffer and no buffer  
(current status)
2) Have two code paths, full buffer and no buffer (much simpler,  
slower for part-buffer case)
3) Have three code paths, full buffer, some buffer, no buffer. some  
buffer would be really messy, and possibly never called.

Apologises for the long mail,

Chris