[RFC] libstdc++/19422: complexity of ass. containers range constr.

[Chris Jefferson]

Paolo Carlini wrote:

> Paolo Carlini wrote:
>
>> Paolo Carlini wrote:
>>
>>> Now, my immediate reaction: why we are not using instead the 
>>> versions of insert_unique/insert_equal that take an hint iterator 
>>> too? That version has guaranteed constant complexity if t is 
>>> inserted right after p (Table 69) and that would be the case when 
>>> [i, j) is already sorted, I think...
>>
>>
>> Forgot to add: in this application, the suited hint iterator would be 
>> end(), of course.
>
>
> Sorry for replying to myself again: in the meanwhile, learned from 
> pag. 167 of Musser/Derge/Saini that my idea makes perfect sense  ;)
>
> Therefore, if nobody stops me, I'm going to implement and test it.
>
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.

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.

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

Chris