Keeping a dynamic sorted range

[bearophile via Digitalmars-d]

Ali Çehreli:

> If an array is sorted every time an element is added,

Items are most times added at the end, and they respect the 
sortness of the whole array. The array never gets sorted.


> On the other hand, array wins if the insertions are batched and

Insertions are not batched, and they are interspersed with 
searches. This is the common use case.


> As Max Klyga said, that single sort better be applied
> on the container, not on the range.

The container unfortunately doesn't know it is sorted, so I have 
to verify the sortness invariant manually, and before the search 
I need to use an assumeSorted(). This is not good.

Bye,
bearophile