Keeping a dynamic sorted range
Jakob Ovrum via Digitalmars-d
digitalmars-d at puremagic.com
Fri Nov 7 20:38:52 PST 2014
On Friday, 7 November 2014 at 14:11:32 UTC, 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
Facing this same problem, a while ago I started work on a
generic, higher-order container that provides insertion, deletion
and search while keeping itself sorted:
https://gist.github.com/JakobOvrum/f1738d31bb7ba7a46581
The above is just a WIP; it's not complete. Of course, positional
container primitives like `insertFront` and `insertBack` will not
be supported.
The implementation is fairly messy due to the lack of traits for
containers, as well as due to some deficiencies in `SortedRange`.
It's obviously useful for arrays, and it's kind of clever how it
can merge lists efficiently, but I'm not sure if it's really
worth all the effort; is it really useful to have something like
this that aims to support such a wide range of underlying
containers? Is it actually useful in real programs for anything
but arrays? So, I stopped working on it...
More information about the Digitalmars-d
mailing list