D graph library -- update

[Dmitry Olshansky]

11-Jul-2013 20:02, Joseph Rushton Wakeling пишет:
> On 07/11/2013 05:17 PM, Andrei Alexandrescu wrote:
>> Unstable sort should be faster than stable sort. If I remember correctly (1) our
>> TimSort is indeed slower than quicksort on random numbers, (2) there is a
>> performance bug that makes our quicksort perform quadratically on data that's
>> essentially sorted but has one unsorted element at the end. Is that the case?
>
> That's _exactly_ the case here. :-\

In such a case if inserting exactly one element into a sorted range you 
may want to special case it to lowerbound + insert.
E.g. something like this:

auto idx = sortedRange.lowerbound(val).length;
//insert should be called on array backing that sortedRange
insert(sortedRange, idx, val);

> Thanks for the clarification!
>


-- 
Dmitry Olshansky