What is the optimal data structure for a pool container?

Question

I am currently using the STL vector file container template to return and receive connections.

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

2) upon release, the connection is returned to the pool through "push_back ()".

This can be very difficult if the pool is often used. So my question is: is there a way to improve performance here by switching to a different data structure?

Answer 1

• If you only add back and erase from the back, vector is fine.
• If you add and erase both the front and the back, but never in the middle, use deque .
• If you often need to insert and erase from the middle, use list .
• Depending on your search and crawl requirements, set may be an alternative.

In any case, you should determine performance; use typedef for your main container so you can quickly switch and test various parameters.

There may be other requirements that you don’t tell us, but which are important for choosing a container:

• vector and deque - containers with random access; list and node set. This affects the cancellation of the iterator.
• vector, deque and list are sequence containers, and set is associative; this affects the search by value.

Answer 2

std::vector is probably the best container for the pool. O (1) to insert, and you can also remove O (1) if you don't need to maintain order. You can simply swap the last element with the deleted element and compress the vector. In addition, std::vector quite efficient compared to other containers. Low memory consumption also means better performance due to more CPU cache requests.

Answer 3

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

Otherwise use std :: list.

In the end, it also depends on your platform and the version of the compiler used and libstdC ++.