Grokking std.container and Ranges
Steven Schveighoffer
schveiguy at yahoo.com
Tue Jun 29 05:00:33 PDT 2010
On Mon, 28 Jun 2010 23:01:42 -0400, Mike Parker <aldacron at gmail.com> wrote:
> I thought I understood ranges until I actually started trying to use
> them. Now I'm having difficulties with the new range-based containers.
> So I've got two issues right now, grokking ranges and understanding the
> container interfaces.
>
> Given an SList, I want to do the following:
>
> foreach(obj; list)
> {
> if(obj.pleaseKillMe)
> somehow_remove_the_object_from_the_list();
> }
>
> Part of my problem is I'm not entirely clear what's going on with the
> foreach. I know it's iterating a range, but is it the SList itself being
> iterated, or is it a range returned by SList.opSlice? I assume the
> latter, which at one point led me to try this (thinking of Java's
> iterator.remove()):
>
> auto r = list[];
> foreach(obj; r)
> {
> if(obj.pleaseKillMe)
> r.popFront();
> }
>
> Which, of course, didn't work. I see that popFront doesn't actually
> 'pop' anything off of, or out of, the range as it would in a traditional
> stack or a queue. The foreach doc says about range.popFront:
>
> move the left edge of the range right one
>
> Meaning, it's more like a next() than the pop() I'm familiar with
> (recalibrating all those years of C and Java terminology is not easy).
> And even if it did, changes to the range do not propagate to the
> underlying container. I understand that, at least (now).
>
> So apparently I want something like the list.stableRemove*() variants,
> which the docs say remove an item from a container without invalidating
> any ranges currently iterating the container. Great! Only, there's no
> variant that accepts a single item. SList has removeFront and removeAny,
> and ranges can be removed via linearRemove. I can insert individual
> items fine. But how do I remove them?
linearRemove is it for SList. Sucks, but that's what's available, until
Andrei can figure out a better way to remove a range.
With a singly linked list, you can't remove the front of a range, because
you have to alter the element *before* the front element. What SList
needs is a function to allow removing all but the *first* element in the
range. Something like removeTail. I think it would be an SList-specific
function, not much use outside there.
Anything you use will have to avoid foreach, removing elements from
anything while using foreach on that thing is not a good idea (unless the
foreach is doing it for you, see below). You have to manually handle the
ranges.
You may want to give dcollections a try. They support purging (the
operation you are trying to write) natively with foreach via opApply. The
linked list is dual-linked, so there are no issues with removing arbitrary
elements (removal of a single element is an O(1) operation):
LinkList!T list;
...
foreach(ref doPurge, obj; &list.purge)
{
doPurge = obj.pleaseKillMe;
}
http://www.dsource.org/projects/dcollections
Please note, the online docs are D1 only, the D2 docs are included in the
distribution, but aren't as pretty.
-Steve
More information about the Digitalmars-d-learn
mailing list