std.collection - changing the collection while iterating

Steven Schveighoffer via Digitalmars-d digitalmars-d at puremagic.com
Mon Jun 22 06:42:41 PDT 2015


On 6/22/15 2:27 AM, Joseph Cassman wrote:
> On Sunday, 21 June 2015 at 23:02:38 UTC, Andrei Alexandrescu wrote:
>> While I work on making std.allocator better, here's some food for
>> thought regarding std.collection.
>>
>> Consider a traditional container with reference semantics, Java-style.
>> Regarding changing the collection (e.g. adding/removing elements)
>> while iterating, we have the following possibilities:
>>
>> 1. Leave it undefined, like the STL does. Probably this is too extreme.
>>
>> 2. Throw an exception if a remove is attempted while ranges exist.
>> This works but it's conservative - e.g. it throws even if those ranges
>> are never to be used again etc.
>>
>> 3. Allow the removal but throw from the ranges if there's any attempt
>> to use a range following a remove.
>>
>> 4. Make it work such that ranges continue to be valid post removal.
>> Perhaps this is on the inefficient side.
>>
>>
>> Andrei
>
> I was trying to understand how it could work with array slices. For
> example, I was thinking of code similar to the following from TDPL p. 103:
>
> import std.conv, std.stdio;
> int main(string[] args) {
>    args = args[1 .. $];
>    while (args.length >= 2) {
>      if (to!int(args[0]) != to!int(args[$ - 1])) {
>        writeln("not palindrome");
>        return 1;
>      }
>      args = args[1 .. $ - 1];
>    }
>    writeln("palindrome");
>    return 0;
> }
>
> Is the slice above considered a range? If so then it seems that (4) is
> already used a lot in existing D code. If it is not, then will slices of
> the possible future library implementation of arrays be considered ranges?
>
> I cannot see all difficulties arising from allowing (4), but I imagine
> code complexity will increase as a result. Perhaps the compiler can
> special case arrays to avoid possible issues making (4) allowable for
> all containers?

No, what Andrei is referring to is modification of the referenced 
structure (not just the elements). In other words, imagine removing 5 
elements from the array while you are doing this iteration, and pushing 
all the other elements up.

Modification of the range itself is not ever going to be illegal! A 
range is for iterating, and if you need to iterate it, you must modify it.

Note also that although the above sample code uses a string which is 
technically a range, it's not used with range primitives (front back, 
popFront, popBack), and really it should be used that way to support UTF.

-Steve


More information about the Digitalmars-d mailing list