All posts

Rust / Notes about Vector and memory allocation

Posted On 01.22.2022

A Vector in Rust is fundamentally a (pointer, capacity, length) triplet. For example, a Vec<Char> containing two elements 'a' and 'b', with the capacity of 4, can be visualized as the following diagram:

            ptr      len  capacity
       | 0x0123 |      2 |      4 |
Heap   +--------+--------+--------+--------+
       |    'a' |    'b' | uninit | uninit |

The pointer will always be pointed to the head of contiguous elements allocated on the heap.

The capacity of a Vector is the amount of space allocated for any future elements that will be added to that Vector.

If the Vector’s length exceeds the capacity, more space will be allocated to increase the capacity, but all the Vector’s elements will need to be reallocated. This can be slow, so creating a Vector with some capacity beforehand is always recommended.

When you create a Vector with Vec::new, vec![] or Vec::with_capacity(0), the capacity will be 0. The Vector will not allocate until new elements are pushed into it.

A Vector will never automatically shrink itself, even if it’s empty. This is to ensure there are no unnecessary allocations and deallocations. If you wish to free up unused memory, use Vec::shrink_to_fit or Vec::shrink_to.

When a Vector is dropped, there is no guarantee on the order of which element will be dropped first.

Vec::push and Vec::insert will never allocate/reallocate if the capacity is sufficient. And it only happens when len == capacity. On the other hand, bulk insertion methods like Vec::append may reallocate even when it’s not necessary.