Fast insert, fast removal and fast access object pool C++ container
Define exactly what properties you want your container to have

You say:


  As you can see, with usual STL containers, you can't have O(1) performance and low memory footprint everywhere.


That's not so much a property of STL, but of container structures in general. You only get O(1) performance if you don't have to search and don't have to shuffle memory around, and if you can't shuffle memory around you can't have a low memory footprint. So you have to make some compromises.

You don't mention what you want to optimize for, or what kind of usage patterns you are expecting. It would be good if you could write down (for yourself) what exact properties you want your container to have, and then verify whether your implementation actually has those properties.

Your metadata uses storage as well

Your container has a vector&lt;T&gt; with the actual data, which is quite efficient. However, there is also metadata. In particular, there is vector&lt;int&gt; index, which you never shrink. So this means that if you have an access pattern where there is a short spike where a lot of data is stored in the container, then after the spike the data itself doesn't use a lot of space, but the vector of indices is now very large. Especially if T is small, then the overhead of the indices and availability queue might be very significant.

Note that you also never shrink index, even if it is possible to do so (whenever tail indices are unused).

Adding to a vector&lt;&gt; is amortized O(1)

Adding items to a vector&lt;&gt; might cause memory allocations and moves, so the time used for an addition is variable, and does not have an upper bound. Whenever the STL has to reallocate memory for a vector&lt;&gt;, it basically doubles the size, so with a constant rate of addition, it needs less and less reallocations. The result is that the amortized cost is O(1). However, be aware that this container might not be suitable for a real-time system.