So, I need a data structure that would support the following operations:
- Add an element to the structure and get some "handle" for that element
- Retrieve an element by a handle
- Remove an element by a handle
- Iterate over all elements
Note that the elements are not expected to have any particular order in iteration. Preferably it should also be cache-friendly and don't use too many memory allocations. The language I have in mind is C++, if that matters.
A doubly-linked list satisfies the requirements (with a "handle" being just a pointer/iterator to a list node). However,
- It uses a memory allocation per each new element, which is a bit too much
- Iteration over a list is extremely cache-unfriendly (as compared to e.g. iteration over contiguous array)
Another possible implementation is to use a hand-written slab allocator over a contiguous chunk of memory, with each cell being either free of occupied. Occupied cells store the actual elements, while free cells maintain a singly-linked list of free cells by storing the index of the next cell in the list (or some predefined null value to mark the end of the list). A "handle" in this case would be an index of a cell. Coupled with some extra per-cell data to decide whether a cell is free or occupied, and an index of the head of the list of free cells, this structure allows
- Fast amortized insertion: put the new element to the head of the list of free cells, updating the head index (and reallocating the cells array if no free cell is available)
- Fast element access (just an index into array)
- Fast removal: add the element's cell to the list of free cells
- Fast iteration: iterate over an array, checking if the current cell is occupied
However, I am not entirely happy with this solution, since
- It has to explicitly maintain the cells state (free/occupied) - this is mostly a technical inconvenience and not a serious issue
- Iteration is still not branch-predictor-friendly (due to checking whether the cell is free or occupied) and might waste a lot of time skipping free cells (thanks to Andrej Bauer for pointing this explicitly), so it is an improvement only if the number of free cells is sufficiently low.
Yet another solution is to implement any kind of binary key-value tree stored inside a contiguous array (auto-expanding, like
std::vector), with array indices used instead of tree node pointers, and keys serving as handles for element access/removal (their only purpose being implementing handles). This way we have
- Amortized $O(\log n)$ insertion - append a tree node to the end of the array, altering the tree structure accordingly (or even $O(1)$ if the tree supports $O(1)$ insertion to the end, like a splay tree, - the data structure generates keys itself, so it can guarantee that they only increase for new elements)
- Amortized $O(\log n)$ removal - remove the node from the tree structure, then swap it with the last node in the array (fixing the indices stored in the last node's children and parent), and decrement the array size
- $O(\log n)$ element access via the tree structure on keys
- Ideal iteration: simply iterate over the whole array (even better if we keep values in a separate array, synchronized with the array for the tree structure, since the latter is not needed for iteration)
This solution trades iteration speed for $O(\log n)$ other operations.
I am mostly interested in increasing the iteration performance, while still retaining fast amortized insertion/deletion. I'm ok with spending some extra $O(n)$ memory, shall the need arise.
So, here's my question: are there better options for a data structure with these requirements?