Boost logo

Boost :

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.


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk