4 ms·
Sounds very cool! How do you implement efficient random deletes?
by ntonozzi 2y ago
Sounds very cool! How do you implement efficient random deletes?
- eru 2y agoThe current implementation doesn't. You could add that functionality via 'tombstones': when you delete an element, you replace it with a 'tombstone' marker in the structure. Whenever you clean up the structure (eg for a resize), you skip the tombstones when you copy the old contents over.
- dzaima 2y agoThat'd break arbitrary reads being contiguous O(1) though.
- eru 2y agoYes, that's true. Though you could still access front and back in amortised O(1).
- bobmcnamara 2y agoThere's a similar data structure sometimes seen in video games that does this, but the name escapes me.
- sensen7 2y agoYou're probably thinking of "slabs" or "slotmaps"
- oasisaimlessly 2y agostd::vector doesn't support efficient random deletes, so this (a generalization of std::vector along one specific axis) won't either. Efficient random deletes and contiguous hole-free storage are completely at odds with each other.
- sensen7 2y agoThey aren't: https://github.com/GossiperLoturot/densemap https://github.com/GossiperLoturot/densemap
- wffurr 2y agoThat’s a map, not an indexed array, and it’s slower than Vec across the board per its own benchmarks.
- sensen7 2y agoYes, it's a map that provides efficient random deletes and contiguous hole-free storage, proving that they are not completely at odds with each other. If you don't care about the map part, you can get the same behavior by just moving the last element in the place of the newly removed element. This invalidates all indices, which is what the DenseMap's overhead is meant to avoid, but Vec's remove also invalidates indices. Vec's remove is strictly worse except that it preserves the ordering if the Vec is sorted.
- oasisaimlessly 2y agoYou can't refer to this collection via a slice (std::span / &[T]), so it's not what I meant when I said "contiguous hole-free storage".