Iterators

Iterators are the glue between containers and algorithms. Every STL container exposes begin/end iterators, and every STL algorithm operates on iterator ranges — this separation means algorithms work with any container without knowing its internal structure. Understanding iterators is essential for using the STL correctly.

What Is an Iterator?

An iterator is an object that behaves like a pointer — it points to an element, can be dereferenced to get the value, and can be advanced to the next element:

cpp

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {10, 20, 30, 40, 50};

    // Iterator — like a pointer to an element
    vector<int>::iterator it = v.begin();

    cout << *it << "\n";    // 10  — dereference
    ++it;                    // Advance to next element
    cout << *it << "\n";    // 20
    it += 2;                 // Jump ahead 2 (random access iterators)
    cout << *it << "\n";    // 40

    // Iterate manually
    for (auto it2 = v.begin(); it2 != v.end(); ++it2) {
        cout << *it2 << " ";
    }
    cout << "\n";   // 10 20 30 40 50

    // auto simplifies the type
    auto start = v.begin();
    auto stop  = v.end();

    return 0;
}

Iterator Categories

Category	Capabilities	Containers
Input	Read once, forward only	`istream_iterator`
Output	Write once, forward only	`ostream_iterator`, `back_inserter`
Forward	Read/write, forward only	`forward_list`, `unordered_map`
Bidirectional	Forward + backward (`--`)	`list`, `map`, `set`
Random Access	+n, -n, [], <	`vector`, `deque`, arrays

cpp

#include <iostream>
#include <list>
#include <vector>
using namespace std;

int main() {
    list<int> lst = {1, 2, 3, 4, 5};

    // Bidirectional — can go forward and backward
    auto it = lst.end();
    --it;                       // Reverse one step
    cout << *it << "\n";        // 5

    vector<int> v = {1, 2, 3, 4, 5};

    // Random access — can jump
    auto vit = v.begin();
    vit += 3;
    cout << *vit << "\n";        // 4
    cout << vit[1] << "\n";      // 5
    cout << (v.end() - v.begin()) << "\n";  // 5 (size)

    return 0;
}

const_iterator

cpp

#include <iostream>
#include <vector>
using namespace std;

void printVector(const vector<int>& v) {
    // const reference — only const_iterator works here
    for (vector<int>::const_iterator it = v.cbegin(); it != v.cend(); ++it) {
        cout << *it << " ";
        // *it = 99;  // ERROR — const_iterator doesn't allow modification
    }
    cout << "\n";
}

int main() {
    vector<int> v = {1, 2, 3, 4, 5};
    printVector(v);  // 1 2 3 4 5

    // auto with const range — cleaner
    for (const auto& val : v) {
        cout << val << " ";
    }

    return 0;
}

Reverse Iterators

cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {1, 2, 3, 4, 5};

    // Reverse iterator — rbegin points to last, rend to before-first
    for (auto it = v.rbegin(); it != v.rend(); ++it) {
        cout << *it << " ";
    }
    cout << "\n";   // 5 4 3 2 1

    // Sort in descending order using reverse iterators
    sort(v.rbegin(), v.rend());
    for (int n : v) cout << n << " ";
    cout << "\n";   // 5 4 3 2 1

    // Search from the back
    auto it = find(v.rbegin(), v.rend(), 3);
    if (it != v.rend()) {
        cout << "Found 3 from back\n";
    }

    return 0;
}

Insert Iterators

cpp

#include <iostream>
#include <algorithm>
#include <vector>
#include <list>
using namespace std;

int main() {
    vector<int> src = {1, 2, 3, 4, 5};
    vector<int> dest;

    // back_inserter — calls push_back on each element
    copy(src.begin(), src.end(), back_inserter(dest));
    // dest = {1, 2, 3, 4, 5}

    // front_inserter — calls push_front (requires list or deque)
    list<int> lst;
    copy(src.begin(), src.end(), front_inserter(lst));
    for (int n : lst) cout << n << " ";
    cout << "\n";   // 5 4 3 2 1 (reversed — each pushed to front)

    // inserter — calls insert at a specific position
    vector<int> v = {1, 5, 6};
    vector<int> toInsert = {2, 3, 4};
    copy(toInsert.begin(), toInsert.end(), inserter(v, v.begin() + 1));
    for (int n : v) cout << n << " ";
    cout << "\n";   // 1 2 3 4 5 6

    return 0;
}

Stream Iterators

cpp

#include <iostream>
#include <iterator>
#include <algorithm>
#include <vector>
#include <sstream>
using namespace std;

