Understanding `std::vector` Capacity and Reallocation

The Anatomy of a std::vector

At its heart, std::vector is a manager for a contiguous block of memory on the heap. Unlike a C-style array on the stack, it can grow and shrink at runtime. To manage this, a std::vector object itself is quite small, typically containing just three key pieces of information.

Let's begin by building a mental model of this internal structure.

As the video explains, the typical internal representation of a std::vector boils down to:

1. A pointer to the beginning of the data (elements): This points to a dynamically allocated array on the heap where the actual objects are stored.
2. The size: The number of elements currently stored in the vector.
3. The capacity: The total number of elements the currently allocated heap memory can hold before a new allocation is needed.

A common mental model for std::vector's internals. The vector object itself is small and lives on the stack (or as a member of another object), while the elements it manages are in a contiguous block on the heap.

The invariant is that size is always less than or equal to capacity (0 <= size <= capacity). When you push_back an element and there is spare capacity (size < capacity), the operation is simple and fast. The new element is constructed at the size index, and size is incremented.

The interesting part, and the core of this lesson, is what happens when size == capacity.

The Reallocation Strategy: Geometric Growth

When a vector is full, it must allocate a new, larger block of memory, move the existing elements into it, and then deallocate the old block. A naive approach might be to just add one extra slot each time. However, this would be incredibly inefficient. If you were to add N elements one by one, you'd perform N reallocations, and the total number of copy/move operations would be on the order of $O(N^2)$, which is terrible.

To solve this, std::vector uses a geometric growth strategy. When it runs out of space, it doesn't just allocate a little more memory; it allocates significantly more, typically by a factor of 1.5 or 2.

This geometric growth ensures that reallocations become progressively less frequent as the vector grows. The cost of copying the elements is "amortized" over many fast push_back operations, resulting in an average time complexity of O(1) for push_back.

Let's see this reallocation process in code.

The "How": Moving vs. Copying and Exception Safety

The implementation you just saw used a simple copy loop. This was the C++98 way of doing things. It works, and it's safe. If an exception is thrown while copying the 5th element, the original vector is still intact, and the new memory can be safely deallocated. This is known as the strong exception guarantee.

However, with C++11 and move semantics, we can do much better. Moving an object is typically much cheaper than copying it, especially for complex objects that manage their own resources (like another vector or a string). An ideal reallocation would move elements from the old buffer to the new one.

But this introduces a problem. What if the move constructor of the 5th element throws an exception? We've already moved the first four elements, leaving them in a valid but unspecified (likely empty) state. We can't roll back to the original state. We've broken the strong exception guarantee!

So, how does std::vector decide whether to use a fast move or a safe copy? It uses type traits.

Specifically, it checks if the element's move constructor is marked noexcept.

This is a perfect example of the practical power of type traits. std::vector uses compile-time information about a type's exception guarantees to make a runtime performance decision. This sophisticated behavior is a key differentiator from simpler dynamic array implementations and a core concept in modern C++ design.

class ResourceHolder {
    int* data; // Represents a resource
public:
    // ... other constructors, destructor ...

    // Move constructor
    ResourceHolder(ResourceHolder&& other) /* what goes here? */ {
        data = other.data;
        other.data = nullptr;
    }
};

ResourceHolder(ResourceHolder&& other) noexcept { // Mark it noexcept
    data = other.data;
    other.data = nullptr;
}

Under the Hood: Allocation vs. Construction

The implementation we saw in the video, which uses new T[new_capacity], is a simplification. High-performance containers like std::vector separate memory allocation from object construction. This gives them finer control, better performance, and more robust exception safety.

The process looks like this:

1. Allocate Raw Memory: Use ::operator new[] (or a custom allocator) to get a block of uninitialized memory. This just reserves bytes; no constructors are called.
2. Construct Objects: Use placement new to construct objects one-by-one in the allocated memory. Placement new has the syntax new(address) Type(args...). It tells the compiler to run the constructor for Type at the specific address provided.

This separation is crucial. During reallocation, std::vector can allocate the new block, and then use placement new to move-construct the elements. If a constructor throws, it knows exactly how many objects were successfully created and can explicitly call their destructors before deallocating the raw memory.

Furthermore, this fine-grained control allows for even more advanced optimizations. Instead of a loop of move-constructing and then destroying old elements, a highly optimized implementation can use an algorithm like uninitialized_move or even uninitialized_relocate. For trivially relocatable types (like std::unique_ptr or a vector of ints), this entire operation can be optimized down to a single, lightning-fast memmove. This is the level of detail that distinguishes C++ from many other languages and is central to its performance story.

Conclusion

You've now seen that std::vector is far more than a simple wrapper around a C array. It's a sophisticated class that embodies key C++ principles.

Key Takeaways:

• Internal Structure: A std::vector manages its data through a pointer to heap memory, a size, and a capacity.
• Reallocation Strategy: It uses geometric growth (e.g., doubling capacity) to achieve amortized O(1) time for push_back.
• Performance vs. Safety: It prefers to move elements during reallocation for speed but falls back to copying if the move constructor might throw an exception, a decision made at compile-time using the is_nothrow_move_constructible type trait. This phenomenon is known as the "vector pessimization".
• Implementation Detail: Professional implementations separate raw memory allocation from object construction (using placement new) to maximize performance and exception safety.

What's Next?

We've established that reallocation is a fundamental, and potentially disruptive, event in a vector's life. In our next lesson, we will explore the direct consequences of this: iterator invalidation. You will learn which operations on a std::vector can cause pointers, references, and iterators to its elements to become invalid, a critical concept for writing correct and safe C++ code.