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?

  • $\begingroup$ Which of the operations do you expect to work faster with your suggestion, in comparison with using a linked list and standard allocation of memory that your programming language provides? Note that in your suggested solution iteration need not be fast, as it may waste a lot of time skipping over empty cells (and must always scan the entire block). $\endgroup$ – Andrej Bauer Nov 26 '20 at 9:39
  • $\begingroup$ @AndrejBauer Thanks for your comment, I'll update the question. I'm mostly concerned with the iteration performance (while still keeping insert/remove O(1)). $\endgroup$ – lisyarus Nov 26 '20 at 9:43
  • $\begingroup$ A linked list satisfies your requirements because allocations are amortized O(1). Is this really about cache? Do you know that your list fits in cache? $\endgroup$ – Andrej Bauer Nov 26 '20 at 9:48
  • $\begingroup$ @AndrejBauer Iteration over linked list is slower, since there's no guarantee that successive nodes are tightly packed in memory. Iteration over my solution is fast (as is generally the case with iteration over contiguous memory), but might waste time skipping empty cells, as you've already noted. I'm asking whether there is a better way. $\endgroup$ – lisyarus Nov 26 '20 at 9:56
  • 1
    $\begingroup$ @AndrejBauer maybe have a look at this stackoverflow thread: stackoverflow.com/questions/1402483/…. The other list container std::forward_list is slightly faster, but ultimately suffers from the same problems. $\endgroup$ – STanja Nov 26 '20 at 10:12

Your Answer

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

Browse other questions tagged or ask your own question.