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?

Thanks!

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.

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

-Steve

On 9/21/20 11:52 AM, Steven Schveighoffer wrote:
> 1. cursors were never invalidated by removal or addition of items.

This should say "by remove or addition of *other* items"

-Steve

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

On Mon, Sep 21, 2020 at 11:05 PM ikod via Digitalmars-d < digitalmars-d@puremagic.com> wrote:

> Sorry, do you mean - the sources were lost?
>

http://www.dsource.org/projects/dcollections


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

>From my POV I`m ok even with containers where stability is not provide. But
it would be perfect to have containers when I can select between
performance or stability.
I hardly ever need stability from containers, so for me it would be ok to
not guarantee in favor of speed. But still would be nice to have a way to
say that in some cases I prefer stability

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

On Monday, 21 September 2020 at 15:28:24 UTC, ikod wrote:
> For example iterator over emsi containers unrolled list - does it provide any stability warranties?

No. It also doesn't specify stability or instability, so I should probably improve the documentation for that.

On 9/22/20 6:05 PM, Brian Schott wrote:
> On Monday, 21 September 2020 at 15:28:24 UTC, ikod wrote:
>> For example iterator over emsi containers unrolled list - does it provide any stability warranties?
> 
> No. It also doesn't specify stability or instability, so I should probably improve the documentation for that.

Thanks. Problem is, I wrote the code in this manner hoping to get rid of the braces (it had the condition reverse). But not a biggie.

On Monday, 21 September 2020 at 21:27:38 UTC, Daniel Kozak wrote:
> On Mon, Sep 21, 2020 at 11:05 PM ikod via Digitalmars-d < digitalmars-d@puremagic.com> wrote:
>
>> Sorry, do you mean - the sources were lost?
>>
>
> http://www.dsource.org/projects/dcollections
>
>
>> > 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.
>>
>
> From my POV I`m ok even with containers where stability is not provide. But

Sometimes we need to operate on collection while we iterate over it, and it's pity if you have to collect this changes somewhere and then apply in separate action.

> it would be perfect to have containers when I can select between
> performance or stability.

Performance (in terms of execution speed) is also first priority for me.
I can give up some small part of speed in exchange for convenience only when user make some unusual and rare things (like updating collection while iterating over it)


> I hardly ever need stability from containers, so for me it would be ok to
> not guarantee in favor of speed. But still would be nice to have a way to
> say that in some cases I prefer stability

It is possible to make stability configurable.

On Monday, 21 September 2020 at 22:00:36 UTC, Steven Schveighoffer wrote:
> 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:

>
> No, they are still there. Last commit was 2011 (meaningful commit), so I guess not yet 10 years.
>
> https://github.com/schveiguy/dcollections
>

Oh, sorry for confusion )

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

Thanks, I'll check it. If dcollections support fast nogc list - that's all what I need. optionally I need stability.

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