Return to Revisions

Kind of echoing Kylotan's suggestion but I would recommend solving this at the data structure level when possible, not at the lower allocator level if you can help it.

Here's a simple example of how you can pool a Foo's memory using an array with holes with elements linked together:

struct FooNode
{
    explicit FooNode(const Foo& ielement): element(ielement) {}

    // Stores a 'Foo'.
    Foo element;

    // Points to the next foo available; either the
    // next used foo or the next deleted foo.
    int next;
};

class Foos
{
    // Stores all the Foo nodes.
    vector<FooNode> nodes;

    // Points to the first used node.
    int first_node;

    // Points to the first free node.
    int free_node;

    Foos(): first_node(-1), free_node(-1)
    {
    }

    void insert(const Foo& element)
    {
         int index = free_node;
         if (index != -1)
         {
              // If there's a free node available,
              // pop it from the free list, overwrite it,
              // and push it to the used list.
              free_node = data[index].next;
              data[index].next = first_node;
              data[index].element = element;
              first_node = index;
         }
         else
         {
              // If there's no free node available, add a 
              // new node and push it to the used list.
              FooNode new_node(element);
              new_node.next = first_node;
              first_node = data.size() - 1;
              data.push_back(new_node);
         }
    }

    void erase(int n)
    {
         // If the node being removed is the first used
         // node, pop it from the used list.
         if (first_node == n)
              first_node = data[n].next;

         // Push the node to the free list.
         data[n].next = free_node;
         free_node = n;
    }
};

Something to this effect: a singly-linked index list with a free list. The index links allow you to skip over removed elements, remove elements in constant-time, and also reclaim/reuse/overwrite free elements with constant-time insertion. And it takes half the memory of a free list allocator implementation to turn it into a data structure using 32-bit indices (assuming you'd have to use 64-bit pointers otherwise).