C++ alternative to vector for arbitrary number of objects using pointers

Question

I'm working on a prototype 'life simulation' game which incorporates any number of objects / entities that may exist in the game.

Up until this point I had been working with vectors of the objects, with every object that gets instantiated gets automatically copied into a vector that allows for some very simple all encompassing functions like:

physics_manager()
{
    for(std::size_t i = 0; i < all_objects.size(); i++)
        all_objects[i].do_physics();
}

However, I've run into a problem when it comes to using pointers. Previously I used pointers to elements within vectors to interact with objects like this:

class object
{
    //Attributes of object
    object * other_object_to_interact_with;
    std::vector<object*> carried_objects
    //etc
}

I've now realised that changing the size of the vector (a frequent occurrence in this simulation) causes all pointers to elements within that vector to point to some random piece of memory.

I've considered using some form of unique ID for this (e.g. an int assigned to each object, then searching the vector for an object with that int to identify the right one), but this feels like an inefficient and ultimately wrong way to do things.

My question is, is there a container similar to the std::vector that:
a) can be iterated through easily for functions such as the above
b) can hold an arbitrary number of objects that changes during program running
c) is safe to use pointers to elements within it even if the container changes size

Alternatively, is there a way to use vectors to achieve the above without using pointers?

UPDATE: An additional thought - would the issue below be present if instead of vectors containing actual objects, I used vectors containing pointers to objects? Presumably then any pointers to objects outside of the vector would be to the objects themselves - how well would C++ memory manage this or would this lead me into new / delete territory?

FURTHER UPDATE: I migrated to lists rather than vectors, which was surprisingly easy. My most commonly used code snippet was:

for(std::size_t i = 0; i < vector.size(); i++)

This was very easily changed to:

for(auto & i : list)

With 'i' now pointing to an actual object of the list rather than an int that can be used to access the vector with vector[i]. No perceptible performance hit so far with approximately 20000 objects being iterated through.

Additionally, when there is a need to use an 'int' as a reference to one of the objects within the list, that's as simple as:

int j = 0;
for(auto & i : base_class_vector)
{
    if(j == desired_number)
    {
        //Do whatever's needed here
        break;
    }

    j++;
}

Answer 1

The simplest container that fulfills the requirements you stated is std::list.

In this particular case, you shouldn't be using vectors, not just because adding new elements may invalidate references and iterators, but (and I am surprised no one mentioned it in the comments) because as you insert new elements, you are repeatedly re-allocating memory for the whole vector, which is inefficient.

Please have a look here to learn more about std::list. In fact, I would recommend familiarising yourself with the remaining STL containers (vector, list, set and map is all you need to make "informed" choices when deciding on what container to use, other containers are either their variation or are fairly specialised).

Answer 2

http://en.cppreference.com/w/cpp/container/deque std::deque

You still get a operator[] for random access, and can do deque[5] without needing to search through your container.

Your pointers are memory stable (auto* j = &deque[5]; deque.push_back(); *j; is always valid.)

Memory linearity is better then std::list, since it organizes in buckets rather then a pointer to every element.

At the end of the day, std::vector or even std::array is always going to be better performing.

So I do recommend trying to vector.reserve(MAX_OBJECTS); if you have a max amount of objects.

By calling reserve, you will both have memory stable pointers to those objects until pushed over the limit and you'll only have one memory allocation.