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