Sequence Containers

STL Sequence Containers: Your Magical Toy Boxes! 🎁

Imagine you have different types of toy boxes at home. Some let you grab toys from both ends. Some are fixed-size. Some let you easily add toys anywhere! Sequence Containers in C++ are exactly like these special boxes for storing your data.

🚂 The Train Analogy

Think of each container as a different type of train:

• vector = A stretchy train that grows from the back
• deque = A magic train that grows from BOTH ends
• array = A fixed train with exactly X cars (never changes!)
• list = A chain of train cars you can unlink anywhere
• forward_list = A one-way chain (only looks forward)

📦 Vector: The Stretchy Backpack

A vector is like a backpack that stretches. You mainly add things at the back, and it grows automatically!

Why Use Vector?

• Super fast to access any item (like numbered lockers)
• Easy to add items at the end
• Most commonly used container!

Simple Example

#include <vector>

vector<int> backpack;
backpack.push_back(10);  // Add 10
backpack.push_back(20);  // Add 20
backpack.push_back(30);  // Add 30

// Access items
cout << backpack[0];  // Prints: 10
cout << backpack[1];  // Prints: 20

// Size
cout << backpack.size();  // Prints: 3

Key Operations

Memory Magic

graph TD
    A["Vector with 3 items"] --> B["Capacity: 4"]
    B --> C["Add 4th item: Fits!"]
    C --> D["Add 5th item"]
    D --> E["Doubles capacity to 8"]

Pro Tip: Vector doubles its capacity when full. Use reserve() if you know the size upfront!

vector<int> scores;
scores.reserve(100);  // Pre-allocate space

🎭 Deque: The Double-Door Magic Box

A deque (pronounced “deck”) is like a magic box with doors on BOTH sides. You can add or remove from front OR back equally fast!

When to Choose Deque?

• Need to add/remove from both ends quickly
• Building a queue or sliding window
• Can’t decide between front or back operations

Simple Example

#include <deque>

deque<string> line;
line.push_back("Alice");   // Back: [Alice]
line.push_front("Bob");    // Front: [Bob, Alice]
line.push_back("Carol");   // [Bob, Alice, Carol]

cout << line.front();  // Bob
cout << line.back();   // Carol

line.pop_front();  // Remove Bob
// Now: [Alice, Carol]

Key Operations

How Deque Works Inside

graph LR
    A["Chunk 1"] --> B["Chunk 2"]
    B --> C["Chunk 3"]
    D["Front operations"] --> A
    E["Back operations"] --> C

Deque stores data in chunks connected together. That’s why both ends are fast!

📐 Array: The Fixed-Size Treasure Chest

An array is like a treasure chest with exactly N compartments. The size is decided at compile time and never changes.

Why Use Array?

• Fastest of all containers (no overhead)
• Size known at compile time
• Safer than raw C arrays

Simple Example

#include <array>

array<int, 5> treasure = {1, 2, 3, 4, 5};

cout << treasure[0];      // 1
cout << treasure.at(2);   // 3 (with bounds check)
cout << treasure.size();  // Always 5

// Fill all with same value
treasure.fill(0);  // [0, 0, 0, 0, 0]

Key Features

Array vs Vector

graph TD
    A["Need to resize?"] -->|Yes| B["Use vector"]
    A -->|No| C["Size known at compile?"]
    C -->|Yes| D["Use array"]
    C -->|No| E["Use vector"]

Remember: Array size must be a constant known when you write the code!

// This works
array<int, 10> a;

// This does NOT work
int n = 10;
array<int, n> b;  // Error!

🔗 List: The Flexible Chain

A list is like a chain of linked boxes. Each box knows the box before AND after it. You can insert or remove anywhere super fast!

When to Choose List?

• Lots of inserting/removing in the middle
• Never need to access by position [i]
• Frequent splicing (moving chunks)

Simple Example

#include <list>

list<int> chain = {1, 2, 3};

chain.push_front(0);  // [0, 1, 2, 3]
chain.push_back(4);   // [0, 1, 2, 3, 4]

// Insert in middle (need iterator)
auto it = chain.begin();
advance(it, 2);       // Move to position 2
chain.insert(it, 99); // [0, 1, 99, 2, 3, 4]

// Remove
chain.remove(99);     // [0, 1, 2, 3, 4]

Unique List Operations

How List Works Inside

graph LR
    A["Box 1"] <--> B["Box 2"]
    B <--> C["Box 3"]
    D["prev"] --> A
    A --> E["next"]

Each element stores two pointers: one to previous, one to next.

Trade-off: Fast insert/remove, but no random access (can’t use [i]).

➡️ Forward List: The One-Way Chain

A forward_list is like list, but each box only knows the next box (not previous). Uses less memory but can only go forward!

When to Choose Forward List?

• Memory is critical
• Only need forward traversal
• Simple linked list operations

Simple Example

#include <forward_list>

forward_list<int> fchain = {1, 2, 3};

fchain.push_front(0);  // [0, 1, 2, 3]
// No push_back! (can't access end)

// Insert after position
auto it = fchain.begin();
fchain.insert_after(it, 99);
// [0, 99, 1, 2, 3]

// Remove after position
fchain.erase_after(it);
// [0, 1, 2, 3]

Key Differences from List

Visualizing Forward List

graph LR
    A["Box 1"] --> B["Box 2"]
    B --> C["Box 3"]
    C --> D["nullptr"]

Only forward arrows. No way back!

Note: forward_list doesn’t have size(). If you need size, count manually or use list.

🎯 Quick Comparison: Which Container to Choose?

graph TD
    A["What do you need?"] --> B{Random access?}
    B -->|Yes| C{Fixed size?}
    C -->|Yes| D["array"]
    C -->|No| E["vector or deque"]
    B -->|No| F{Insert in middle?}
    F -->|Often| G["list"]
    F -->|Rarely| H{Both ends?}
    H -->|Yes| I["deque"]
    H -->|No| J["vector"]

Speed Comparison Table

*O(1) amortized (sometimes needs to grow)

🎁 Summary: Your Container Toolkit

🌟 Golden Rules

1. Default to vector - It’s fast and flexible
2. Use array - When size is fixed and known
3. Use deque - When you need front operations
4. Use list - When inserting in middle is common
5. Use forward_list - Only when memory is critical

Remember: The STL containers are your friends. Pick the right tool for the job, and your code will be fast, clean, and happy!