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

[Paolo Carlini <pcarlini at suse dot de>]

Hi,

this interesting PR points out that we have a problem wrt the complexity 
of range constructor (and range insert) when [i, j) is sorted: should be 
linear, is n*log(n) instead, as in the generic case...

Indeed, internally, in the loop, insert_unique and insert_equal taking 
ranges are using insert_unique/insert_equal taking a value, and 
submitter seems definitely right.

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

Is my reasoning correct? Comments?

Thanks,
Paolo.