iterator stability for containers

[ikod]

On Monday, 21 September 2020 at 15:52:03 UTC, Steven 
Schveighoffer wrote:
> On 9/21/20 11:28 AM, ikod wrote:
>> Hello,
>> 
>> 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 
> items.
> 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.

Agree totally.

I have problems with stable and performant iterator over unrolled 
linked list, so I'm looking around for available solutions.

>
> -Steve