std::vector vs std::list for insertion frequency and dynamic size

Question

Consider the case where I've to add a random number of items to a container i.e. the size of the container cannot be predicted, the frequency of the insertion is high ,and the insertion should be at the end of the container, additional to that I want to remove an element with almost a constant time.

Note: I want also to use the list or the vector in the shared memory.

So in this case, which is better to use std::vector or std::list?

Answer 1

With the clarification in the comments, the answer is std::vector. This is not surprising, as std::list is rarely the best container for a job.

Adding elements to the end is amortized constant time, and removing an element at a random index is as fast as a list, as finding elements in a list typically takes longer than deleting them from a vector.

Note that if order does not matter, you can swap an arbitrary element of a vector with the end one, then pop_back for constant-time random-access erase.

If you regularly iterate over the container, you can remove_if - erase in order to erase elements efficiently at the same time. If erasure happens at a different time than iteration, marking elements as 'to be erased' then erasing them on the next iteration can keep things sane.

Another container to consider if the element order does not matter is unordered_set.