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