I have divided my 2D game map into 100x100 pixel pieces (the map size will be integer multiple of dimensions of the piece size). Each map piece contains a list of map objects in it; so that a short list of nearby game object will be available all the time for each given location on the map. I preferred this structure in order to increase performance of the collision detection algorithm.

My question is:
What will happen to the memory allocated by std::vector<MapPieces> when I add a new game object pointer to any of the GameObjects instance? I mean, when a game object overlaps the area of a MapPiece instance and I add its pointer the the GameObjets list, will the entire std::vector<MapPieces> reallocate in the memory? If yes, what kind of container should I prefer instead of std::list<std::shared_ptr<GameObject>> GameObjects?

class GameMap
{
	public:
		// ...
		std::vector<MapPiece> MapPieces;
		// ...
};

class MapPiece
{
	public:
		// ...
		std::list<std::shared_ptr<GameObject>> GameObjects;
		// ...
};

No, the memory for the entire vector will not reallocate if you add something to one of the individual lists.

No, the memory for the entire vector will not reallocate if you add something to one of the individual lists.

But why? Can you please explain it? It is said that, the vector elements are contiguous in the memory. When I add a new list element, the vector must reallocate in order to preserve its contiguous structure. How do you disprove this?

But why? Can you please explain it? It is said that, the vector elements are contiguous in the memory. When I add a new list element, the vector must reallocate in order to preserve its contiguous structure. How do you disprove this?

The vectors memory contains only the lists body. Imagine an implementation like this:

template<typename Type>
class vector
{
    Type* m_array;
     size_t m_count;
};

A list is most likely implemented like this:

class list
{
   Node* m_pFirst; // pointer to the first node
};

Now if you have a vector<list>, the only thing that is in the memory of the vector is this pointer to the first node. The node itselfs lies elswhere on the heap, and so does every other node you add.