Do sorted ranges have any special properties?

[Andrei Alexandrescu]

Philippe Sigaud wrote:
> On Tue, Jul 27, 2010 at 07:20, Andrei Alexandrescu 
> <SeeWebsiteForEmail at erdani.org <mailto:SeeWebsiteForEmail at erdani.org>> 
> wrote:
> 
> 
>     * slicing a sorted range should produce a sorted range. so your
>     wrapper range opIndex must be modified to account for this.
> 
>     Cool, makes sense.
> 
> 
> 
> Another thing, though I'm not sure it's a good idea, it to have them 
> define an opIndex[ElementType!R e], that would just either forward to 
> .find() or do a simple binary search by itself: O(lg(n)) is quite good.
>  
> Yeah, isAssociativeRange!R  ;)
> But that's blurring the line between container and range, I guess.

One issue is dealing with sorted random-access ranges of size_t. Then 
there's ambiguity - which [] did you mean, searching on straight indexing?

> In the same vein, a sorted range could optionally define opIn_r that 
> also promises O(lg(n)) complexity.

This is a strong argument for putting sorted range functionality inside 
Sorted!Range.

> As for taking ideas from other languages: in Clojure, data structures 
> for which it makes sense (maps, sets?) are functions of their element 
> and return true if the provided value is in the structure. That allows 
> one to use them as predicate for finding and such, which makes for very 
> clean code, as they also have encoded literal values.

Not getting it, could you please expand/insert a link?

> Btw, should they really be called "sorted" or "ordered"? "sorted" 
> implies there was a sorting action, which is not always the case. It may 
> very well have been created that way.

Not sure, but as a putative user, with "sorted" I know 100% what's going 
on; with the slightly oblique "ordered" I might be worried enough to 
look up the manual.


Andrei