www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Grokking std.container and Ranges

reply Mike Parker <aldacron gmail.com> writes:
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?
Jun 28 2010
next sibling parent BCS <none anon.com> writes:
Hello Mike,

 I want to do the following:
 foreach(obj; list)
 {
 if(obj.pleaseKillMe)
 somehow_remove_the_object_from_the_list();
 }

That isn't legal for normal arrays or AAs. IIRC the docs even say that you can't change what a foreach is iterating over during the foreach. I think you will have to convert to a manual for loop to make it work. That said, I've not worked with range at all. -- ... <IXOYE><
Jun 28 2010
prev sibling next sibling parent "Rory McGuire" <rmcguire neonova.co.za> writes:
On Tue, 29 Jun 2010 07:16:13 +0200, BCS <none anon.com> wrote:

 Hello Mike,

 I want to do the following:
 foreach(obj; list)
 {
 if(obj.pleaseKillMe)
 somehow_remove_the_object_from_the_list();
 }

That isn't legal for normal arrays or AAs. IIRC the docs even say that you can't change what a foreach is iterating over during the foreach. I think you will have to convert to a manual for loop to make it work. That said, I've not worked with range at all.

Perhaps keep the foreach and make a list of to be deleted objects and then delete them after the foreach.
Jun 29 2010
prev sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Mon, 28 Jun 2010 23:01:42 -0400, Mike Parker <aldacron 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
Jun 29 2010