Iterators

🚀 C++ STL Iterators: Your Magic Pointer Friends!

The Story of the Library Explorer 📚

Imagine you’re in a giant library with thousands of books. You want to look at each book one by one. But how do you move through all those shelves?

You need a magic bookmark that:

• Remembers where you are
• Moves forward to the next book
• Sometimes moves backward too
• Tells you what book you’re looking at

That’s exactly what an Iterator is! It’s your guide through any collection of data.

🎯 Iterators Overview

What is an Iterator?

An iterator is like a smart finger pointing at items in a container.

vector<int> books = {10, 20, 30};
auto finger = books.begin();
// finger now points to 10

Think of it this way:

• 📦 Container = A box of toys
• 👆 Iterator = Your finger pointing at one toy
• ➡️ Moving = Slide your finger to the next toy

Why Do We Need Iterators?

Different containers store data differently:

• vector = Books on a shelf (numbered spots)
• list = Train cars linked together
• set = Sorted cards in order

But iterators let you visit all of them the same way!

// Works for vector, list, set - anything!
for (auto it = container.begin();
     it != container.end(); ++it) {
    cout << *it << endl;
}

The Magic Duo: begin() and end()

graph TD
    A["Container"] --> B["begin"]
    A --> C["end"]
    B --> D["👆 First Element"]
    C --> E["🚫 One Past Last"]

• begin() = Points to FIRST item
• end() = Points AFTER the last item (like a stop sign!)

vector<int> nums = {5, 10, 15};
auto start = nums.begin(); // points to 5
auto stop = nums.end();    // points PAST 15

🏷️ Iterator Categories

Just like vehicles have different abilities (car vs plane vs boat), iterators come in 5 categories.

The Iterator Family Tree

graph TD
    A["🐌 Input Iterator<br>Read Once, Forward Only"]
    B["📝 Output Iterator<br>Write Once, Forward Only"]
    C["➡️ Forward Iterator<br>Read/Write, Forward Only"]
    D["↔️ Bidirectional Iterator<br>Forward AND Backward"]
    E["🚀 Random Access Iterator<br>Jump Anywhere!"]

    A --> C
    B --> C
    C --> D
    D --> E

1. 🐌 Input Iterator

Like reading a text message once - you can only go forward and read.

istream_iterator<int> reader(cin);
int x = *reader;  // read value
++reader;         // move to next

Can do: Read (*it), move forward (++it) Cannot: Write, go backward

2. 📝 Output Iterator

Like writing on a printer - you can only write and move forward.

ostream_iterator<int> writer(cout, " ");
*writer = 42;  // writes "42 "
++writer;      // ready for next

Can do: Write (*it = x), move forward (++it) Cannot: Read, go backward

3. ➡️ Forward Iterator

Like walking through a museum - look, touch, but only move forward.

forward_list<int> fl = {1, 2, 3};
auto it = fl.begin();
*it = 100;    // change value
++it;         // move forward
// --it;      // ❌ Cannot go back!

Can do: Read, write, move forward Cannot: Go backward

4. ↔️ Bidirectional Iterator

Like a train on tracks - can go forward AND backward!

list<int> train = {10, 20, 30};
auto it = train.begin();
++it;  // now at 20
--it;  // back to 10 ✅

Used by: list, set, map

5. 🚀 Random Access Iterator

Like teleportation - jump anywhere instantly!

vector<int> v = {10, 20, 30, 40, 50};
auto it = v.begin();
it += 3;          // jump to 40!
it -= 2;          // back to 20
cout << it[2];    // peek at 40 (2 ahead)

Used by: vector, deque, array

Quick Category Comparison

🔧 Iterator Operations

Basic Operations Everyone Has

1. Dereference (*it) - See the value

vector<int> v = {99};
auto it = v.begin();
cout << *it;  // prints 99

2. Increment (++it) - Move forward

++it;  // now points to next element

3. Compare (it1 == it2) - Are they same spot?

