D Ranges in C#

[Steven Schveighoffer]

On Sat, 01 Jun 2013 04:11:59 -0400, bearophile <bearophileHUGS at lycos.com>  
wrote:

> David Piepgrass:

>> In fact, most STL algorithms require exactly two iterators--a  
>> range--and none require only a single iterator<
>
> I think there are some C++ data structures that store many single  
> iterators. If you instead store ranges you double the data amount.

This is true.  In dcollections, I have the concept of cursors.  These are  
1 or 0 element ranges (they are 0 after the first popFront).  For almost  
all cases, they require an extra boolean to designate the "empty" state.

So while not consuming 2x, it's more like 1.5x-ish.  Because of alignment,  
it pretty much requires 2x.  There have been suggestions on utilizing  
perhaps unused bits in the pointer to designate the empty flag, but I'm a  
bit aprehensive on that, especially if the node is GC-managed.

But besides the space requirements the *concept* of a single-element  
pointer is very much needed.  And cursors fill that role.

As an example, std.algorithm.find consumes a range until it finds the  
specific value.  It then returns a range of the remaining data.  But what  
if you wanted the range of the data UNTIL the first value?

In std.container, we have three functions to deal with this, upperBound,  
lowerBound, and equalRange.  But even with these, it can be difficult to  
construct intersections of these two ranges.

In dcollections, we have one function, find, which returns a cursor.  Then  
using the cursor, you can construct the range you need:

auto r = mymap[mymap.find(5)..$]; // opDollar not supported yet, but will  
be.

auto rbefore = mymap[mymap.begin()..mymap.find(5)];

All of this is safe and correct, and I think it reads rather well.

There are other good places where single-element ranges are useful.  It is  
important to note that a cursor is NOT equivalent to a range of one  
element.  Such a range in a node-based container has two node pointers.  A  
cursor MUST only point at exactly one element.  This is important when  
considering cursor invalidation -- removing an element unreferenced by a  
cursor should not invalidate that cursor (depending on how the container  
is structured).  For example, adding a new value to a hash set, or  
removing an unrelated value from a hash set may invalidate all ranges, but  
not cursors.

-Steve