More flexible sorted ranges?

[Xinok via Digitalmars-d-learn]

On Sunday, 2 November 2014 at 20:19:12 UTC, bearophile wrote:
> Xinok:
>
>> My concern is that SortedRange only accepts a range which is 
>> random-access and limits its functionality to those 
>> primitives. Concatenation is not required for random-access 
>> ranges, so should we expect SortedRange to overload this 
>> operator?
>
> I understand, that's why I am asking this here...
> I think the desire to keep a sorted range around and grow it 
> keeping its invariant is a common enough need for my code. 
> Currently I keep an array then I use assumeSorted + upperBound, 
> but this is not safe nor nice.
> Perhaps sorted ranges should become more transparent in Phobos.
>
> There are other invariants beside sortness that can be useful 
> to carry around, like set-ness (every item is unique inside 
> this collection) and few more.
>
> Bye,
> bearophile

I take back my original argument. As of 2.066, the requirements 
for SortedRange have been relaxed so it now accepts input ranges. 
The documentation needs to be updated to reflect this change.

Still, I'm not comfortable to adding concatenation to 
SortedRange. I would prefer named functions which append / 
prepend elements with the guarantee that it preserves the 
invariant.

In general, I don't feel that SortedRange is an ideal solution 
anyways. Wrapping ranges in a struct adds too much overhead and 
we can't extend the functionality of it. Would it be possible to 
replace SortedRange with a @sorted attribute or something?