How does std::vector support contiguous memory for custom objects of unknown size

Question

I'm struggling with the correct mental model and understanding of std::vector.

What I thought I knew

When you create a vector of type T and then reserve N elements for the vector, the compiler basically finds and reserves a contiguous block of memory that is N * sizeof(T) bytes. For example,

// Initialize a vector of int
std::vector<int> intvec;

// Reserve contigious block of 4 4-byte chunks of memory
intvec.reserve(4);  // [ | | | ]

// Filling in the memory chunks has obvious behavior:
intvec.push_back(1);  // [1| | | ]
intvec.push_back(2);  // [1|2| | ]

Then we can access any element in random access time because, if we ask for the kth element of the vector, we simply start at the memory address of the start of the vector and then "jump" k * sizeof(T) bytes to get to the kth element.

Custom Objects

My mental model breaks down for custom objects of unknown/varying size. For example,

class Foo {

public:
    Foo() = default;
    Foo(std::vector<int> vec): _vec{vec} {}

private:
    std::vector<int> _vec;
};

int main() {

    // Initialize a vector Foo
    std::vector<Foo> foovec;

    // Reserve contigious block of 4 ?-byte chunks of memory
    foovec.reserve(4);  // [ | | | ]

    // How does memory allocation work since object sizes are unkown?
    foovec.emplace_back(std::vector<int> {1,2});        // [{1,2}| | | ]
    foovec.emplace_back(std::vector<int> {1,2,3,4,5});  // [{1,2}|{1,2,3,4,5}| | ]

    return 0;
}

Since we don't know the size of each instance of Foo, how does foovec.reserve() allocate memory? Furthermore, how could you achieve random access time we don't know how far to "jump" to get to the kth element?

Answer 1

the size of

class Foo {

public:
    Foo() = default;
    Foo(std::vector<int> vec): _vec{vec} {}

private:
    std::vector<int> _vec;
};

is known and constant, the internal std::vector does the allocation in the heap, so there is no problem to do foovec.reserve(4);

else how a std::vector can be in the stack ? ;-)

Answer 2

Your concept of size is flawed. A std::vector<type> has a compile time known size of space it is going to take up. It also has a run time size that it may use (this is allocated at run time and the vector holds a pointer to it). You can picture it laid out like

+--------+
|        |
| Vector |
|        |
|        |
+--------+
     |
     |
     v
+-------------------------------------------------+
|         |         |         |         |         |
| Element | Element | Element | Element | Element |
|         |         |         |         |         |
+-------------------------------------------------+

So when you have a vector of things that have a vector in them, each Element becomes the vector and then those point of to their own storage somewhere else like

+--------+
|        |
| Vector |
|        |
|        |
+----+---+
     |
     |
     v
+----+----+---------+---------+
| Object  | Object  | Object  |
|  with   |  with   |  with   |
| Vector  | Vector  | Vector  |
+----+----+----+----+----+----+
     |         |         |    +---------+---------+---------+---------+---------+
     |         |         |    |         |         |         |         |         |
     |         |         +--->+ Element | Element | Element | Element | Element |
     |         |              |         |         |         |         |         |
     |         |              +-------------------------------------------------+
     |         |    +-------------------------------------------------+
     |         |    |         |         |         |         |         |
     |         +--->+ Element | Element | Element | Element | Element |
     |              |         |         |         |         |         |
     |              +-------------------------------------------------+
     |    +-------------------------------------------------+
     |    |         |         |         |         |         |
     +--->+ Element | Element | Element | Element | Element |
          |         |         |         |         |         |
          +---------+---------+---------+---------+---------+
          

This way all of the vectors are next to each other, but the elements the vectors have can be anywhere else in memory. It is for this reason you don't want to use a std:vector<std::vector<int>> for a matrix. All of the sub vectors get memory to wherever so there is no locality between the rows.

---

Do note that this applies to all of the allocator aware containers as they do not store the elements inside the container directly. This is not true for std::array as, like a raw array, the elements are part of the container. If you have an std::array<int, 20> then it is at least sizeof(int) * 20 bytes in size.