Iterators and Ranges: Comparing C++ to D to Rust
Steven Schveighoffer
schveiguy at gmail.com
Mon Jun 14 15:43:47 UTC 2021
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
More information about the Digitalmars-d
mailing list