Container for fast deletion and addition of elements

Question

I need a container that is able to delete and add elements as fast as possible, without the need of reallocation that usually takes place when we push_back elements in an std::vector or when we delete elements.

By looking around on the internet I have found that a good way to achieve this is to use a fixed-size container. The class is supplied with a counter which accounts for the number of "active elements". Deletion of an element consists just of swapping said element with the last active one of the container and decreasing the counter of active elements by one.

What do you think of this implementation? How can I improved it?

#include <vector>

template <class Element>
class ObjectPool
{

private:
    size_t            activeElements;
    std::vector<Element> elements;

public:
    ObjectPool(size_t maxElements)
    {
        activeElements = 0;
        elements.resize(maxElements);
    }

    size_t size() const
    {
        return activeElements;
    }

    Element& at(size_t index)
    {
        if (index >= activeElements) {
            throw std::out_of_range("System: element requested is not active.");
        }
        return elements.at(index);
    }

    const Element& at(size_t index) const
    {
        if (index >= activeElements) {
            throw std::out_of_range("System: element requested is not active.");
        }
        return elements.at(index);
    }

    Element& back()
    {
        if (activeElements <= 0) {
            throw std::out_of_range("System: number of active elements is zero.");
        }
        return elements.at((size_t)(activeElements - 1));
    }

    const Element& back() const
    {
        if (activeElements <= 0) {
            throw std::out_of_range("System: number of active elements is zero.");
        }
        return elements.at((size_t)(activeElements - 1));
    }

    void addBackElement()
    {
        if (activeElements < elements.size()) {
            activeElements++;
        }
        else
        {
            throw std::out_of_range("System: maximum limit of elements in the system exceeded.");
        }
    }

    void deleteElement(size_t index)
    {
        if (index >= activeElements) {
            throw std::out_of_range("System: element requested is not active.");
        }
        activeElements--;
        swapElements(activeElements, index);
    }

    void resize(size_t maxElements)
    {
        elements.resize(maxElements);
    }

private:
    void swapElements(size_t i, size_t j)
    {
        std::swap(elements.at(i), elements.at(j));
    }
};

Answer 1

struct Laugh {
  Laugh() {
    std::cout << "Ha";
  }
};

int main() {
  ObjectPool<Laugh> pool(3);
}

Do you hear the evil laughter?

"active" vs the lifetime of an object

What happened? When you resize the vector from its initial size 0 to some larger size in the constructor, then the vector will be filled with default-inserted objects. So directly after construction of your object pool, it is already completely filled with alive objects. These objects stay alive all the time (unless you resize). Your notion of an "active" object basically just revolves around whether one can access (through at) that object. "deleting" just moves one object out of the "active" (accessible) region of your pool. "adding" enlarges this "active" region.

This is very confusing and not what one does expect from an "object pool"!

Further, it puts up some requirements to that Element type, namely that it must be default-insertable. With the standard allocator (which you use) this means that Element has to be constructible through value initialization. That's a pretty tough requirement, as it basically means that Element needs to have a zero argument constructor. Now, if Element is a bit more than a simple value / data aggregation type, then its objects will probably depend on some objects of other types. To follow the SRP one wouldn't let an Element construct the other objects then, but rather pass it the requirements upon its own construction (dependency injection).

Your object pool design does not allow this, though. In short: You sign yourself up for lots of future trouble.

To fix this, use reserve for your vector in the constructor, and actually construct new objects when adding (make emplace_back of the vector accessible) and destruct (terminology is important!) them when you want to get rid of them. To keep that later operation fast, swap the last element and the one you want to get rid of and then erase the last. (Of course this only works when order doesn't matter. Moreover, it invalidates possibly obtained references to the last element.)

Swapping done right

Calling std::swap directly is almost always wrong. Bring it into scope with using std::swap;, and then just do an unqualified call: swap(a, b). This allows ADL to kick in and find potentially useful user-defined swap functions.

Provide a complete interface

std::vector provides at, which - like yours - does bounds checking. It also provides operator[] which does not. Thus, I'd hope for (expect) your class to provide this feature, too.

Furthermore, I'd follow the terminology used by the standard std::vector for adding / removing elements here: push_back (or emplace_back) and erase.

Expose the allocator

std::vector allows to use a different allocator than the standard one. You should expose this with your pool, too. That allows for object pools whose objects have automatic storage duration ("are on the stack") when used with such an allocator.

Answer 2

I believe the main problem with your code is, well, not with your code, but rather with your

Poor specification of requirements

I need a container that is able to delete and add elements as fast as possible, without the need of reallocation that usually takes place when we push_back elements in an std::vector or when we delete elements.

Why? What do you need it for? What will you do with it?

If you were to say something about that, we would be able to avoid asking you questions such as...

• Do you intend to remove elements from the middle rather than the ends of your data structure? And if it's just the ends - is it both ends, or one end?
• In fact, are your elements even ordered, or rather, do you care about their order?
• Are consecutive insertions and/or removals localized (i.e. closeby)? Or are they otherwise related?
• You wrote the memory needs to be contiguous. Why?
• Do you have a lot of removals and few insertions? A lot of insertions and few removals? Neither?
• Do you mind possibly using more the minimum amount of space necessary?
• Do you care about alignment?
• Are your elements all of equal size?

All of these, and other considerations, impact the choice of an existing data structure or the implementation of a new one.

Don't reinvent the wheel

I need a container

It's very likely that somebody else, with more experience, has already written the container you need. You should really do more work looking at already-implementing containers and explaining why you've ruled them out. Particularly those in the standard library and in various Boost libraries.

Also:

• If you use std::vector<...>::reserve(), you don't get that reallocation you said you were worried about - as long as you haven't exceeded the maximum number of elements. Doesn't that solve your problem from the get go, obviating the need to write anything at all?