Quick A: The only one matching the requirements is a
std::deque, but it might be worth to consider using a memory pool.
Recently on SO:
Since you're asking specifically for a standard container,
std::dequeis the most promising option given your requirements. As long as you only add elements, the existing ones are not relocated, and references/pointers (but not iterators) remain valid. When removing elements, you may however need to leave gaps or swap the element to remove with the last element.
std::vectoris not stable, and
std::forward_listas well as all the associative containers are fragmented.
Looking at Boost.Container, you have additional options, however with other trade-offs:
boost::flat_map provides contiguous storage (like
std::vector), but with it the stability problem
boost::stable_vectoroffers element stability at the cost of contiguity.
Alternatively, you can have a look at pool allocators (like Boost.Pool). They provide low fragmentation and fast allocation, and the container in front of it can still be used like a normal container.