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

Subject: Re: [boost] [Containers] Complexity of flat_*::insert(first,last)
From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2011-08-04 03:30:47

El 04/08/2011 2:41, John Bytheway escribió:

> No; the existing complexity is better.  Let S=size() and N=aS.  You have
>
> N log(S+N)
> = aS log(S(1+a))
> = S(a log(S) + a log(1+a))
> <  S(a log(S) + 1+2a+a log(a))
>
> (If you don't think that's obvious see
> <http://www.wolframalpha.com/input/?i=a+Log[1%2Ba]%3C1%2B2a%2Ba+Log[a]>)
>
> = S(1+2a + a(log(S)+log(a)))
> = S + aS(2 + log(aS))
> = S + N(2 + log(N))
> = N + N log(N) + S + N
>
> which is the alternative.  Of course, there are constant factors to
> worry about, but my gut says they work in favour of the existing
> implementation too.

Thanks! I think I also missed some copies. In sort+merge, first N was 
suppossed to be about insertion (which is wrong since sort and merge 
also make copies) and not about sorting (comparisons), so sorting 
complexity would be:

N log(N) + S + N = S(alog(S) + 1+a+a log(a))

Regarding copies: With existing implementation we have some middle 
insertions for each value (that would be quadratic: N*size()). With 
merge+sort, we have less copies on first insertion (we insert at 
vector's end which is at worst linear) but I haven't taken in care the 
internal copies that sort() and inplace_merge() need to do. And I should 
use my own sort() and inplace_merge to support movable objects for C++03 
compilers. So maybe I'll stick to current implementation for now ;-)

Best,

Ion

PS: And all that without considering the time complexity a new call has, 
depending on the free blocks the allocator manages ;-)