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