Keeping a dynamic sorted range
Max Klyga via Digitalmars-d
digitalmars-d at puremagic.com
Fri Nov 7 07:33:54 PST 2014
On 2014-11-07 14:11:30 +0000, bearophile said:
> (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
Ranges are not container. They are meant for traversing. If you want a
sorted range - use an underlying container that preserves ordering
(trees, heaps)
More information about the Digitalmars-d
mailing list