Can references to smap elements be invalidated when a different element is erased?

[wmww]

The docs say Iterators are invalidated after insert and erase. References are only invalidated after erase, which implies yes but this wasn't obvious to me from the code.

My usecase is I'm trying to build an insertion order-preserving map on top of an smap (maybe a candidate for including in STC if interested). My idea for how to do that is have elements of the inner smap be a doubly-linked list of values that my insert/erase functions maintain and my iterator iterates through, but this breaks if an erase on the inner smap can invalidate pointers to unaffected elements.

[kmarius]

In short: yes, erasing a different element can invalidate other references. The reason is that during deletion of a non-leaf element, the element (more precisely: the value) is swapped with its predecessor (which must be a leaf), happening here:

STC/include/stc/smap.h

Line 485 in 19db505

d[tn].value = d[tx].value; /* move */

I actually did what you are planning to do, but with a hash map (which suffers from the same invalidation problems). The solution here is to store only pointers to list nodes in the hash map, and let the list do all the (de-)allocations.

Also note that since STCs list is singly linked, it is not possible to erase an element in O(1). I did add a doubly linked list for this reason (well, only the parts that I needed, it might otherwise be broken), but that takes some changes to internal files.

If it is of interest I can try to build a minimal example, it won't be generic though.

Edit: I re-checked, and I actually use this as a hash set, not a map. Iterating over key-value pairs in insertion order might be more difficult.

[wmww]

Thanks! Seems like the extra layer of allocation is the best option. I was planning to make my own list, and make the whole thing generic.