Sequence Containers: Ordered Collections

The STL provides several sequence containers, each with different performance characteristics. Choose based on access patterns and operation frequencies.

std::vector: Dynamic Array

Contiguous memory, random access, amortized O(1) push_back:

std::vector<int> v;
v.push_back(10);
v.push_back(20);
v.emplace_back(30);  // Construct in-place

v[0] = 15;  // O(1) random access
v.resize(100);
v.reserve(1000);  // Pre-allocate capacity

for (const auto& elem : v) {
    std::cout << elem << ' ';
}

Capacity vs Size

• size(): Number of elements
• capacity(): Allocated storage
• reserve(n): Ensure capacity ≥ n (doesn’t change size)
• resize(n): Change size (may construct/destroy elements)

std::vector<int> v;
v.reserve(100);  // capacity = 100, size = 0
v.resize(50);    // capacity = 100, size = 50 (elements default-constructed)

Invalidation Rules

• push_back: Invalidates all if reallocation occurs
• insert/erase: Invalidates from point of modification onward
• clear: Invalidates all iterators, size = 0, capacity unchanged

When to Use vector

• Default choice for sequence container
• Need random access
• Frequent access to elements
• Size relatively stable or grows at end

std::deque: Double-Ended Queue

Like vector but efficient insertion/deletion at both ends:

std::deque<int> d;
d.push_front(10);  // O(1)
d.push_back(20);   // O(1)
d[1] = 25;         // O(1) random access

d.pop_front();     // O(1)
d.pop_back();      // O(1)

Implementation

Not contiguous memory—typically a sequence of fixed-size arrays (chunks). Random access is O(1) but slightly slower than vector.

When to Use deque

• Need push/pop at both ends
• Random access required
• Don’t need pointer stability
• Used by std::stack and std::queue

std::list: Doubly-Linked List

Bidirectional list, O(1) insertion/deletion anywhere (if you have iterator):

std::list<int> lst = {1, 2, 3, 4, 5};

auto it = std::find(lst.begin(), lst.end(), 3);
lst.insert(it, 10);  // Insert before 3: {1, 2, 10, 3, 4, 5}
lst.erase(it);       // Remove 3: {1, 2, 10, 4, 5}

lst.push_front(0);
lst.push_back(6);

Splice Operations

Move elements between lists in O(1):

std::list<int> l1 = {1, 2, 3};
std::list<int> l2 = {4, 5, 6};

l1.splice(l1.end(), l2);  // Move all of l2 to end of l1
// l1: {1, 2, 3, 4, 5, 6}, l2: {}

When to Use list

• Frequent insertion/deletion in middle
• No need for random access
• Need iterator stability (iterators never invalidated except for erased elements)
• Rarely used in practice (cache-unfriendly)

std::forward_list: Singly-Linked List

Like list but single direction, smaller memory footprint:

std::forward_list<int> fwd = {1, 2, 3};

fwd.push_front(0);  // O(1)
// No push_back (would be O(n))

auto it = fwd.before_begin();
fwd.insert_after(it, 10);  // Insert after position

When to Use forward_list

• Minimizing memory overhead matters
• Only need forward iteration
• Very rare in practice

std::array: Fixed-Size Array

Compile-time fixed size, no dynamic allocation:

std::array<int, 5> arr = {1, 2, 3, 4, 5};

arr[0] = 10;  // O(1) access
arr.at(2) = 30;  // Bounds-checked access

// Size is part of type
// std::array<int, 5> != std::array<int, 6>

array vs C Array

int c_array[5];          // No bounds checking, decays to pointer
std::array<int, 5> arr;  // Knows size, range-based for, STL algorithms

When to Use array

• Fixed size known at compile time
• Want STL container interface
• Need to pass to functions without decay

Performance Comparison

† Amortized
‡ If you already have an iterator