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

Subject: Re: [boost] [Containers] Complexity of flat_*::insert(first,last)
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2011-08-07 09:39:00

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.