Philippe Sigaud wrote:
On Tue, Jul 27, 2010 at 07:20, Andrei Alexandrescu
<[email protected] <mailto:[email protected]>>
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
