D Ranges in C#

[David Piepgrass]

>> 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.
>
> Hashmaps would be the most common example. Usually implemented 
> as a linked list of key-value pairs along with a vector of list 
> iterators.

In theory. But the .NET hashtables are implemented with an 
*array* of key-value pairs and an array of *indexes*. The former 
forms a virtual linked list that is more efficient than a 
traditional linked list, and the latter is more efficient than a 
vector of iterators (especially on x64, as the indexes can be 
32-bit.)

> Iterators are also useful for constructing sub-ranges, which 
> proves useful in the implementation of some algorithms. Writing 
> std::next_permutation in D with ranges is quiet frustrating 
> compared to C++.
>
> https://github.com/D-Programming-Language/phobos/blob/master/std/algorithm.d#L10901
> http://gcc.gnu.org/onlinedocs/gcc-4.6.2/libstdc++/api/a01045_source.html#l03619
>
> Notice that in D you need to maintain a count of the elements 
> popped off the back and then use takeExactly to retrieve that 
> portion again. In C++ you just move the iterators around and 
> create "ranges" from pairs of iterators as you need them.
>
> When I implemented nextPermutation in D, I constantly felt as 
> if I was fighting with ranges instead of working with them - I 
> knew exactly what I wanted to do, but ranges only provide a 
> roundabout way of doing it.

Hmm, very interesting. I suppose the problem with C++ iterators 
is that they are useless without external context: you can't 
increment or decrement one without also comparing it to begin() 
or end() in its container, which implies that the caller must 
manually keep track of which container it came from. Thus, an 
iterator is hardly an improvement over a plain-old integer index, 
the only advantages being

1. You can dereference it (*if* you can be sure it doesn't point 
to end())
2. Unlike an index, it's compatible with non-random-access data 
structures

But perhaps the iterator concept could be improved by being made 
self-aware: if the iterator "knew" and could tell you when it was 
at the beginning or end of its container. This would increase the 
storage requirement in some circumstances but not others. For 
example, an iterator to a doubly-linked list node can tell when 
it is at the beginning or end, but an iterator to a singly-linked 
list node can only tell when it is at the end. A pointer inside 
an array may or may not be able to tell if it is at the end 
depending on how arrays work, e.g. perhaps the way D heap arrays 
work would allow an array iterator, implemented as a simple 
pointer, to still know when it is safe to increment and decrement.

The simplest possible .NET array iterator is an array reference 
plus an index, and again the iterator can know when it is at the 
beginning or end of the array--except that if the iterator came 
from inside a range, it would be unaware of the range's 
boundaries, which may be smaller than the array's boundaries.