digitalmars.D.learn - efficient and safe way to iterate on associative array?
- aki (23/23) Mar 04 2016 Is it okay to modify associative array while iterating it?
- Minas Mina (5/28) Mar 04 2016 I think what you can do is extract its contents to an array,
- JR (5/10) Mar 04 2016 You can populate an array of key values (here string, so
- Mike Parker (6/28) Mar 04 2016 It is not safe to modify an aa when iterating with .byKey,
- Steven Schveighoffer (10/33) Mar 04 2016 You cannot add or remove keys. You can modify values for existing keys.
- aki (19/29) Mar 04 2016 Thank you for it. Now I know.
Is it okay to modify associative array while iterating it? import std.stdio; void main() { string[string] hash = [ "k1":"v1", "k2":"v2" ]; auto r = hash.byKeyValue(); while(!r.empty) { auto key = r.front.key; auto value = r.front.value; r.popFront(); writefln("key=%s, value=%s", key, value); // may not modify 'hash' here ? hash = null; } } I guess probably it's not. Then, my question is are there an efficient and safe way to iterate on an associative array even if there are possibility to be modified while iterating? I'm writing interpreter and want to make my language to be safe; even malicious script cannot fall it in 'core dump' state. It is okay if it causes undefined behavior like throw or instant exit from loop, but not crash. Thanks, Aki.
Mar 04 2016
On Friday, 4 March 2016 at 13:53:22 UTC, aki wrote:Is it okay to modify associative array while iterating it? import std.stdio; void main() { string[string] hash = [ "k1":"v1", "k2":"v2" ]; auto r = hash.byKeyValue(); while(!r.empty) { auto key = r.front.key; auto value = r.front.value; r.popFront(); writefln("key=%s, value=%s", key, value); // may not modify 'hash' here ? hash = null; } } I guess probably it's not. Then, my question is are there an efficient and safe way to iterate on an associative array even if there are possibility to be modified while iterating? I'm writing interpreter and want to make my language to be safe; even malicious script cannot fall it in 'core dump' state. It is okay if it causes undefined behavior like throw or instant exit from loop, but not crash. Thanks, Aki.I think what you can do is extract its contents to an array, iterate it and modify it as you like, and then insert back to another associative array. I don't think it's efficient but I don't know if it's possible to do something else.
Mar 04 2016
On Friday, 4 March 2016 at 14:16:55 UTC, Minas Mina wrote:On Friday, 4 March 2016 at 13:53:22 UTC, aki wrote: I think what you can do is extract its contents to an array, iterate it and modify it as you like, and then insert back to another associative array. I don't think it's efficient but I don't know if it's possible to do something else.You can populate an array of key values (here string, so string[]) of the entries to delete, then iterate through it afterwards and call .remove to clean up. http://dpaste.dzfl.pl/b63a8e8e5c3b
Mar 04 2016
On Friday, 4 March 2016 at 13:53:22 UTC, aki wrote:Is it okay to modify associative array while iterating it? import std.stdio; void main() { string[string] hash = [ "k1":"v1", "k2":"v2" ]; auto r = hash.byKeyValue(); while(!r.empty) { auto key = r.front.key; auto value = r.front.value; r.popFront(); writefln("key=%s, value=%s", key, value); // may not modify 'hash' here ? hash = null; } } I guess probably it's not. Then, my question is are there an efficient and safe way to iterate on an associative array even if there are possibility to be modified while iterating? I'm writing interpreter and want to make my language to be safe; even malicious script cannot fall it in 'core dump' state. It is okay if it causes undefined behavior like throw or instant exit from loop, but not crash.It is not safe to modify an aa when iterating with .byKey, .byValue, or .byKeyValue. You can safely do it with .keys and .values, but these allocate so it isn't likely to be the most efficient. Your best bet if it's something you need to do frequently is probably what JR recommended.
Mar 04 2016
On 3/4/16 8:53 AM, aki wrote:Is it okay to modify associative array while iterating it? import std.stdio; void main() { string[string] hash = [ "k1":"v1", "k2":"v2" ]; auto r = hash.byKeyValue(); while(!r.empty) { auto key = r.front.key; auto value = r.front.value; r.popFront(); writefln("key=%s, value=%s", key, value); // may not modify 'hash' here ? hash = null; } } I guess probably it's not. Then, my question is are there an efficient and safe way to iterate on an associative array even if there are possibility to be modified while iterating? I'm writing interpreter and want to make my language to be safe; even malicious script cannot fall it in 'core dump' state. It is okay if it causes undefined behavior like throw or instant exit from loop, but not crash. Thanks, Aki.You cannot add or remove keys. You can modify values for existing keys. Note, in your code, this would not cause a problem, since setting hash to null just removes the reference from the local variable 'hash', it does not alter the AA in any way. In dcollections, all containers support "purging", or iterating through elements, removing the current element if desired before moving to the next. But I haven't touched this library in ages, I don't know if it still compiles even. -Steve
Mar 04 2016
On Friday, 4 March 2016 at 16:46:35 UTC, Steven Schveighoffer wrote:You cannot add or remove keys. You can modify values for existing keys. Note, in your code, this would not cause a problem, since setting hash to null just removes the reference from the local variable 'hash', it does not alter the AA in any way. In dcollections, all containers support "purging", or iterating through elements, removing the current element if desired before moving to the next. But I haven't touched this library in ages, I don't know if it still compiles even. -SteveThank you for it. Now I know. I will copy and modify AA source to customize. (src/rt/aaA.d) I wonder what if D support safe variant like safeByKeyValue. Actually it seems easy (in aaA.d): bool _aaRangeEmpty(Range r) { return r.impl is null || r.idx == r.dim; } can be changed to: bool _aaRangeEmptySafe(Range r) { if(r.impl is null || r.idx >= r.dim) return true; if (!r.buckets[r.idx].filled) throw xxxException(); return false; } It can become safe by a cost of small overhead. -- Aki.
Mar 04 2016