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-03 17:18:24

El 03/08/2011 19:27, Phil Endecott escribió:
> Hi Ion,
>
> (Note typo: i,j vs, first,last)

Thanks.
>
> What implementation are you assuming to get that complexity? It seems to
> me that it is worse than it could be if you implement it something like
> this (PSEUDO-CODE):

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.

The second part is vector insertion time in case is a vector front 
insertion by N. I think it should prepend "at most ".

Your code should be:

N ¿? //insert
+ O(N log(N)) //sort (comparisons)
+ O(size()+N) //inplace_merge  (comparisons) if using intermediate memory

I think (I'm not an expert and it could depend on N's size) your code 
has lower complexity (and an additional allocation, I think it could be 
faster depending on the cost of the copies).

I guess we can just measure ;-)

Ion

PS: For set and map I don't know how to avoid duplicate issue.
PS2: I offer some insertion guarantees for duplicates (see N1780):

insert(end(), t) //insert at the end of duplicates
insert(begin(), t)// insert at from of duplicates

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1780.html

insert(first, last) was offering insertion in the end of duplicates (it 
was just a loop of simple insertions). This algorithm changes this, 
although the documentation does not offer any guarantee so I guess we 
can change it. Or use stable_sort (with additional memory N log N like 
std::sort) to guarantee it (inplace_merge is stable).