2
$\begingroup$

I have a data structure that implements the following operations all in $O(1)$:

  • $\text{insert(x)}$, inserts a value into the data structure and returns a unique key $k$ to the value
  • $\text{delete(k)}$, deletes the value at key $k$ and returns it
  • $\text{get(k)}$, returns a reference to the element at key $k$

Internally the storage is simply a contiguous array $A$ of $(x, v)$ tuples. $x$ is either a value or is used to store a freelist. $v$ is a version tag. When $v$ is odd $x$ is a valid item with version $v$. When $v$ is even $x$ is unoccupied and is re-used to store the index of the next unoccupied item after this.

The key $k$ is a tuple of $(i, v)$, an index into the contiguous array and a version. Only when $A[k_i]_v = k_v$ is this key valid and contained in the data structure. Finally, on every insert and delete $A[i]_v$ is incremented.

Now this is very similar to a memory allocator (which returns pointers instead of keys), but the difference is that physical memory locations can be safely re-used here without spurious errors where old pointers point to new items. So from the perspective from the user every key that $\text{insert}$ ever gives is unique.

The question is, what is a good name for this data structure? I've seen similar data structures called "slot maps" in game development, but it's not quite the same. They don't use versioning and support dense iteration through using two indirections (one key -> idx and idx -> item), whereas this data structure can have a sparse memory layout.

It's also very similar to a slab allocator, but again it has added safety of returning permanently unique keys, even when re-using storage.

$\endgroup$
0
$\begingroup$

I ended up settling for Sparse Slot Map. I was wrong to say that slot maps don't do versioning - that depends on the implementation.

$\endgroup$
  • $\begingroup$ Would love to see it if you have an open source implementation or something! Sounds neat! $\endgroup$ – Lance Pollard Jul 3 '18 at 3:31
  • $\begingroup$ @LancePollard github.com/orlp/slotmap $\endgroup$ – orlp Aug 2 '18 at 13:38
0
$\begingroup$

I think what you did is very similar to the data structure described here: https://research.swtch.com/sparse

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.