3 ms·
The current implementation doesn't. You could add that functionality via 'tombstones': when you delete an element, you replace it with a 'tombstone' marker in
by eru 2y ago
The 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"