D Ranges in C#

[Mehrdad]

On Saturday, 1 June 2013 at 16:30:05 UTC, David Piepgrass 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.
>>
>> 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 usually (but not always) faster, as they don't have 
an extra level of indirection involved -- the iterators tell you 
directly where to look in memory, whereas indices are useless 
without containers (or iterators) backing them.


You shouldn't be using 32-bit indices on x64, that defeats the 
whole point of x64.


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


No, that's exactly the opposite of what happens.

The caller just accepts two iterators (like std::unique), so that 
it has the end iterator as well as the begin iterator.