CODE: C CPP STL Iterator

If containers answer _where data lives_

and algorithms answer _what to do with data_

then iterators answer the most important question:

How do we access data in a generic, type-safe, and efficient way?

What Is an Iterator?

They are an objects like a pointer that points to an element inside a container

Use iterator to deal with container rather than pointers because it is safer and it will prevent the known behaviour in case of the container is empty.

At minimum, it supports:

• Dereferencing (*it)
• Increment (++it)
• Comparison (it != end)

Iterator ≈ Smart Pointer + Navigation Rules

Example

std::vector<int> v = {1, 2, 3};

for (auto it = v.begin(); it != v.end(); ++it) {
    std::cout << *it << " ";
}

Vector memory:
[1][2][3]

Iterators:
 ^  ^  ^
 |  |  |
begin  ++  end

Why Not Just Use Indexing?

v[i];

Problem:

• Not all containers support indexing
• std::list, std::set, std::map cannot do this
• Algorithms would break

Iterators Solve This

std::sort(v.begin(), v.end());
std::count(l.begin(), l.end(), 5);

Same algorithm — different containers.

Types of Iterators

Not all iterators are equal, STL defines iterator categories, which describe what operations are allowed.

Algorithms select the fastest possible implementation based on iterator type.

The 5 Iterator Categories (From Weak → Strong)

Input
 ↓
Output
 ↓
Forward
 ↓
Bidirectional
 ↓
Random Access

1. Input Iterator: Can read from the pointed element.
2. Output Iterator: Can write to the pointed element.
3. Forward Iterator: Can move forward (increment) through the container.
4. Bidirectional Iterator: Can move both forward (increment) and backward (decrement).
5. Random Access Iterator: Can jump directly to any element (e.g., std::vector iterator).

Input Iterator

Read-only, single-pass

Used for:

• Streams
• One-direction traversal

std::istream_iterator<int> it(std::cin);

Capabilities:

*it   → read
++it  → move forward

Cannot go backward

Cannot re-read the same element

Output Iterator

Write-only, single-pass

Used for:

• Output streams
• Inserters

std::ostream_iterator<int> it(std::cout, " ");

Capabilities:

*it = value
++it

Cannot read

Cannot compare meaningfully

Forward Iterator

Read + write, multi-pass, forward only

Used by:

• std::forward_list
• Some custom containers

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

Capabilities:

*it
++it
== !=

Explanation:

[1] -> [2] -> [3] -> null

Bidirectional Iterator

Forward + backward traversal

Used by:

• std::list
• std::set
• std::map

auto it = myList.begin();
++it;
--it;

Explanation:

[1] <-> [2] <-> [3]

Random Access Iterator (Most Powerful)

Full pointer arithmetic

Used by:

• std::vector
• std::array
• std::deque

Capabilities:

it + n
it - n
it[n]
it < it2

Explanation:

[0][1][2][3][4]
 ^        ^
 it      it+3

Why Iterator Categories Matter (Performance)

Example:

std::advance(it, n);

Implementation depends on iterator type

Random Access → O(1)
Bidirectional → O(n)
Forward       → O(n)

Same function name — different performance.

begin(), end(), rbegin(), rend()

Forward Iteration

for (auto it = c.begin(); it != c.end(); ++it)

begin --> [data] --> end

Reverse Iteration

for (auto it = c.rbegin(); it != c.rend(); ++it)

rend <-- [data] <-- rbegin

Const Iterators

Prevent modification of elements.

std::vector<int>::const_iterator it;

Or preferred:

for (const auto& x : v) { }

Why They Matter

• Enforce correctness
• Enable compiler optimizations
• Express intent clearly

Iterators vs Raw Pointers

Raw pointers are iterators — but not all iterators are pointers.

Range-Based for Loop (Iterator Syntax Sugar)

for (auto& x : container) {
    // uses begin() and end()
}

Equivalent to:

for (auto it = container.begin(); it != container.end(); ++it)

Creating Your own iterator

Creating a custom iterator requires defining a class that mimics the behavior of STL iterators.

The class should implement certain functions like operator*() for dereferencing and operator++() for advancing the iterator. Here’s a basic example:

• *Dereferencing (operator)**: This returns the current element the iterator points to.
• Increment (operator++): Moves the iterator to the next element in the container.
• Comparison operators (operator==, operator!=): Allow comparing iterators to know when to stop iterating (e.g., it != end).

#include <iostream>

template<typename T>
class MyIterator {
private:
    T* ptr;  // Pointer to the current element

public:
    // Constructor
    MyIterator(T* p = nullptr) : ptr(p) {}

    // Dereference operator
    T& operator*() const {
        return *ptr;
    }

    // Prefix increment operator (++it)
    MyIterator& operator++() {
        ++ptr;
        return *this;
    }

    // Postfix increment operator (it++)
    MyIterator operator++(int) {
        MyIterator temp = *this;
        ++ptr;
        return temp;
    }

    // Equality operator (it == other)
    bool operator==(const MyIterator& other) const {
        return ptr == other.ptr;
    }

    // Inequality operator (it != other)
    bool operator!=(const MyIterator& other) const {
        return ptr != other.ptr;
    }
};

int main() {
    int numbers[] = {1, 2, 3, 4, 5};

    // Create iterators pointing to the start and end of the array
    MyIterator<int> begin(numbers);
    MyIterator<int> end(numbers + 5);

    // Traverse the array using the custom iterator
    for (MyIterator<int> it = begin; it != end; ++it) {
        std::cout << *it << " ";
    }

    return 0;
}

Iterators and Algorithms (The Contract)

Algorithms rely on:

• Iterator category
• Operator overloads (<, ==)
• Valid iterator ranges

Example:

std::sort(v.begin(), v.end());

Requires:

Random Access Iterator
operator<

Fails for:

std::list (no random access)

When to Use Which Iterator Type