jeudi 16 septembre 2021

Is there a name for the data structure in which you use a contiguous vector of objects as a kind of pool?

Say you need a collection of objects such that

  1. You don't care what order they are in.
  2. You want to be able to add and delete items in amortized constant time.
  3. You want the collection to be layed out in memory contiguously.

Now, if it wasn't for 3. you could use a hash set. But with 3. the obvious implementation is using a resizable array, like an std::vector in C++, and do inserts by adding to the back and deletes by swapping the back item into the slot you want to delete and shortening the size of array by 1.

My main question is does this data structure have a name? It seems related to a "pool" but the term pool is the name of a pattern not of a data structure. Also there is the term "slab" but this seems to be about a kind of allocator only.

My secondary question is what are the advantages of this data structure over a hash set in the case in which you don't need contiguous layout. The main one I see is if all you need is 1., 2., and 3. then using a hash set will mean that the item type needs to be hashable and with this data structure it does not.

Aucun commentaire:

Enregistrer un commentaire