std.container & ranges

[Steven Schveighoffer]

On Sun, 30 Oct 2011 06:38:30 -0400, Max Wolter <awishformore at gmail.com>  
wrote:

> Hello there.
>
> I seem to be having problems wrapping my head around how to use the  
> ranges in the context of containers in phobos. Specifically, I can't  
> seem to figure out how to remove an element from a linked list.
>
>           foreach(cell; organism)
>           {
>              if(cell.x == x && cell.y == y)
>              {
>                 organism.stableLinearRemove(cell);
>                 break;
>              }
>           }
>
> mind.d(123): Error: function  
> std.container.SList!(Cell).SList.linearRemove (Range r) is not callable  
> using argument types (Cell)
> mind.d(123): Error: cannot implicitly convert expression (cell) of type  
> cell.Cell to Take!(Range)
>
> I somehow get the feeling such a basic operation should just...work?

I offer an alternative collection library to std.container which has a  
simpler (IMO) interface and features.

There is specifically a feature for removal during iteration.  It would  
look like this:

foreach(ref doRemove, cell; &organism.purge)
{
    doRemove = cell.x == x && cell.y == y; // flag indicating the current  
element should be removed
    // note, not necessary to break here
    if(doRemove)
       break;
}

Note two things, removal during iteration is directly supported, meaning  
it does not derail the iteration; and removal during iteration is a quick  
operation (O(lg(n)) or better) in terms of the individual removal.

If you have a linked list, you can also do it the "range" way:

organism.remove(find!((a){return a.x == x && a.y ==  
y;})(organism[]).begin);

begin is an accessor for a dcollections range that returns a reference  
(cursor) to the first element in the range.

Note also that dcollections' linked list is doubly-linked, so removal is  
O(1).

-Steve