Boost logo

Boost :

Subject: Re: [boost] [Containers] Complexity of flat_*::insert(first,last)
From: John Bytheway (jbytheway+boost_at_[hidden])
Date: 2011-08-04 15:24:25


On 04/08/11 18:29, Phil Endecott wrote:
> Hi John,
>
> John Bytheway wrote:
>> No; the existing complexity is better. Let S=size() and N=aS. You
>> have
>>
>> N log(S+N)
>
> Sorry, I'm lost already. What is N log(S+N) supposed to be the
> complexity of?

It's what Ion said two posts ago:

> I took the first part from SGI documentation (the standard also says
> "N log(a.size() + N)") since I was implementing it as a loop of
> simple insertions:
>
> http://www.sgi.com/tech/stl/MultipleAssociativeContainer.html
>
> Average complexity for insert range is at most O(N * log(size() +
> N)), where N is j - i.

John


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