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

[Steven Schveighoffer]

On 6/14/21 12:02 PM, Ola Fosheim Grøstad wrote:
> 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:

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

Yes, this is how dcollections worked. Except dcollections cursors were 
slightly more tied to an element than C++ iterators. In fact, 
re-examining the implementation, I made some mistakes which I never 
addressed.

My concept was that a cursor points either an element or *one past* the 
element. So popFront'ing a cursor doesn't move past the element to the 
next element, it moves to the space beyond the element. The awesome 
thing this enables is that you have a choice of both before and after 
the element, without having to refer to the next element at all (and 
things like rearranging or inserting elements do not affect the cursor's 
viability).

However, in particular the red-black-tree based sets/maps just used the 
Node pointer as-is for slicing, regardless of whether it was empty or 
not. Which is very much not correct according to the concept. But I 
haven't touched the code or used it in over a decade, so I'm not sure if 
I'll ever fix that.

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

Yes, it's pointing at the boundaries. That's what makes them composable.

-Steve