www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Is removing elements of AA in foreach loop safe?

reply berni <someone somewhere.com> writes:
Iterating of some structure and removing elements thereby is 
always errorprone and should be avoided. But: In case of AA, I've 
got the feeling, that it might be safe:


 foreach (k,v;ways)
     if (v.empty)
         ways.remove(k);


Do you agree? Or is there a better way to achieve this?
Aug 29 2019
next sibling parent Jonathan M Davis <newsgroup.d jmdavisprog.com> writes:
On Thursday, August 29, 2019 4:11:58 AM MDT berni via Digitalmars-d-learn 
wrote:

 Iterating of some structure and removing elements thereby is
 always errorprone and should be avoided. But: In case of AA, I've

 got the feeling, that it might be safe:

 foreach (k,v;ways)

     if (v.empty)

         ways.remove(k);


 Do you agree? Or is there a better way to achieve this?


No, it's not safe to do that. If you insert or remove any elements from an
AA while looping over it, you're going to have weird behavior. If you want
to remove elements in a loop, then you'll need to do something like put each
key that you want to remove in a dynamic array while looping over the AA and
then loop over the dynamic array to remove the elements from the AA.

- Jonathan M Davis
Aug 29 2019
prev sibling next sibling parent reply XavierAP <n3minis-git yahoo.es> writes:
On Thursday, 29 August 2019 at 10:11:58 UTC, berni wrote:

 Iterating of some structure and removing elements thereby is 
 always errorprone and should be avoided. But: In case of AA, 
 I've got the feeling, that it might be safe:


 foreach (k,v;ways)
     if (v.empty)
         ways.remove(k);


 Do you agree? Or is there a better way to achieve this?


It compiles and it runs without throwing any RangeError... So it 
appears to be safe. Otherwise it'd be a bug that there's not 
error.
Aug 30 2019
next sibling parent XavierAP <n3minis-git yahoo.es> writes:
 On Thursday, 29 August 2019 at 10:11:58 UTC, berni wrote:

 Do you agree? Or is there a better way to achieve this?




An alternative would be to reassign the AAA to the output of 
std.algorithm.filter()... but assignment between AAs and Ranges 
isn't so type-direct.
Aug 30 2019
prev sibling parent reply Paul Backus <snarwin gmail.com> writes:
On Friday, 30 August 2019 at 13:43:54 UTC, XavierAP wrote:

 On Thursday, 29 August 2019 at 10:11:58 UTC, berni wrote:

 Iterating of some structure and removing elements thereby is 
 always errorprone and should be avoided. But: In case of AA, 
 I've got the feeling, that it might be safe:


 foreach (k,v;ways)
     if (v.empty)
         ways.remove(k);


 Do you agree? Or is there a better way to achieve this?


 It compiles and it runs without throwing any RangeError... So 
 it appears to be safe. Otherwise it'd be a bug that there's not 
 error.


Whether you actually get an error at runtime depends on the load 
factor of the AA. If it drops below a certain threshold, the AA 
will be resized [1], and its original memory will be freed [2].

[1] 
https://github.com/dlang/druntime/blob/master/src/rt/aaA.d#L631
[2] 
https://github.com/dlang/druntime/blob/master/src/rt/aaA.d#L154
Aug 30 2019
parent reply berni <someone somewhere.com> writes:
On Friday, 30 August 2019 at 15:00:59 UTC, Paul Backus wrote:

 Whether you actually get an error at runtime depends on the 
 load factor of the AA. If it drops below a certain threshold, 
 the AA will be resized [1], and its original memory will be 
 freed [2].


It could still work, depending on how the foreach loop is 
implemented. If the keys were stored away before starting the 
loop it would work. But for one thing, it isn't implemented that 
way and for the other, one shouldn't rely on it, because the 
implementation could change. What I hoped for, was, that the 
specs enforce somewhere, that this is to be implemented in a safe 
manner.

I'll replace this loops by something better, e.g. the mentioned 
filter. But I've never worked with AAs and filters yet. Will see, 
if I manage to do that. Else I'll probably just copy the keys and 
use them for an independent loop.
Aug 30 2019
parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Fri, Aug 30, 2019 at 04:45:20PM +0000, berni via Digitalmars-d-learn wrote:

 On Friday, 30 August 2019 at 15:00:59 UTC, Paul Backus wrote:

 Whether you actually get an error at runtime depends on the load
 factor of the AA. If it drops below a certain threshold, the AA will
 be resized [1], and its original memory will be freed [2].


 
 It could still work, depending on how the foreach loop is implemented.
 If the keys were stored away before starting the loop it would work.
 But for one thing, it isn't implemented that way and for the other,
 one shouldn't rely on it, because the implementation could change.
 What I hoped for, was, that the specs enforce somewhere, that this is
 to be implemented in a safe manner.
 
 I'll replace this loops by something better, e.g. the mentioned
 filter. But I've never worked with AAs and filters yet. Will see, if I
 manage to do that. Else I'll probably just copy the keys and use them
 for an independent loop.