if (it == v.end()) {
    cout << "Reached the end!";
}

Bidirectional Operations

Decrement (--it) - Move backward

list<int> lst = {1, 2, 3};
auto it = lst.end();
--it;  // now points to 3
--it;  // now points to 2

Random Access Operations

Jump (it + n, it - n) - Teleport!

vector<int> v = {10, 20, 30, 40, 50};
auto it = v.begin();
auto jump = it + 3;  // points to 40

Index (it[n]) - Peek ahead

cout << it[2];  // shows 30 (without moving)

Distance (it2 - it1) - How far apart?

auto start = v.begin();
auto finish = v.end();
int dist = finish - start;  // 5 elements

Compare (<, >, <=, >=)

if (it < v.end()) {
    cout << "Still more to go!";
}

Helper Functions 🛠️

advance(it, n) - Move any iterator

list<int> lst = {1, 2, 3, 4, 5};
auto it = lst.begin();
advance(it, 3);  // now at 4

distance(it1, it2) - Count steps

auto d = distance(lst.begin(), it);
// d = 3

next(it) and prev(it) - Get neighbor

auto second = next(lst.begin());
auto before = prev(lst.end());

⚠️ Iterator Invalidation

The Danger Zone! 🚨

Remember our magic bookmark? Imagine if someone removed the page it was pointing to. The bookmark now points to… nothing! That’s invalidation.

vector<int> v = {1, 2, 3};
auto it = v.begin();  // points to 1
v.clear();            // BOOM! 💥
// 'it' is now INVALID - don't use it!

When Do Iterators Break?

graph TD
    A["Container Changed"] --> B{What Changed?}
    B --> C["Element Removed"]
    B --> D["Element Added"]
    B --> E["Container Reallocated"]
    C --> F["⚠️ Iterator to that<br>element = INVALID"]
    D --> G["⚠️ Depends on<br>container type"]
    E --> H["💥 ALL iterators<br>= INVALID"]

Vector Invalidation Rules

❌ ALL iterators invalid after:

• push_back() (if capacity changes)
• insert()
• reserve() with larger size
• resize() to larger

❌ Iterators at/after position invalid:

• erase(pos)
• insert(pos, val)

vector<int> v = {1, 2, 3, 4, 5};
auto it = v.begin() + 2;  // points to 3

v.erase(v.begin());  // remove 1
// 'it' is NOW INVALID! ⚠️

List Invalidation (Safer!)

Lists are friendlier - only the erased element’s iterator breaks.

list<int> lst = {1, 2, 3};
auto it1 = lst.begin();      // -> 1
auto it2 = next(it1);        // -> 2
auto it3 = next(it2);        // -> 3

lst.erase(it2);              // remove 2

// it1 still valid! ✅ -> 1
// it2 INVALID ❌
// it3 still valid! ✅ -> 3

Safe Patterns

Pattern 1: Erase and get new iterator

vector<int> v = {1, 2, 3, 4, 5};
auto it = v.begin() + 2;
it = v.erase(it);  // now points to 4

Pattern 2: Loop with erase

// Remove all even numbers safely
for (auto it = v.begin(); it != v.end(); ) {
    if (*it % 2 == 0) {
        it = v.erase(it);  // get next valid
    } else {
        ++it;
    }
}

Pattern 3: Use index for vectors

// When you must modify during loop
for (size_t i = 0; i < v.size(); ++i) {
    if (v[i] < 0) {
        v.erase(v.begin() + i);
        --i;  // adjust index
    }
}

Quick Invalidation Cheat Sheet

🎉 You Made It!

Now you know:

• ✅ What iterators are (smart pointers for collections)
• ✅ The 5 categories (Input → Random Access)
• ✅ All the operations you can perform
• ✅ When iterators become invalid (and how to stay safe!)

Remember: Iterators are your magic bookmark through any collection. Treat them well, watch for invalidation, and they’ll serve you faithfully! 🚀