Sequential Containers

Chapter 1: The Zoo — Container Types

The standard library defines six sequential containers. Each makes a different trade-off between access speed and insertion/deletion speed:

Choosing a Container

Chapter 2: Common Operations

All sequential containers share a core set of operations. Learning these once means you can use any container:

c++
vector<int> v = {1, 2, 3};
v.push_back(4);          // {1, 2, 3, 4}
v.insert(v.begin(), 0); // {0, 1, 2, 3, 4} — O(n) for vector
v.erase(v.begin() + 2); // {0, 1, 3, 4} — shifts elements left

Chapter 3: Insert & Erase Under the Hood

The cost of insertion and deletion depends entirely on the data structure. Let's look at what actually happens in memory:

vector insert at middle

Every element after the insertion point must be shifted right to make room. This is O(n) where n is the number of elements after the insertion point. If the vector is full, it must also reallocate.

list insert at middle

A doubly-linked list just rewires two pointers. The new node points to its neighbors, and the neighbors update their pointers. No elements are moved. O(1).

deque insert at front

A deque stores elements in blocks (pages). Inserting at the front just uses space in the first block. If the first block is full, a new block is allocated. No shifting needed. O(1).

Chapter 4: How vector Grows

A vector stores elements in a single contiguous block. When that block fills up and you push_back another element, the vector must allocate a bigger block, copy everything, and free the old one. This sounds expensive — and it is, per-reallocation. But the doubling strategy makes the average cost per push O(1).

Size vs Capacity

Chapter 5: Iterator Invalidation

This is the trap that bites every C++ programmer at least once. When you modify a container's size, existing iterators, pointers, and references to its elements may become invalid. Using an invalidated iterator is undefined behavior — crashes, garbage data, or silent corruption.

When Are Iterators Invalidated?

c++
// CORRECT: erase returns iterator to next element
auto it = v.begin();
while (it != v.end()) {
    if (*it % 2 == 0)
        it = v.erase(it);   // erase returns next valid iterator
    else
        ++it;
}

// WRONG: it is invalidated after erase
for (auto it = v.begin(); it != v.end(); ++it)
    if (*it % 2 == 0)
        v.erase(it);  // BUG! it is now invalid, ++it is UB

Chapter 6: Container Comparison Simulator

Let's compare how vector, deque, and list actually store and manipulate data. Each uses a fundamentally different memory layout, which is why their operation costs differ.

Chapter 7: Container Adaptors

A container adaptor wraps an existing container to provide a different interface. The adaptor restricts which operations are available, giving you a specific data structure semantics.

c++
#include <stack>
stack<int> stk;
stk.push(1);  stk.push(2);  stk.push(3);
stk.top();     // 3 (most recently pushed)
stk.pop();     // removes 3; top is now 2

Chapter 8: Beyond — Connections

Sequential containers are the backbone of C++ programs. Choosing the right one and understanding iterator invalidation are skills that separate novice code from professional code.

Continue Reading

Next up: Chapter 10: Generic Algorithms — powerful operations that work on any container through iterators.