Re: [boost] [Containers] Complexity of flat_*::insert(first,last)

Gottlob Frege wrote:

My instinct is that pre-sorting the incoming range is worthwhile.

If you're going to do the insert-in-a-loop, that dominates and it is still O( N * (S+N) ). I think sorting brings down the constant by a factor of 2 compared to random data but it doesn't change the big-O. If you're going to do an inplace_merge or similar, that requires that the range is sorted. Phil.