[PATCH] PR libstdc++/81476 Optimise vector insertion from input iterators

[Marc Glisse]

On Wed, 19 Jul 2017, Jonathan Wakely wrote:

> The PR shows a fairly pathological case where ranges of InputIterators
> are repeatedly inserted at the start of a vector. Each insertion from
> an InputIterator moves every element after the insertion point by a
> single position. So if we insert 1000 elements at the start we move
> each existing element 1000 times to reach its final position.
>
> This patch changes insertions that aren't at the end to use a
> temporary vector, which starts empty so insertions are at the end, and
> so fast. Then we do a range insert to copy everything from that vector
> at once. That uses random access iterators, so we know how far to move
> the existing elements and can just move them to their final position
> in one step.

Is it legal to use the allocator even though capacity-size is large enough 
for the inserted range?

-- 
Marc Glisse