RFC on range design for D2

[Andrei Alexandrescu]

Steven Schveighoffer wrote:
> "Andrei Alexandrescu" wrote
> <snip>
> 
> Excellent ideas!  I think the best part is about how you almost never need 
> individual iterators, only ever ranges.  Perfectly explained!
> 
> One issue that you might not have considered is using a container as a data 
> structure, and not using it for algorithms.  For example, how would one 
> specify that one wants to remove a specific element, not a range of 
> elements.  Having a construct that points to a specific element but not any 
> specific end element might be a requirement for non-algorithmic reasons.

I'm sure you know and imply this, but just to clarify for everybody: 
Modifying the topology of the container is a task carried by the 
primitives of the container. Ranges can "look" at the topology and 
change elements sitting in it, but not alter the topology.

Much like in STL, there's a container primitive for removing a range. It 
will return a range too, namely the range starting at the deleted 
position. Removing an element is really removing a range of one element 
- just a particular case.

> Also, some ranges might become invalid later on whereas the iterators would 
> not.  Take for example a Hash container.  If you have to rehash the table, a 
> range now might not make any sense, as the 'end' element may have moved to 
> be before the 'begin' element.  But an iterator that points to a given 
> element will still be valid (and could be used for removal).  In fact, I 
> don't think ranges make a lot of sense for things like Hash where there 
> isn't any defined order.  But you still should have a 'pointer' type to 
> support O(1) removal.

Iterators can be easily defined over hashtables, but indeed they are 
easily invalidated if implemented efficiently.

> One doesn't see any of these problems with arrays, because with arrays, you 
> are guaranteed to have contiguous memory.
> 
> What I'm trying to say is there may be a reason to have pointers for certain 
> containers, even though they might be unsafe.

A pointer to an element can be taken as &(r.first). The range may or may 
not allow that, it's up to it.

> My personal pet peeve of many container implementations is not being able to 
> remove elements from a container while iterating.  For example, I have a 
> linked list of open file descriptors, iterate over the list, closing and 
> removing those that are done (which should be O(1) per removal).  In many 
> container implementations, iteration implies immutable, which means you have 
> to add references to the elements to remove to another list to then remove 
> afterwards (somtimes at the cost of O(n) per removal.  grrrr.)  I hope 
> ranges will support removal while traversing.

In STL removing from a list while iterating is easy and efficient, 
albeit verbose as always:

list<Filedesc> lst;
for (list<Filedesc>::iterator i = lst.begin(); i != lst.end(); )
{
     if (should_remove) i = lst.erase(i);
     else ++i;
}

In Phobos things will be something like:

List!(Filedesc) lst;
for (auto r = lst.all; !r.isEmpty; )
{
     if (should_remove) r = lst.erase(take(1, r));
     else r.next;
}


Andrei