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

[Paolo Carlini]

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.

Paolo.

P.S. Why the bug? I guess that the requirement in Table 69 about linear 
complexity of "ordered" construction and insert, was not part of the 
original design of the STL.