iterator stability for containers
igor.khasilev at gmail.com
Mon Sep 21 21:01:23 UTC 2020
On Monday, 21 September 2020 at 15:52:03 UTC, Steven
> On 9/21/20 11:28 AM, ikod wrote:
>> I'd like to know if there are any iterator stability rules for
>> dlang containers?
>> For example iterator over emsi containers unrolled list - does
>> it provide any stability warranties?
>> Or any other containers?
> In dcollections (which is over 10 years past bitrotting), a
> major focus of mine was to ensure stability when possible.
Sorry, do you mean - the sources were lost?
> Therefore, I had a few nice properties:
> 1. cursors were never invalidated by removal or addition of
> 2. ranges could be invalidated, but for certain containers,
> ranges would be invalidated only if the items being removed
> were the endpoints of the ranges.
> 3. Removing items from a hash based container wouldn't rehash
> (to avoid iteration issues).
I don't know if my solution is correct but I solved this by
creating "immutable" copy of hashmap buckets array at the moment
when user decided to mutate hash table while iterator is active.
Iterator continue to walk over this immutable copy and user is
free to change main table. So this works like "copy on write" and
provide stable byKey/Value/Pair ranges.
> 4. All containers supported removal while iterating via a
> special foreach mechanism.
> Honestly, my impetus for creating dcollections was to reproduce
> some of the nice features of iterators in C++, including
> removal while iterating.
I have problems with stable and performant iterator over unrolled
linked list, so I'm looking around for available solutions.
More information about the Digitalmars-d