what is the optimal data structure for a pool container?

Question

At the moment i use the STL vector container template to put back and get the connections.

1) on get, a connection is returned and "erase()"d from pool vector.

2) on release, the connection is handed back to the pool via "push_back()".

This might be very heavy if the pool is frequently used. So my question is, is there any way to improve the performance here by switching to an other data structure?

Answer 1

• If you only append at the back and erase from the back, vector is fine.
• If you append and erase from both front and back, but never from the middle, use deque.
• If you frequently must insert into and erase from the middle, use list.
• Depending on your lookup and traversal requirements, set might be an alternative.

In any case, you should profile the performance; use a typedef for your main container so you can quickly switch and test the different options.

There may be other requirements which you aren't telling us but which are important for the choice of container:

• vector and deque are random-access containers; list and set are node-based. This affects iterator invalidation.
• vector, deque and list are sequence containers, while set is associative; this affects lookup by value.

Answer 2

std::vector is probably the best container for pool. O(1) for insertion and you can also have O(1) for removal if you don't need to maintain order. You can just swap the last item with the item removed and shrink the vector. Also std::vector is pretty space efficient compared to other containers. Low memory consumption also means a better performance because of more CPU cache hits.

Answer 3

Keep vector if you know the maximum number of connections possible in advance (see vector::reserve).

Otherwise use std::list.

At the end it also depends of your platform and the version of the compiler and libstdc++ used.