int main() {
    // Read integers from stdin until EOF
    // istream_iterator<int> it(cin), end;
    // vector<int> v(it, end);

    // Read from stringstream
    string data = "10 20 30 40 50";
    istringstream ss(data);
    istream_iterator<int> begin(ss), end;
    vector<int> v(begin, end);

    for (int n : v) cout << n << " ";
    cout << "\n";   // 10 20 30 40 50

    // Write to stdout using ostream_iterator
    ostream_iterator<int> out(cout, ", ");
    copy(v.begin(), v.end(), out);
    cout << "\n";   // 10, 20, 30, 40, 50,

    return 0;
}

Iterator Arithmetic and Distance

cpp

#include <iostream>
#include <iterator>
#include <vector>
#include <list>
using namespace std;

int main() {
    vector<int> v = {10, 20, 30, 40, 50};

    // distance — O(1) for random access, O(n) for forward iterators
    auto it = v.begin();
    advance(it, 3);
    cout << *it << "\n";   // 40
    cout << distance(v.begin(), it) << "\n";  // 3

    // next / prev (don't modify the iterator)
    auto it2 = next(v.begin(), 2);   // Points to v[2]
    cout << *it2 << "\n";   // 30

    auto it3 = prev(v.end(), 1);    // Points to last element
    cout << *it3 << "\n";   // 50

    return 0;
}

Writing a Custom Iterator

cpp

#include <iostream>
#include <iterator>
using namespace std;

// A range generator — iterates over [start, end) step
class Range {
    int current, stop, step;

public:
    Range(int start, int stop, int step = 1)
        : current(start), stop(stop), step(step) {}

    // Iterator is the range itself (simplified pattern)
    class iterator {
        int value, step;
    public:
        using iterator_category = input_iterator_tag;
        using value_type        = int;
        using difference_type   = ptrdiff_t;
        using pointer           = const int*;
        using reference         = const int&;

        iterator(int v, int s) : value(v), step(s) {}

        int  operator*()  const { return value; }
        iterator& operator++()  { value += step; return *this; }
        bool operator!=(const iterator& other) const {
            return (step > 0) ? value < other.value : value > other.value;
        }
    };

    iterator begin() const { return {current, step}; }
    iterator end()   const { return {stop, step}; }
};

int main() {
    // Range-based for over our custom Range
    for (int i : Range(0, 10)) {
        cout << i << " ";
    }
    cout << "\n";   // 0 1 2 3 4 5 6 7 8 9

    for (int i : Range(0, 20, 3)) {
        cout << i << " ";
    }
    cout << "\n";   // 0 3 6 9 12 15 18

    for (int i : Range(10, 0, -1)) {
        cout << i << " ";
    }
    cout << "\n";   // 10 9 8 7 6 5 4 3 2 1

    // Works with STL algorithms!
    Range r(1, 6);
    int sum = 0;
    for (int n : r) sum += n;
    cout << "Sum 1..5: " << sum << "\n";   // 15

    return 0;
}

Practical Example: Pipeline with Iterators

cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <iterator>
using namespace std;

int main() {
    vector<int> data = {5, 2, 8, 1, 9, 3, 7, 4, 6, 0};

    // Step 1: Copy elements > 4 to a new vector using copy_if + back_inserter
    vector<int> filtered;
    copy_if(data.begin(), data.end(), back_inserter(filtered),
            [](int x) { return x > 4; });

    // Step 2: Sort
    sort(filtered.begin(), filtered.end());

    // Step 3: Print to stdout with ostream_iterator
    copy(filtered.begin(), filtered.end(),
         ostream_iterator<int>(cout, " "));
    cout << "\n";   // 5 6 7 8 9

    // Step 4: Prefix sums
    vector<int> prefix;
    partial_sum(filtered.begin(), filtered.end(), back_inserter(prefix));
    copy(prefix.begin(), prefix.end(),
         ostream_iterator<int>(cout, " "));
    cout << "\n";   // 5 11 18 26 35

    // Step 5: Total
    int total = accumulate(filtered.begin(), filtered.end(), 0);
    cout << "Total: " << total << "\n";   // 35

    return 0;
}

Summary

Iterators abstract element access — begin() points to the first element, end() is one past the last
Iterator categories: input, output, forward, bidirectional, random access — algorithms require minimum categories
Use auto for iterator types — vector<int>::iterator is verbose; auto is cleaner
rbegin()/rend() give reverse iterators — use them to iterate backwards or sort in reverse
Insert iterators (back_inserter, front_inserter, inserter) let algorithms write to containers
distance, advance, next, prev are utility functions for iterator arithmetic
A custom iterator needs: operator*, operator++, operator!=, and the iterator tag type aliases

Next, we'll dive into templates — the mechanism that makes the STL itself generic and lets you write code that works for any type.