Here is a simple and yet efficient object pool implementation.

An object pool is a container that allows us to access, iterate, allocate, and destroy objects of a given type.

A example of usage can be:

	ObjectPool<Bubble> bubbles;
	// allocate two objects
	auto first_bubble = bubbles.allocate();
	auto second_bubble = bubbles.allocate();
	// remove one
	bubbles.free(first_bubble);
	// iteration
	for(const auto& bubble : bubles)
		// use bubble

The key feature of the object pool structure is how it handles object deletion (and consequently, allocation). The structure stores all objects in a contiguous block of memory (just like an array) – so each object’s memory slot address can be easily computed from its index. Then,

  • whenever a particular object is destroyed, no piece of memory is actually freed. Instead, the index of the deleted object slot is appended to a list;

  • whenever an object is created, no new memory is allocated, but the slot of a previously deleted object is recycled instead.

This list is a linked list of slots available to newly created objects. The list will store indices instead of pointers (you will see why soon). We could however, store our list inside the array itself, by reinterpreting free slots as nodes of the list:

Note: the list does not requires any extra memory – besides a variable to store the head index. Deletion and allocation can be made in O(1).

If we want to iterate over objects (skipping the free slots) we will have to spend extra memory – like storing another list for the active slots. Then we have a list of free slots (white) and a list of used slots (orange). Now we can iterate over active objects.

What if we have a second array list_array to store both lists? Where each list_array index i corresponds to a unique index (i - 1) in the object array and each element points to the next element in the list it belongs to:

The thing with the pair (i, i-1) is we can conveniently use 0 as a null node in order to identify the end of the list (it is just a choice). You could use a large number, but not a negative number though. Allowing negative numbers would take from us half of the range of indices we can map.

Whenever a slot is freed or allocated, we just move the node from one list to the other. It is straightforward, because a node of the orange list stored at index i of list_ array relates to the slot of index i-1 in the array of objects (that is why we use indices instead of pointers). There is a catch though, if we simply remove an arbitrary node from the orange list we must make sure to connect the previous node to the next one. So the orange list is a doubled linked list.

Here is the scheme of the list_array:

Note that the indices we store inside nodes are node indices, not storage indices, due to our decision of using 0 as the null node. Each orange node stores two indices: an index to the previous node on the list and an index to the next node in the list.

There is no need to create any special structure for the nodes of any of the lists. We can encode all the information we need into an single unsigned integer of 32 bits (or a different size depending of how many objects you want store), even for the doubled linked list. In the latter type of list we can use the upper 16 bits to store the index of the previous node, and the lower 16 bits to store the index of the next node. Both nodes can be easily computed:

	node & 0xff // next node
	node >> 16 // previous node