iterator stability for containers

Steven Schveighoffer schveiguy at gmail.com
Mon Sep 21 22:00:36 UTC 2020


On 9/21/20 5:01 PM, ikod wrote:
> 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?

No, they are still there. Last commit was 2011 (meaningful commit), so I 
guess not yet 10 years.

https://github.com/schveiguy/dcollections

What I meant was simply that I haven't touched it in a long time, and it 
likely would be a bit of work to get it working again. For sure there is 
no dub file.

> 
>> 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.

This requires a lot of recordkeeping, but is a reasonable solution. I 
wanted to avoid too much of this. I provided a primitive that you can 
always check if a cursor or range belongs to a container.

I *think* I had experimented at one point with keeping a revision count, 
and throwing if you tried to iterate something that was no longer at the 
same revision. But I don't remember if that ever made it into any 
versions. Maybe that was a different project...

>> 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.

Technically, dcollections doesn't have unrolled linked lists. But the 
default allocator allocates a page-worth of nodes, which are assigned in 
order from the block, so it should be pretty cache friendly.

If there is any interest, I can accept PRs to resurrect it or put it 
into code.dlang.org.

-Steve


More information about the Digitalmars-d mailing list