[patch] libstdc++/66742 use allocators correctly in list::sort()

[Jonathan Wakely]

In list::sort() we use 65 list objects to use as temporary storage,
splicing and swapping elements between lists.

However the lists are default constructed, with no allocator argument,
which is wrong because the allocator type might not be default
constructible, and even more wrong because splicing and merging
between lists with non-equal allocators is undefined behaviour.

So if this->get_allocator() != allocator_type() then we have undefined
behaviour.

The attached patch replaces the fixed-size array of 64
default-constructed lists with a new container-like type,
_ListSortBuf, which is initially empty (so we don't create lists we
don't need) but will grow up to a maximum size (which I kept at 64).
As the container grows it initializes new elements with the correct
allocator, so that every list used in the sort uses the same
allocator.

As well as reducing the number of lists we construct when sorting this
also allows us to range-check and ensure we don't overflow the
fixed-size array (we now get an exception if that happens, although
that's probably not possible even on a 64-bit machine).

Unfortunately this seems to hurt performance, presumably the extra
indirections to the _ListSOrtBuf rather than just an array of lists
confuse the optimisers.

Does anyone see any better solution to this? (other than rewriting the
whole sort function, which I think has been proposed)
-------------- next part --------------
A non-text attachment was scrubbed...
Name: patch.txt
Type: text/x-patch
Size: 6742 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20150703/78cb5281/attachment.bin>