iterator stability for containers
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:
>>> I'd like to know if there are any iterator stability rules for dlang
>>> 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.
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
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
> 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
More information about the Digitalmars-d