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)
         {
              free_element = data[index].next;
              data[index].next = first_node;
              data[index].element = element;
              first_node = index;
         }
         else
         {
              FooNode new_node(element);
              new_node.next = first_node;
              first_node = data.size() - 1;
              data.push_back(new_node);
         }
    }

    void erase(int n)
    {
         if (first_node == n)
              first_node = data[n].next;
         data[n].next = free_node;
         free_node = n;
    }
};