Keeping a dynamic sorted range

[bearophile via Digitalmars-d]

(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