Iterators

Iterators and Ranges

Iterators are objects that allow you to traverse container elements without exposing the underlying implementation. This chapter covers iterators in detail.

Iterator Types

┌─────────────────────────────────────────────────────────────┐
│                    Iterator Categories                       │
├─────────────────────────────────────────────────────────────┤
│                                                             │
│  Input Iterator     →  Read values (once), forward only    │
│  Output Iterator    →  Write values (once), forward only   │
│  Forward Iterator   →  Read/write, forward only             │
│  Bidirectional      →  Read/write, forward & backward       │
│  Random Access     →  Read/write, any position            │
│  Contiguous        →  Read/write, contiguous memory        │
│                                                             │
└─────────────────────────────────────────────────────────────┘

Basic Iterator Usage

#include <vector>
#include <iostream>

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

    // Using iterators
    for (auto it = vec.begin(); it != vec.end(); ++it) {
        std::cout << *it << " ";
    }
    // Output: 10 20 30 40 50

    // Using const iterator
    for (auto it = vec.cbegin(); it != vec.cend(); ++it) {
        // *it = 100;  // Error: can't modify
    }
}

Iterator Operations

Moving Iterators

std::vector<int> vec = {1, 2, 3, 4, 5};

auto it = vec.begin();

// Advance
std::advance(it, 2);   // Move 2 positions
++it;                  // Move forward
--it;                  // Move backward

// Distance
auto dist = std::distance(vec.begin(), it);  // Number of elements

Random Access

std::vector<int> vec = {10, 20, 30, 40, 50};

auto it = vec.begin() + 2;   // Points to 30
int value = *(it + 1);       // 40

// Comparison
bool less = vec.begin() < vec.end();  // true

Iterator Adaptors

Reverse Iterators

std::vector<int> vec = {1, 2, 3, 4, 5};

// Reverse iteration
for (auto rit = vec.rbegin(); rit != vec.rend(); ++rit) {
    std::cout << *rit << " ";  // 5 4 3 2 1
}

Insert Iterators

#include <iterator>

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

// Back insert
std::copy(source.begin(), source.end(), std::back_inserter(dest));

// Front insert (for deque/list)
std::deque<int> deque;
std::copy(source.begin(), source.end(), std::front_inserter(deque));

// Insert at position
std::vector<int> vec = {1, 5, 6};
std::copy(source.begin(), source.end(), std::inserter(vec, vec.begin() + 1));
// vec: {1, 1, 2, 3, 5, 6}

Stream Iterators

#include <iterator>

std::vector<int> vec = {1, 2, 3, 4, 5};

// Output to stream
std::copy(vec.begin(), vec.end(),
    std::ostream_iterator<int>(std::cout, " "));
// Output: 1 2 3 4 5

// Input from stream
std::vector<int> input;
std::copy(std::istream_iterator<int>(std::cin),
          std::istream_iterator<int>(),
          std::back_inserter(input));

Move Iterators

#include <vector>

std::vector<std::unique_ptr<int>> source;
source.push_back(std::make_unique<int>(1));
source.push_back(std::make_unique<int>(2));

// Move elements
std::vector<std::unique_ptr<int>> dest(
    std::make_move_iterator(source.begin()),
    std::make_move_iterator(source.end())
);

Iterator Traits

#include <iterator>
#include <type_traits>

std::vector<int> vec = {1, 2, 3};
using Iterator = std::vector<int>::iterator;

// Get iterator category
using Category = typename std::iterator_traits<Iterator>::iterator_category;

// Category is std::random_access_iterator_tag

// Check at compile time
static_assert(
    std::is_same_v<Category, std::random_access_iterator_tag>,
    "Expected random access iterator"
);

Custom Iterators

#include <iterator>

template<typename T>
class ArrayIterator {
private:
    T* ptr;

public:
    using iterator_category = std::random_access_iterator_tag;
    using value_type = T;
    using difference_type = std::ptrdiff_t;
    using pointer = T*;
    using reference = T&;

    ArrayIterator(T* p) : ptr(p) {}

    reference operator*() { return *ptr; }
    pointer operator->() { return ptr; }

    ArrayIterator& operator++() { ++ptr; return *this; }
    ArrayIterator operator++(int) { auto t = *this; ++ptr; return t; }

    bool operator==(const ArrayIterator& other) const { return ptr == other.ptr; }
    bool operator!=(const ArrayIterator& other) const { return ptr != other.ptr; }

    // Random access
    reference operator[](difference_type n) { return ptr[n]; }
    ArrayIterator& operator+=(difference_type n) { ptr += n; return *this; }
    ArrayIterator& operator-=(difference_type n) { ptr -= n; return *this; }
};

class IntArray {
private:
    static const int SIZE = 10;
    int data[SIZE];

public:
    IntArray() { for (int i = 0; i < SIZE; i++) data[i] = i; }

    ArrayIterator<int> begin() { return ArrayIterator<int>(data); }
    ArrayIterator<int> end() { return ArrayIterator<int>(data + SIZE); }
};

int main() {
    IntArray arr;
    for (auto it = arr.begin(); it != arr.end(); ++it) {
        std::cout << *it << " ";  // 0 1 2 3 4 5 6 7 8 9
    }
}

Ranges (C++20)

C++20 introduces ranges - a cleaner way to work with containers:

#include <ranges>
#include <vector>

std::vector<int> vec = {1, 2, 3, 4, 5};

// Using ranges
for (int n : vec | std::views::filter([](int n) { return n % 2 == 0; })) {
    // Process even numbers
}

// Transform
for (int n : vec | std::views::transform([](int n) { return n * 2; })) {
    // Process doubled values
}

// Take first N
for (int n : vec | std::views::take(3)) {
    // First 3 elements
}

Complete Example

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

int main() {
    std::vector<int> vec = {5, 2, 8, 1, 9, 3};

    // Sort using iterators
    std::sort(vec.begin(), vec.end());

    // Find using iterators
    auto it = std::find(vec.begin(), vec.end(), 5);
    if (it != vec.end()) {
        std::cout << "Found 5 at position: " << (it - vec.begin()) << "\n";
    }

    // Reverse iteration
    std::cout << "Reverse: ";
    for (auto rit = vec.rbegin(); rit != vec.rend(); ++rit) {
        std::cout << *rit << " ";
    }
    std::cout << "\n";

    // Copy to output stream
    std::cout << "Elements: ";
    std::copy(vec.begin(), vec.end(),
        std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\n";

    // Transform using iterator adapter
    std::vector<int> squared;
    std::transform(vec.begin(), vec.end(),
        std::back_inserter(squared),
        [](int n) { return n * n; });

    std::cout << "Squared: ";
    std::copy(squared.begin(), squared.end(),
        std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\n";

    return 0;
}

Key Takeaways

• Iterators provide a uniform way to traverse containers
• Different iterator categories support different operations
• Iterator adaptors provide special traversal behaviors
• C++20 ranges provide a more expressive way to compose operations
• Use iterators with STL algorithms for clean, generic code

Next Steps

Now let’s dive into memory management - one of the most important aspects of C++.

Next Chapter: 04_memory/19_pointers.md - Pointers Deep Dive