Keeping a dynamic sorted range

[Ali Çehreli via Digitalmars-d]

On 11/07/2014 06:11 AM, bearophile wrote:
> (This is a partial repost from a recent D.learn thread.)
>
> In Phobos we have SortedRange and assumeSorted, but I do find them not
> very good for a common enough use case.
>
> The use case is to keep a sorted array, keep adding items to it (adding
> larger and larger items at the end. Or sometimes even inserting items in
> the middle. In both cases I keep the sorting invariant). And while I add
> items, I also now and then want to perform a binary search on the sorted
> range.
>
> So sometimes I'd like to do something like this (but a SortedRange
> doesn't have append):
>
> struct Foo { int x; }
> SortedRange!(Foo[], q{ a.x < b.x }) data;
> data ~= Foo(5);
> immutable n = data.upperBound(Foo(2)).length;
>
> Bye,
> bearophile

If an array is sorted every time an element is added, then insertion is 
N.log(N) and searching is log(N). I don't know when that penalty is 
better than data locality that an array brings.

A more traditional data structure is a binary tree in this case because 
it has log(N) for both insertion and search.

On the other hand, array wins if the insertions are batched and then 
there is a single sort before many searches. As Max Klyga said, that 
single sort better be applied on the container, not on the range.

Ali