Object pool with linked list of available objects implementation I was reading some gameprogrammingpatterns (awesome book, by the way, would recommend) and was very excited when I learned that unions are a thing that exists, so I decided to implement an object pool as outlined there.

I'm looking for a review of the usual culprits. Poor readability, not making use of standard library stuff/language features. But more than that, I'd love it if someone could point out how I could improve the access and removal algorithms, as well as an elegant way that I could have duplicates in the list.

What I mean by "doesn't allow duplicates", by the way, is that duplicates are considered equally, so if it's of type int, and there are the values {1, 2, 3, 3, 4, 5} in the pool, and you call removeObj(3), the first 3 that is come across will be "deleted", regardless of what you actually wanted.

#include &lt;vector&gt;

//Doesn't allow duplicates
//O(1) insertion
//O(n) removal
//O(n) access

template &lt;class T&gt;
class Pool
{
    private:

        struct Object
        {
            bool available;
            union
            {
                T data;
                Object* next;
            }state;
        };

        int size = 0;
        int numAlive = 0;

        Object* nextAvailable = nullptr;
        std::vector&lt; Object &gt; objs;

    public:
        Pool();
        Pool(int size);

        bool create(T newObj);
        std::vector&lt;T*&gt; getAlive();
        bool removeObj(T toDel);
};

template &lt;class T&gt;
Pool&lt;T&gt;::Pool()
{
}

template &lt;class T&gt;
Pool&lt;T&gt;::Pool(int size):size(size)
{
    objs = std::vector&lt; Object &gt;(size);

    //All are available
    for(int i = 0; i &lt; objs.size() - 1; i++)
    {
         objs[i].state.next = &amp;objs[i+1];
    }

    objs[objs.size()-1].state.next = nullptr; //Last one terminates list

    nextAvailable = &amp;objs[0];
}

template &lt;class T&gt;
bool Pool&lt;T&gt;::create(T newObj)
{
    if(nextAvailable == nullptr)
    {
        return false;
    }

    Object* newO = nextAvailable;
    nextAvailable = nextAvailable-&gt;state.next;

    newO-&gt;state.data = newObj;
    newO-&gt;available = false;
    numAlive++;

    return true;
}

template &lt;class T&gt;
std::vector&lt;T*&gt; Pool&lt;T&gt;::getAlive()
{
    std::vector&lt;T*&gt; avl = std::vector&lt;T*&gt;(numAlive);
    int cnt = 0;
    for(auto&amp; o : objs)
    {
        if(!o.available)
        {
            avl.at(cnt++) = &amp;(o.state.data);
        }
    }

    return avl;
}

template &lt;class T&gt;
bool Pool&lt;T&gt;::removeObj(T toDel)
{
    for(auto&amp; ob: objs)
    {
        if(!ob.available &amp;&amp; ob.state.data == toDel)
        {
            ob.state.next = nextAvailable;
            ob.available = true;
            nextAvailable = &amp;ob;
            numAlive--;
            break;
        }
    }
}
Design and architecture:

The design of your Object Pool is somewhat unusual. Since you are declaring the payload of type T by value inside the Object struct, once the vector objs is allocated, all objects will also be allocated beforehand. This is fine, if that was your intention, but will require type T to be default constructible. 

Another strange thing is the bool create(T newObj); method. You are actually passing a T instance by value. So the pool will in reality only be storing a copy of an existing object. Usually, object/memory pools will keep a set of instances of something that can be recycled. Thus, I would expect the creation method of the pool to return a pointer to an existing (and possibly recycled) object:

T * Pool::create() { /* ... */ }


Possibly returning nullptr or throwing an exception if out of memory or instances to recycle.

The way you deallocate the objects is also unusual. You are again passing a copy of some value of type T to the removeObj() method, which then scans the array of Objects and if finding a match, marks it as unused. Again you are making the assumption that type T can be compared with operator ==, which is not the case for User Defined Types if you don't explicitly implement operator ==. That seems like and unnecessary constraint. In fact, your whole Object Pool seems to be just a thin wrapper over a vector. What I would have expected to see would be a method that returns a pointer to the pool so that is can be recycled. Something in the lines of:

void Pool::free(T * object) { /* ... */ }


I would like to point you to this implementation of a Pool allocator that you can refer to. This was used by the Doom 3 game. It is also based on a linked list, but it uses a list of arrays of objects. Thanks to some pointer manipulation, removal is also constant complexity. Looking at that implementation might make these things I've mentioned more clear to you.

Code review:

Now focusing on the code presented in the question:


This is a personal preference of mine, but I like to place the public section of a class first in the header file. My rationale is that people using and reading my code will care much more about the public methods of a class, so that's what they want to see first when reading the header file. Private/protected sections of a class are of interest to the programmer maintaining the code, so it makes sense that they don't need that much visibility.
You don't need to implement an empty constructor. Use the new default syntax (C++11):

// In the declaration inside the class body:
Pool() = default;

You should probably make the constructor that takes a single size parameter explicit, to avoid questionable implicit conversions:

explicit Pool(int size);

Since your class has some naked pointers as its members, defining its behavior regarding copy and assignment is very important. Read about The Rule of Three. My suggestion at first would be to just make it non-copyable by deleting the assignment operator and copy constructor. It seems like the safest and simplest option in this case:

Pool(const Pool&amp;) = delete;
Pool&amp; operator = (const Pool&amp;) = delete;

The size member variable is unnecessary. std::vector has a member function with the same name: size().
Initialize the member vector objs in the constructor initialization list:


template &lt;class T&gt; Pool&lt;T&gt;::Pool(int size):size(size) 
{
    objs = std::vector&lt; Object &gt;(size);
    ...



By doing that assignment, you are risking a duplicate initialization. It will first be initialized with the default vector constructor and then again with operator =. I'm not sure if the current generation of compilers is optimizing that or not. I'd guess not because this is a bad programming practice that is easy to fix:

 template &lt;class T&gt; Pool&lt;T&gt;::Pool(int size) 
     : objs(size)
     , numAlive(0)
     , nextAvailable(nullptr)
 {
     ...
 }


Note that you could also use the uniform initialization style if you wanted (e.g. use { } instead of ( ) when calling the constructors of the member variables).
Avoid repeating types when declaring objects (remember to DRY):


std::vector&lt;T*&gt; avl = std::vector&lt;T*&gt;(numAlive);



No need to type std::vector&lt;T*&gt; twice here. You have two options in this case:


The "classic" style:

 std::vector&lt;T*&gt; avl(numAlive);

The new "auto" style from C++11:

 auto avl = std::vector&lt;T*&gt;{numAlive};



I personally like the first "classic" style, however, the second one is starting to be advocated by some programmers, including Herb Sutter.