www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - AA.remove in foreach && AA = new vs cleaning

reply "Saaa" <empty needmail.com> writes:
Is there anything with removing the current key in a foreach?

foreach (K k, ; aa)
{
  ..
  aa.remove(k);
}

What if it isn't the current key?
If the iteration is generated on the fly it shouldn't be a problem, right?

&&

Is it better to new an AA or empty(.remove) it on the fly if you loop over 
all the keys anyways?
That is, I need an similar empty AA the next iteration :)
Removing every element takes of course as many operations as keys, but 
filling the array won't take
as many memory allocations, as the gc doesn't return the key allocations. Am 
I making any sense here? :D
Oct 21 2009
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 21 Oct 2009 23:06:47 -0400, Saaa <empty needmail.com> wrote:

 Is there anything with removing the current key in a foreach?

 foreach (K k, ; aa)
 {
   ..
   aa.remove(k);
 }
Yes, behavior is undefined. from http://digitalmars.com/d/2.0/statement.html#ForeachStatement : "The aggregate must be loop invariant, meaning that elements to the aggregate cannot be added or removed from it in the [loop body]" I have gotten around this in dcollections by removing elements outside the loop body. See for example the keypurge function of HashMap (http://www.dsource.org/projects/dcollections/docs/current/dcollections.HashMap.html) -Steve
Oct 21 2009
parent reply "Saaa" <empty needmail.com> writes:
Steven Schveighoffer wrote:
 Yes, behavior is undefined.

 from http://digitalmars.com/d/2.0/statement.html#ForeachStatement :

 "The aggregate must be loop invariant, meaning that elements to the 
 aggregate cannot be added or removed from it in the [loop body]"
I suspect removing the current key isn't a problem in the current implementation; Been using it quite a lot without any problems :) But I've changed everything to new the array afterwards as I deleted all the keys anyways.
 I have gotten around this in dcollections by removing elements outside the 
 loop body.  See for example the keypurge function of HashMap 
 (http://www.dsource.org/projects/dcollections/docs/current/dcollections.HashMap.html)
Do you add the ones to be deleted to a dynamic array or do you loop over all elements afterwards? I expect the first :)
Oct 21 2009
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 22 Oct 2009 00:45:36 -0400, Saaa <empty needmail.com> wrote:

 Steven Schveighoffer wrote:
 Yes, behavior is undefined.

 from http://digitalmars.com/d/2.0/statement.html#ForeachStatement :

 "The aggregate must be loop invariant, meaning that elements to the
 aggregate cannot be added or removed from it in the [loop body]"
I suspect removing the current key isn't a problem in the current implementation; Been using it quite a lot without any problems :)
It may well sometimes work, but it's not defined to work. I've seen instances where it caused problems (i.e. segfaults). You may just not have hit that threshold.
 But I've changed everything to new the array afterwards as I deleted all  
 the
 keys anyways.
Not sure what you mean here.
 I have gotten around this in dcollections by removing elements outside  
 the
 loop body.  See for example the keypurge function of HashMap
 (http://www.dsource.org/projects/dcollections/docs/current/dcollections.HashMap.html)
Do you add the ones to be deleted to a dynamic array or do you loop over all elements afterwards? I expect the first :)
I delete them as they are requested to be deleted. Since the deletion is done by the opApply function, it has knowledge of when it is ok to delete the element, and can save off any necessary structural information needed to get to the next element. It makes for an efficient method to traverse and remove in one pass. -Steve
Oct 21 2009
parent reply "Saaa" <empty needmail.com> writes:
Steven Schveighoffer wrote

 But I've changed everything to `new` the array afterwards as I deleted 
 all  the
 keys anyways.
