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 ;-)