Contiguous storage

The simplest way to store objects is to put them just next to each other in one large chunk of memory. Such memory can be accessed in a random access manner in O(1) time.

The easiest way to do that is using std::array, which is just a wrapper around normal C-style arrays. It should always be preferred over normal C-style arrays, because it comes with no runtime cost, but adds some comfort and safety. Just as C-style arrays, it has a fixed size once it is created.

The std::vector comes into play when array-like storage is needed, but with varying sizes. It uses memory from the heap to store objects. Whenever new objects are pushed into the vector exceeding its current size, it will automatically move all items to a larger chunk of newly allocated memory, and delete the old chunk. Furthermore, if a new item shall be inserted between old ones, it can even move the existing items back and forth. If an item somewhere in the middle shall be removed, the vector class will automatically close the gap by moving the other objects together.

If lots of objects are inserted/removed at the front and/back of an std::vector that leads to a lot of new memory allocations in order to gain space, with potentially costly object move, std::deque offers an interesting trade off here. The objects are stored in fixed-size chunks of contiguous memory, but these chunks are independent of each other. This makes it very simple and quick to arbitrarily grow the deque, because objects in existing chunks can stay where they are, whenever a new chunk is allocated and put at the front or the end of the container. Deque stands for double-ended queue.