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

[Ola Fosheim Grøstad]

On Monday, 14 June 2021 at 15:43:47 UTC, Steven Schveighoffer 
wrote:
> On 6/14/21 11:22 AM, Ola Fosheim Grøstad wrote:
>> 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.

You only need to store a pointer to the container, but it doesn't 
matter if the datastructure you are looking at only provide 
offsets that stays within the legal range. Like if you do a 
binary search on a sorted dictionary and each element/node has 
offsets that expands to the range of items that starts with the 
same prefiks.

If we think of random access ranges (e.g. C++) as slices, you can 
implement binary search with elegance, but what to do if you want 
move out of the range? Then you end up writing cluttered code. At 
this point, table pointers ("C++ iterators") make the code less 
cluttered. So, there is an advantage to "C++ ranges" that can be 
decomposed into table pointers.

> 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.

Yes, that makes it more flexible. So a zero-length range is a 
pointer to the space between two elements, and a one-length range 
is a pointer to that one element? That is kinda like "C++ 
iterators". C++ begin() could be seen as pointing to the space 
before the first element and end() could be seen as pointing the 
space after the last element. So in a sense, "C++ iterators" are 
zero-length "ranges".

Of course, usually begin() is described as pointing to the first 
element, but that is a matter of wording. It actually makes more 
sense sometimes to think of "C++ iterators" as being pointers to 
the space between elements.