Ch9.8: vector

Overview

Understanding how ::fast_io::vector manages its capacity is essential for writing efficient code. A vector maintains two quantities:

• size: the number of elements currently stored.
• capacity: the number of elements the vector can hold before it must allocate more memory.

1. How Growth Works

Internally, a vector is three pointers into a single contiguous heap allocation:

• begin_ptr — start of the allocated buffer.
• curr_ptr — one past the last constructed element (i.e., begin_ptr + size()).
• end_ptr — one past the end of the allocated buffer (i.e., begin_ptr + capacity()).

// Conceptual layout of a vector with size=3, capacity=8:
//
//   begin_ptr     curr_ptr                end_ptr
//       |            |                      |
//       v            v                      v
//   +----+----+----+----+----+----+----+----+
//   | e0 | e1 | e2 |    |    |    |    |    |
//   +----+----+----+----+----+----+----+----+
//   ^                       ^
//   |_______ size=3 ________|
//   |___________ capacity=8 _________________|

The hot path: when there is spare capacity

When you call push_back() or emplace_back(), the vector first checks whether curr_ptr != end_ptr. If there is room, the element is constructed in-place at curr_ptr and the pointer is advanced. This is the hot path — a single constructor call and a pointer increment, with no allocation.

The cold path: when capacity is exhausted

When curr_ptr == end_ptr, the vector must reallocate. The steps are:

1. Compute new capacity: the capacity is doubled (2×). If the current capacity is 0, it grows to 1 element. If doubling would overflow size_t, it clamps to the maximum possible capacity.
2. Allocate a new buffer of the new capacity.
3. Move elements from the old buffer to the new one. For trivially-copyable types (like integers, floats, POD structs), this is a single memcpy. For non-trivial types, each element is move-constructed into the new buffer and then destroyed in the old buffer.
4. Deallocate the old buffer.
5. Update all three pointers to point into the new buffer.

// Growth sequence for a vector<size_t>:
//
// capacity: 0 → 1 → 2 → 4 → 8 → 16 → 32 → ...
// size:     0   1   2   3   4    5    6    ...
//
// Each arrow that crosses a power-of-2 boundary triggers reallocation.

Why doubling gives amortised Θ(1)

Consider the total work of n insertions starting from an empty vector. The reallocations happen at sizes 1, 2, 4, 8, …, up to the largest power of 2 less than n. The total number of element moves is:

1 + 2 + 4 + 8 + … + n/2 < n

So the total cost of all reallocations is proportional to n, giving an amortised Θ(1) cost per insertion. Most insertions hit the hot path; only a few trigger the expensive reallocation.

Trivially-copyable vs non-trivial types

This distinction matters for performance: a vector<::std::size_t> of 1 million elements reallocates via a single memcpy of 8 MB, which is heavily optimised by the hardware. A vector<::fast_io::string> of 1 million elements must move-construct and destroy each string individually.

2. reserve()

reserve(n) ensures that the vector has enough capacity for at least n elements. It does not change the size. If the current capacity is already ≥ n, this is a no-op.

Use reserve() when you know in advance how many elements you will need, to avoid repeated reallocations:

#include <fast_io_dsal/vector.h>
#include <fast_io.h>

int main() {
    ::fast_io::vector<::std::size_t> v;

    // Without reserve: push_back triggers reallocations at 1, 2, 4, 8, 16, ...
    // With reserve: zero reallocations during the loop
    v.reserve(1000zu);
    for (::std::size_t i{}; i < 1000zu; ++i) {
        v.push_back(i);
    }
    // size() == 1000, capacity() >= 1000
}

3. push_back_unchecked()

When you have pre-allocated capacity with reserve(), you can use push_back_unchecked() to skip the capacity check on each insertion. This eliminates a branch from the hot path:

::fast_io::vector<::std::size_t> v;
v.reserve(100zu);

// Normal push_back checks: "is curr_ptr == end_ptr?" every iteration.
// push_back_unchecked skips that check — UB if you exceed capacity.
for (::std::size_t i{}; i < 100zu; ++i) {
    v.push_back_unchecked(i);
}
// size() == 100, capacity() >= 100

The pattern reserve() + push_back_unchecked() is the fastest way to fill a vector when the count is known in advance.

4. shrink_to_fit()

shrink_to_fit() requests that the vector reduce its capacity to match its size. This triggers a reallocation if the current capacity exceeds the size, copying elements to a tighter buffer and freeing the old one.

::fast_io::vector<::std::size_t> v;
v.reserve(10000zu);
for (::std::size_t i{}; i < 5zu; ++i) v.push_back(i);
// size() == 5, capacity() >= 10000

v.shrink_to_fit();
// size() == 5, capacity() == 5

5. clear() vs clear_destroy()

These two operations differ in what happens to the allocated memory:

::fast_io::vector<::std::size_t> v{1zu, 2zu, 3zu};
v.reserve(1000zu);

v.clear();
// size() == 0, capacity() >= 1000 (memory still held)

v.clear_destroy();
// size() == 0, capacity() == 0 (memory freed)

Key takeaways

• A vector is three pointers (begin_ptr, curr_ptr, end_ptr) into one contiguous allocation.
• Growth is 2×: capacity doubles on each reallocation, giving amortised Θ(1) push_back.
• Trivially-copyable types relocate via memcpy; non-trivial types are move-constructed element-wise.
• reserve(n) pre-allocates to avoid reallocations when the count is known.
• reserve() + push_back_unchecked() is the fastest way to fill a vector.
• clear() keeps memory for reuse; clear_destroy() frees it.