Not sure what you mean here.
foreach (K k, ; aa) { .. //aa.remove(k); } aa = new int[char];
 I have gotten around this in dcollections by removing elements outside 
 the
 loop body.  See for example the keypurge function of HashMap
 (http://www.dsource.org/projects/dcollections/docs/current/dcollections.HashMap.html)
Do you add the ones to be deleted to a dynamic array or do you loop over all elements afterwards? I expect the first :)
I delete them as they are requested to be deleted. Since the deletion is done by the opApply function, it has knowledge of when it is ok to delete the element, and can save off any necessary structural information needed to get to the next element.
How is this `outside the loop body`? Should I read it as `after the loop body`?
 It makes for an efficient method to traverse and remove in one pass.

 -Steve 
Oct 21 2009
parent reply "Saaa" <empty needmail.com> writes:
Saaa wrote:
 Steven Schveighoffer wrote

 But I've changed everything to `new` the array afterwards as I deleted 
 all  the
 keys anyways.
Not sure what you mean here.
foreach (K k, ; aa) { .. //aa.remove(k); } aa = new int[char];
Error: new can only create structs, dynamic arrays or class objects So, what is the fastest way to clean an AA?
Oct 21 2009
next sibling parent "Saaa" <empty needmail.com> writes:
 So, what is the fastest way to clean an AA?
dsource tutorials to the rescue : loop over all keys and remove. Now I understand the AA discussion on .D :)
Oct 22 2009
prev sibling next sibling parent Rainer Deyke <rainerd eldwood.com> writes:
Saaa wrote:
 So, what is the fastest way to clean an AA? 
int[char] tmp; aa = tmp; -- Rainer Deyke - rainerd eldwood.com
Oct 22 2009
prev sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 22 Oct 2009 02:59:13 -0400, Saaa <empty needmail.com> wrote:

 Saaa wrote:
 Steven Schveighoffer wrote

 But I've changed everything to `new` the array afterwards as I deleted
 all  the
 keys anyways.
Not sure what you mean here.
foreach (K k, ; aa) { .. //aa.remove(k); } aa = new int[char];
Error: new can only create structs, dynamic arrays or class objects So, what is the fastest way to clean an AA?
aa = null; However, if you have multiple copies of the AA, this does not clear out the data. It merely resets the AA reference. I'd not trust your code because it's undefined behavior. If you want to remove all the elements individually, copy the keys to an array, then iterate over the array removing each element. Or use a real collection class, such as Tango's or dcollections' and use the clear() method :) -Steve
Oct 22 2009
parent reply "Saaa" <empty needmail.com> writes:
Steven Schveighoffer wrote:
 So, what is the fastest way to clean an AA?
aa = null;
:(
 However, if you have multiple copies of the AA, this does not clear out 
 the data.  It merely resets the AA reference.

 I'd not trust your code
:)
 because it's undefined behavior.  If you want to  remove all the elements 
 individually, copy the keys to an array, then  iterate over the array 
 removing each element.
This is what the dsource example does, it loops over a copy of all the keys :) foreach(K key; aa.keys) aa.remove(key);
 Or use a real collection class, such as Tango's or dcollections' and use 
 the clear() method :)

 -Steve
As nulling is all it takes I don't think it's that much faster :)
Oct 22 2009
parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 22 Oct 2009 19:58:40 -0400, Saaa <empty needmail.com> wrote:

 Steven Schveighoffer wrote:
 So, what is the fastest way to clean an AA?
aa = null;
:(
 However, if you have multiple copies of the AA, this does not clear out
 the data.  It merely resets the AA reference.

 I'd not trust your code
:)
 because it's undefined behavior.  If you want to  remove all the  
 elements
 individually, copy the keys to an array, then  iterate over the array
 removing each element.
This is what the dsource example does, it loops over a copy of all the keys :) foreach(K key; aa.keys) aa.remove(key);
If this works, it means that aa.keys returns a copy of the keys from aa, not a lazy view of the keys. This makes it less efficient, but makes the removal possible. In dcollections, the map keys property returns an iterator over the keys of the object. It is a live view, so there is no copy of the keys, so running code like this for a dcollections HashMap for instance, would result in undefined behavior. However, dcollections provides a way to safely iterate over a map and remove individual elements: foreach(ref dopurge, k, v; hashmap) { if(shouldRemove(k, v)) dupurge = true; }
 Or use a real collection class, such as Tango's or dcollections' and use
 the clear() method :)

 -Steve
As nulling is all it takes I don't think it's that much faster :)
As I said, nulling only clears the reference. You could do the same thing with a container class. Here is an example: int[int] aa1; aa1[0] = 0; auto aa2 = aa1; aa1 = null; // does not clear aa2, all the data is still there. Now, replace line one with auto aa1 = new HashMap!(int, int); And the same rules apply. Except aa1.clear() will clear out *the elements* of aa1 and aa2. That's what I was talking about. -Steve
Oct 23 2009