How to correctly check if set contains an element?

[asmorodinov]

Hello, from the benchmark code I figured out that this seems to be the way to check if set contains an element:

bool res = set.find(i + 1).leaf();

However, the following code seems to work incorrectly

for (int i = 0; i < 32; ++i) {
    set.insert(i);
    assert(!set.find(i + 1).leaf());
}

Here, assert fails at i = 31. This is very strange, since we never inserted i+1 into the set, so it should not be present in it. Is this a bug? Or am I doing something wrong?

[philsquared]

Hi, Thanks for trying this out. Unfortunately I only ever got as far as implementing enough to support my talk on the subject and it still has many rough edges, incomplete interface and, yes, likely many bugs. Shortly after the author of Immer said that a phamt container was going in (although I can't seem to find it there now), so I didn't spend any more time on it.

[asmorodinov]

Hello, thanks for the quick response and clarification in the comments and in the readme file. Also thanks for the talk, it was very interesting to watch!

Immer is indeed quite a nice library as it implements many persistent and immutable data structures (sets, maps, arrays, etc), and I ended up using it.

It seems that current implementation of set uses CHAMP data structure, which appears to be an improved HAMT (there is a nice article on this topic with reference to original paper). I have not found any information about it in the immer documentation, only in the code, however (maybe because this is considered to be an implementation detail). It also seems that their 2017 paper and CppCon talk describe only persistent vector structure (with RRB Trees), although I might be wrong here.