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

[Ola Fosheim Grøstad]

On Monday, 14 June 2021 at 16:29:09 UTC, Steven Schveighoffer 
wrote:
> 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.

Was that because it was harder to do for red-black-trees?

I have been toying with chunked containers that allows fast 
transfers of ranges of objects from one container type to another.

The basic idea being that you could have a queue and then quickly 
transfer the whole queue to a B-tree or maybe the first 100 
objects of the queue to the middle of a deque.

But it is challenging to come up with a chunk type that works 
equally well for many container types. So I limit it to 
sequential container types. Then have links between the chunks 
(so basically a linked list of small arrays). That way I can have 
one iterator type that works for all container types.

I would also like to make it possible to have table pointers that 
doesn't become invalidated when moving a chunk, but how to do 
this if they point to the space between elements and not the 
element itself? Like if it points to the space between two chunks 
and you move the chunk after to a new container then the table 
pointer would move to the new container as well (or the 
implementation would be inefficient).

Seems like the semantics of pointing to elements instead of the 
space between elements is more robust for this kind of container 
semantics. So, when you mutate then the distinction between 
pointing to or between elements become significant.

Also, it then becomes important to figure out whether table 
pointers point to one specific container or the content and how 
the table pointers can be implemented efficiently (time and 
space).