6.1 Sequence Containers (Vector vs List)

In C++, sequence containers hold data elements in a linear arrangement. While high level languages hide how arrays are managed, C++ forces you to choose between contiguous memory layouts and pointer chained nodes. This choice has massive implications for cache performance and memory allocation overhead.

Let's look at the layouts of vectors, lists, and double ended queues.

The std::vector is a dynamic array stored in a contiguous block of heap memory. When you insert elements, they are placed right next to each other in physical RAM. This layout is extremely fast because CPUs read memory in blocks called cache lines. When the CPU reads the first element of a vector, it pre-fetches the subsequent elements into cache memory, leading to massive speedups during traversal.

* Vector Capacity Reallocation: A vector has a set capacity. When you push back elements and exceed that capacity, the vector must grow. Under the hood, it performs a complex operations dance: allocating a new heap buffer (usually double the size), moving or copying all existing elements to the new buffer, and deleting the old buffer. This makes individual reallocations slow, though amortized insertions remain O(1).

* The Theater Row Metaphor: A vector is like booking a row of contiguous seats at a theater. If your party grows and you need one more seat, but the seat next to you is occupied, you cannot just split the group. You must stand up, walk to a new, empty row that has double the capacity, sit down in the same order, and release the old row.

The std::list is a doubly linked list. Each element is stored in a separate, independently allocated node on the heap. Each node contains the data along with pointers pointing to the next and previous nodes.

Because nodes are allocated one by one, list traversal forces the CPU to chase pointers across scattered memory addresses, causing constant cache misses. However, lists excel at inserting or deleting elements anywhere in the container in constant O(1) time because they only need to update pointer addresses without shifting adjacent data.

* The Treasure Hunt Metaphor: A list is like a house wide treasure hunt where each clue card tells you the coordinates of the next clue card. The cards are scattered all over the house (scattered heap addresses). To find the last card, you must walk from card to card, which is slow, but adding a new card in the middle just requires writing coordinates on two cards without moving the physical cards.

The std::deque (double ended queue) is a hybrid container. Instead of one contiguous array, it allocates a directory of fixed size memory chunks. This allows it to perform constant time insertions at both the front and back without reallocating the entire container, making it a very efficient backing store for queues and stacks.

By default, when you add elements to a vector, it grows dynamically by doubling capacity, which triggers slow heap reallocations. You can prevent this using reserve:

* reserve(N): Allocates heap space for N elements but does not initialize them (size remains 0, capacity is N). This is a pure speed optimization.

* resize(N): Allocates memory and default initializes N elements (size becomes N).

If you know how many elements you will store, always call reserve first. It reduces execution times from multiple reallocations to exactly one allocation.

When you add objects to a vector using push_back, you create a temporary object, which is then copied or moved into the vector's memory block, and then the temporary is destroyed. This wastes instructions.

Modern C++ provides emplace_back, which forwards the arguments directly to the constructor of the element, constructing the element in place inside the vector's memory buffer with zero temporary copies:

#include <vector>
#include <string>

struct Item {
    std::string name;
    int quantity;
    Item(std::string n, int q) : name{n}, quantity{q} {}
};

int main() {
    std::vector<Item> cart;
    
    // Optimize capacity allocation in one step
    cart.reserve(100);

    // Inefficient: Creates temporary Item object, then copies/moves it
    cart.push_back(Item{"Notebook", 5});

    // Optimal: Constructs Item directly inside the vector memory! Zero copy overhead!
    cart.emplace_back("Laptop", 1);

    return 0;
}