Vector Implementation - 1: Size and Capacity Are Different

A vector's visible elements can occupy only part of its allocated array

A vector keeps three pieces of state: a pointer to a backing array, its size, and its capacity. The size tells you how many elements the vector currently contains. The capacity tells you how many elements the backing array can hold before another allocation is needed.

The running vector starts empty. It has no backing slots, size 0, and capacity 0. After appending 4, it has one element, so its state is [4], size 1, and capacity 1. After appending 2, its state is [4, 2], size 2, and capacity 2.

Appending 7 replaces that two-slot backing array with a four-slot array. The existing values remain at indices 0 and 1, and 7 is written at index 2. The state is now [4, 2, 7, unused], size 3, and capacity 4. The unused slot is allocated storage, but it is not an element in the vector.

An append uses the next free slot when size is smaller than capacity

When size is smaller than capacity, the backing array already has a free slot. The next valid position is index size, because the current elements occupy indices 0 through size - 1. For [4, 2, 7, unused], size is 3, so push_back(1) writes 1 at index 3.

v[3] = 1;       // write into the first unused slot
size = size + 1; // the vector now contains four elements

After the write and the size update, the state is [4, 2, 7, 1], size 4, and capacity 4. Capacity did not change because the four-slot backing array was already available. The vector's elements are now exactly the values at indices 0 through 3.

A full vector must replace its backing array before it can append

The first append starts with size 0 and capacity 0, so there is no free slot. The vector allocates capacity 1, writes 4 into the new array, and increases size to 1. The next append starts with size equal to capacity, so it allocates capacity 2, copies 4, releases the old C++ array, switches to the new pointer, writes 2, and increases size to 2.

Appending 7 begins with size 2 and capacity 2, so the vector repeats the replacement process with capacity 4. It first allocates the larger array, then copies the two existing elements 4 and 2, releases the old array, switches its stored pointer, writes 7 at index 2, and increases size to 3.

1. 1Check whether the backing array is full.
2. 2Allocate a larger backing array.
3. 3Copy the existing size elements into it.
4. 4Release the old C++ array.
5. 5Switch the stored pointer to the new array.
6. 6Write the new value and increase size.

The order matters. Writing the new value before creating space would write outside the old array. Releasing the old array before copying would destroy the only copies of 4 and 2. The existing values survive because they are copied into the new array before the old storage is released.

if (__________) grow();

The invariant 0 <= size <= capacity separates valid elements from spare storage

The vector's state follows one rule after every operation: 0 <= size <= capacity. The empty state has size 0 and capacity 0. After 4, the values are [4], size is 1, and capacity is 1. After 2, the values are [4, 2], size is 2, and capacity is 2. After 7, the values are [4, 2, 7, unused], size is 3, and capacity is 4. After 1, size and capacity are both 4.

When size is 3, indices 0, 1, and 2 are valid vector elements. Index 3 exists in the allocated backing array, but it is not a vector element yet. Treating that slot as part of the vector would confuse storage with data and would make the vector appear to contain an extra value.