Hash Tables in D

Steven Schveighoffer via Digitalmars-d-announce digitalmars-d-announce at puremagic.com
Thu Jan 7 06:11:14 PST 2016


On 1/7/16 7:26 AM, Adrian Matoga wrote:
> On Sunday, 3 January 2016 at 19:29:05 UTC, Martin Nowak wrote:
>> There is a bug.
>>
>> You should never do this b/c of iterator/range invalidation.
>>
>> foreach (key; aa.keys)
>>     aa.remove(key);
>
> I've recently hit this when trying to remove some of the elements from
> an AA while iterating over it. It's easy to forget that it is not
> allowed, especially when working on more complex algorithms.
> Accidentally, it worked all fine even with large data sets with DMD
> 2.069, but with GDC mysterious segfaults appeared - the first thought in
> such case was obviously a bug in GDC or in the older front-end.
>
> However, this is a very convenient, natural and intuitive syntax for
> something that is needed quite frequently, yet this code breaks silently
> in non-predictable ways.
> There are already registered issues concerning this (or similar with
> insertion) problem, including:
>
> https://issues.dlang.org/show_bug.cgi?id=4179
> https://issues.dlang.org/show_bug.cgi?id=2255
> https://issues.dlang.org/show_bug.cgi?id=10821
> https://issues.dlang.org/show_bug.cgi?id=10876
> https://issues.dlang.org/show_bug.cgi?id=13903
>
> I've personally encountered segfaults, infinite loops, programs
> producing incorrect results. Some solutions to this were proposed in the
> bug reports - either:
> a) explicitly allow removing during iteration, and make sure it always
> works, or
> b) explicitly disallow removing during iteration, and always throw an
> Error whenever it is attempted. In some cases it could even be
> detectable in compile time.
>
> And I don't mean including a single sentence about this somewhere in the
> docs. I mean an error reported by the compiler and/or runtime. The
> runtime checks could be disabled for -release, but there should be at
> least an option to detect such errors.
> Probably the worst part of it is that you're free to wrap it in @safe,
> while it's not safe at all.
>

With dcollections [1] I had a feature called "purging" where you would 
iterate over a collection like this:

foreach(ref bool removeIt, int val; collection)
{
    if(someCondition) removeIt = true;
}

The entire reason for this is because you can do something similar in 
C++ containers, and I found it absolutely annoying that the existing 
container classes don't allow this. A very frequent use of containers is 
to iterate through picking which ones should be removed (think of a cache)

-Steve

[1] http://schveiguy.github.io/dcollections/


More information about the Digitalmars-d-announce mailing list