This is the mail archive of the
mailing list for the libstdc++ project.
Re: [RFC] libstdc++/19422: complexity of ass. containers range constr.
Chris Jefferson wrote:
> Yep, I agree. I was a bit worried for a brief moment, because I didn't
> know you could pass the end() iterator as a hint, but I see in our
> implementation of tree you can do this.
In understand from Musser/Saini that this is a common idiom.
> On a related now, I believe there is a similar bug with the insert
> function, which takes a range of iterators, which is supposed to take
> NlogN(ish) in general, and linear if the range is sorted.
Indeed. Patching the underlying stl_tree functions will automatically
> Now there is actually a problem with the actual standard here I think
> (imagine inserting the square numbers into a set which was missing
> them. It would take a "long" time to get from one square to the next).
> From the "spirit" of the function however, I think we should keep
> passing the iterator that insert_unique/insert_equal gives us back
> again when we are inserting a sequence.
> While poking around in here, I have a feel we have implemented
> insert_unique and insert_equal incorrectly. It looks to me like given
> a.insert(p,t) we are promising constant amorized time if t is inserted
> BEFORE p, not after it (like tabl 69 says). This looks fairly easy to
> fix, but if anyone has more knowledge of this code, I'd perfer them to
> check / poke it :)
Thanks for the hint: during my initial analysis of the problem I also
noticed something strange... I have to double-check, but I'm pretty sure
that the original STL specifications say "before"... Interestingly,
however, passing just end() has the advantage the probably the two
issues can be decoupled and the latter, more delicate, dealt with