Iterators and Ranges: Comparing C++ to D to Rust

[Steven Schveighoffer]

On 6/14/21 11:22 AM, Ola Fosheim Grøstad wrote:
> On Monday, 14 June 2021 at 15:12:56 UTC, Steven Schveighoffer wrote:
>> I'm referring to the talk, where you can use one function (search) to 
>> compose any possible "range" from the result that makes sense, but 
>> also ones that don't make sense.
> 
> Ok, but some complicated algorithms are sometimes easier to express if 
> you allow the ones that don't make sense (but does not happen).


True, and matching iterators from separate subranges might be reasonable 
when they all come from an original container/range. It's still *mostly* 
possible with cursors, as long as you have a definitive parent 
range/container to use for range composition.

> 
>> A C++ "safe" iterator that is essentially a range under the hood 
>> doesn't compose any better than D ranges.
> 
> I don't think "C++ iterators" with safety checks essentially are ranges, 
> they are essentially checked pointers.

You'd have to restrict them to forward-only. Which may not be a huge 
issue, if you don't ever go backwards. Or else, also you'd have to store 
the beginning of the original as well as the end.

> 
> How would you quickly search an annotated suffix array with D ranges as 
> cursors?

dcollections cursors are not iterators, they store an optional reference 
to one element, and also can tell you whether they belong to a container 
or not (they are actually ranges of zero or one element, but that's 
mostly only because it was easy to support).

So you can compose ranges using the original container and the cursors.

In terms of std::search (which is not the style that dcollections 
supported), you would use it just like C++, but of course, you have to 
compose the range before passing to a D algorithm which requires ranges.

Like:

```d
auto allEqualRange = container.search(someValue);
auto allBeforeRange = container[container.begin .. mid.begin]; // I wish 
container.begin could be `^`
auto allAfterRange = container[mid.end .. $];
auto beforeAndEqual = container[container.begin .. mid.end];
auto equalAndAfter = container[mid.begin .. $];
```

Dcollections supported a `find` method, which returned a cursor. Then 
you can compose your ranges with that. Possibly only redblacktree-based 
containers with allowed duplicates would match the requirements for 
`search`.

-Steve