More flexible sorted ranges?
Tobias Pankrath via Digitalmars-d-learn
digitalmars-d-learn at puremagic.com
Thu Dec 4 00:08:33 PST 2014
On Sunday, 2 November 2014 at 15:13:37 UTC, bearophile wrote:
> I have often arrays that are sorted, and sometimes I'd like to
> append items to them. So I'd like to write something like:
>
>
> SortedRange!(Foo[], q{ a.x < b.x }) data;
> data ~= Foo(5);
> immutable n = data.upperBound(Foo(2)).length;
>
>
> This means having an array of Foos as sorted range, and
> appending an item to it keeping the sorting invariant (so in
> non-release mode the append verifies the array is empty or the
> last two items satisfy the sorting invariant), and this allows
> me to call functions like upperBound any time I want on 'data'
> without using any unsafe and unclean assumeSorted.
>
> Is this possible and a good idea to do?
>
> Bye,
> bearophile
To make it compatible with std.container, you should call it
Sorted(T, pred) and make it a accept any std.container, whose
opSlice returns a RandomAccesRange. A Sorted(Array!U, pred)
wouldn't itself be a RandomAcessRange but a container and it's
opSlice should return a SortedRange.
The algorithms that work on arrays and currently return a
SortedRange could retur n a Sorted!(U[], pred) instead.
More information about the Digitalmars-d-learn
mailing list