In general, modifying a container (of any kind) while iterating over it
is a bad idea, because it leads to corner cases with counter-intuitive
semantics.  In some cases, it can be made to work if the container
supports deletion of the *current* element being iterated over. But this
requires support from the container.

General insertion/deletion during iteration over a container, generally
speaking, leads to corner cases with "strange" behaviour. The problem is
that iteration order becomes non-obvious once arbitrary changes can
happen during iteration. If you're iterating over elements E1, E2, E3,
etc., and then somebody inserts a new element E, should the current
iteration include E or not?  In an unordered container like an AA, this
becomes an arbitrary choice (depends on implementation details like the
hash function).  If inserting/deleting from a container entails
reorganization, what happens to the order of the ongoing iteration?
Depending on how iteration is implemented, you may end up visiting the
an element more than once, inadvertently skipping over some elements, or
in rare cases end up iterating forever (if the container reorg moves
your current position back while triggering more additions, and
iterating over the added elements triggers a similar reorg).

The basic problem is that the meaning of "iteration" becomes ill-defined
once the container is subject to change in the middle of iteration. The
exact semantics become dependent on the implementation details of the
container, and you basically have to know exactly how the container
works under the hood in order to predict the effects.  When the
implementation details are not known / should not to be known
(encapsulation), this should generally be avoided. It's better to keep a
list of changes in a separate list, and finish the current iteration
first, then apply the changes in the list to the container.


T

-- 
Programming is not just an act of telling a computer what to do: it is also an
act of telling other programmers what you wished the computer to do. Both are
important, and the latter deserves care. -- Andrew Morton
Aug 30 2019
prev sibling next sibling parent Jordan Wilson <wilsonjord gmail.com> writes:
On Thursday, 29 August 2019 at 10:11:58 UTC, berni wrote:

 Iterating of some structure and removing elements thereby is 
 always errorprone and should be avoided. But: In case of AA, 
 I've got the feeling, that it might be safe:


 foreach (k,v;ways)
     if (v.empty)
         ways.remove(k);


 Do you agree? Or is there a better way to achieve this?


This should work, due to the keys property returning a dynamic 
array:

foreach (k; ways.keys) {
     if (ways[k].empty)
         ways.remove(k);
}

Jordan
Aug 30 2019
prev sibling parent reply Ferhat =?UTF-8?B?S3VydHVsbXXFnw==?= <aferust gmail.com> writes:
On Thursday, 29 August 2019 at 10:11:58 UTC, berni wrote:

 Iterating of some structure and removing elements thereby is 
 always errorprone and should be avoided. But: In case of AA, 
 I've got the feeling, that it might be safe:


 foreach (k,v;ways)
     if (v.empty)
         ways.remove(k);


 Do you agree? Or is there a better way to achieve this?


I know, it is foreach loop in question. How about using a reverse 
for loop like:

for (size_t i = arr.length ; i-- > 0 ; ){
     arr.remove(i);
}
Sep 03 2019
parent reply berni <someone somewhere.com> writes:
On Tuesday, 3 September 2019 at 20:06:27 UTC, Ferhat Kurtulmuş 
wrote:

 I know, it is foreach loop in question. How about using a 
 reverse for loop like:

 for (size_t i = arr.length ; i-- > 0 ; ){
     arr.remove(i);
 }


This would be good, if it where for slices. But with associative 
arrays, this doesn't work. :-(
Sep 03 2019
parent Ferhat =?UTF-8?B?S3VydHVsbXXFnw==?= <aferust gmail.com> writes:
On Wednesday, 4 September 2019 at 06:20:00 UTC, berni wrote:

 On Tuesday, 3 September 2019 at 20:06:27 UTC, Ferhat Kurtulmuş 
 wrote:

 I know, it is foreach loop in question. How about using a 
 reverse for loop like:

 for (size_t i = arr.length ; i-- > 0 ; ){
     arr.remove(i);
 }


 This would be good, if it where for slices. But with 
 associative arrays, this doesn't work. :-(


Oh, I am sorry that I missed that point.
Sep 04 2019