std.collection - changing the collection while iterating

[Steven Schveighoffer via Digitalmars-d]

On 6/21/15 10:55 PM, Andrei Alexandrescu wrote:
> On 6/21/15 7:31 PM, Steven Schveighoffer wrote:
>> On 6/21/15 7:02 PM, 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.
>>
>> I don't think it's undefined, it depends on the container:
>>
>> http://www.cplusplus.com/reference/set/set/erase/
>>
>> "Iterators, pointers and references referring to elements removed by the
>> function are invalidated. All other iterators, pointers and references
>> keep their validity."
>
> "Invalidated" = undefined. The point is to make it a hard error when
> trying to use an invalidated range. -- Andrei

No, that's not why I quoted it.

An iterator remains valid as long as its target hasn't been removed. For 
instance:

std::set<int> s;
s.insert(1);
s.insert(2);
s.insert(3);
auto beg = s.begin();
auto end = s.end();
s.erase(s.find(2));
// beg and end are still valid because they weren't removed

while(beg != end) {
std::cout << *beg << " ";
beg++;
}

outputs 1 3

So I don't think removing elements should invalidate ranges that do not 
refer to removed elements. Should such ranges that get invalidated throw 
an error? Would be very nice but potentially costly. Perhaps in some 
debug mode? It may be a case of using the right allocator.

I can't imagine using certain containers, e.g. linked lists, without the 
ability to remove while maintaining pointers to certain elements.

-Steve