18.2 — Introduction to iterators

In this lesson, you'll learn about iterators, one of the most important concepts in modern C++. Iterators provide a unified way to access elements in containers and are essential for using the Standard Template Library (STL) algorithms effectively.

What are iterators?

An iterator is an object that points to an element in a container and provides a way to traverse through the container's elements. Think of iterators as a generalization of pointers that work with different types of containers.

Imagine iterators like bookmarks:

• A bookmark points to a specific page in a book
• You can move the bookmark to the next or previous page
• You can read the content at the current page
• You can compare bookmarks to see if they point to the same page

Why do we need iterators?

Before iterators, accessing container elements required different approaches:

#include <iostream>
#include <vector>
#include <list>

int main()
{
    // With arrays/vectors - use indices
    std::vector<int> vec = {1, 2, 3, 4, 5};
    for (size_t i = 0; i < vec.size(); ++i)
    {
        std::cout << vec[i] << " ";
    }
    std::cout << std::endl;
    
    // With linked lists - different approach needed
    std::list<int> lst = {1, 2, 3, 4, 5};
    // Can't use lst[i] because lists don't support random access!
    // Need a different way to traverse
    
    return 0;
}

Output:

1 2 3 4 5 

Iterators solve this problem by providing a uniform interface for all container types.

Types of iterators

C++ defines five categories of iterators, each with different capabilities:

1. Input iterators

• Read-only, forward-moving
• Can be dereferenced to read values
• Can be incremented to move forward
• Example: Reading from a file stream

2. Output iterators

• Write-only, forward-moving
• Can be dereferenced to write values
• Can be incremented to move forward
• Example: Writing to a file stream

3. Forward iterators

• Read and write, forward-moving only
• Combines input and output iterator capabilities
• Can make multiple passes through data
• Example: std::forward_list iterators

4. Bidirectional iterators

• Read and write, can move forward and backward
• All forward iterator capabilities plus decrement
• Example: std::list, std::set, std::map iterators

5. Random access iterators

• Read and write, can jump to any position
• All bidirectional capabilities plus random access
• Can use arithmetic operations (iterator + n)
• Example: std::vector, std::deque, array iterators

Basic iterator usage

Let's start with the most common iterator operations:

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> numbers = {10, 20, 30, 40, 50};
    
    // Get iterators to the beginning and end
    std::vector<int>::iterator it = numbers.begin();
    std::vector<int>::iterator end_it = numbers.end();
    
    std::cout << "Using iterators to traverse: ";
    
    // Traverse the container
    while (it != end_it)
    {
        std::cout << *it << " ";  // Dereference to get value
        ++it;                     // Move to next element
    }
    std::cout << std::endl;
    
    return 0;
}

Output:

Using iterators to traverse: 10 20 30 40 50 

Key iterator operations:

• container.begin(): Returns iterator to first element
• container.end(): Returns iterator past the last element
• *it: Dereferences iterator to access the value
• ++it: Moves iterator to next element
• it != end_it: Compares iterators for inequality

Using auto for cleaner code

Modern C++ allows you to use auto to simplify iterator declarations:

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> numbers = {10, 20, 30, 40, 50};
    
    std::cout << "Using auto with iterators: ";
    
    // Much cleaner than std::vector<int>::iterator
    for (auto it = numbers.begin(); it != numbers.end(); ++it)
    {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

Output:

Using auto with iterators: 10 20 30 40 50 

Const iterators

When you don't need to modify elements, use const iterators:

#include <iostream>
#include <vector>

int main()
{
    const std::vector<int> numbers = {10, 20, 30, 40, 50};
    
    // const_iterator for read-only access
    std::cout << "Using const iterators: ";
    for (auto it = numbers.cbegin(); it != numbers.cend(); ++it)
    {
        std::cout << *it << " ";
        // *it = 100; // Error! Cannot modify through const iterator
    }
    std::cout << std::endl;
    
    return 0;
}

Output:

Using const iterators: 10 20 30 40 50 

Iterator methods:

• cbegin() and cend(): Return const iterators
• begin() and end(): Return regular iterators (const if container is const)

Reverse iterators

Many containers support reverse iterators for backward traversal:

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> numbers = {10, 20, 30, 40, 50};
    
    std::cout << "Forward: ";
    for (auto it = numbers.begin(); it != numbers.end(); ++it)
    {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    
    std::cout << "Reverse: ";
    for (auto it = numbers.rbegin(); it != numbers.rend(); ++it)
    {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

Output:

Forward: 10 20 30 40 50 
Reverse: 50 40 30 20 10 

Reverse iterator methods:

• rbegin(): Returns reverse iterator to last element
• rend(): Returns reverse iterator past the first element
• crbegin() and crend(): Const reverse iterators

Iterators with different containers

Iterators provide a uniform interface across different container types:

#include <iostream>
#include <vector>
#include <list>
#include <set>

template<typename Container>
void printContainer(const Container& container, const std::string& name)
{
    std::cout << name << ": ";
    for (auto it = container.begin(); it != container.end(); ++it)
    {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
}

int main()
{
    std::vector<int> vec = {3, 1, 4, 1, 5};
    std::list<int> lst = {3, 1, 4, 1, 5};
    std::set<int> st = {3, 1, 4, 1, 5}; // Note: set removes duplicates and sorts
    
    printContainer(vec, "Vector");
    printContainer(lst, "List");
    printContainer(st, "Set");
    
    return 0;
}

Output:

Vector: 3 1 4 1 5 
List: 3 1 4 1 5 
Set: 1 3 4 5 

Iterator arithmetic

Random access iterators (like those for vectors) support arithmetic operations:

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> numbers = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
    
    auto it = numbers.begin();
    
    std::cout << "First element: " << *it << std::endl;
    
    // Jump forward by 3 positions
    it += 3;
    std::cout << "Fourth element: " << *it << std::endl;
    
    // Jump forward by 2 more positions
    it = it + 2;
    std::cout << "Sixth element: " << *it << std::endl;
    
    // Jump backward by 1 position
    --it;
    std::cout << "Fifth element: " << *it << std::endl;
    
    // Calculate distance between iterators
    auto distance = numbers.end() - numbers.begin();
    std::cout << "Container size: " << distance << std::endl;
    
    // Access element using array-like syntax
    std::cout << "Seventh element using it[1]: " << it[1] << std::endl;
    
    return 0;
}

Output:

First element: 10
Fourth element: 40
Sixth element: 60
Fifth element: 50
Container size: 10
Seventh element using it[1]: 60

Modifying elements through iterators

You can modify container elements through non-const iterators:

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> numbers = {1, 2, 3, 4, 5};
    
    std::cout << "Original: ";
    for (const auto& num : numbers)
        std::cout << num << " ";
    std::cout << std::endl;
    
    // Modify elements using iterators
    for (auto it = numbers.begin(); it != numbers.end(); ++it)
    {
        *it *= 2; // Double each element
    }
    
    std::cout << "Doubled: ";
    for (const auto& num : numbers)
        std::cout << num << " ";
    std::cout << std::endl;
    
    // Modify specific elements
    auto it = numbers.begin();
    *it = 100;        // Change first element
    *(it + 2) = 200;  // Change third element
    
    std::cout << "After specific changes: ";
    for (const auto& num : numbers)
        std::cout << num << " ";
    std::cout << std::endl;
    
    return 0;
}

Output:

Original: 1 2 3 4 5 
Doubled: 2 4 6 8 10 
After specific changes: 100 4 200 8 10 

Iterator invalidation

Important: Some operations can invalidate iterators, making them unsafe to use:

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> numbers = {1, 2, 3};
    
    auto it = numbers.begin();
    std::cout << "Value at iterator: " << *it << std::endl;
    
    // This might invalidate the iterator!
    numbers.push_back(4);
    
    // Using 'it' here might be unsafe - it could be invalidated
    // In practice, small additions might not invalidate, but it's not guaranteed
    
    // Safer approach: get a new iterator after modification
    it = numbers.begin();
    std::cout << "Safe access after push_back: " << *it << std::endl;
    
    // Operations that commonly invalidate iterators:
    // - push_back() (if reallocation occurs)
    // - insert() (if reallocation occurs)
    // - erase()
    // - resize()
    // - clear()
    
    return 0;
}

Output:

Value at iterator: 1
Safe access after push_back: 1

Practical example: Finding elements

Here's a practical example using iterators to search for elements:

#include <iostream>
#include <vector>
#include <string>

template<typename Iterator, typename T>
Iterator findElement(Iterator begin, Iterator end, const T& target)
{
    for (auto it = begin; it != end; ++it)
    {
        if (*it == target)
        {
            return it;
        }
    }
    return end; // Not found
}

int main()
{
    std::vector<std::string> fruits = {"apple", "banana", "orange", "grape", "kiwi"};
    
    std::string searchFruit = "orange";
    auto result = findElement(fruits.begin(), fruits.end(), searchFruit);
    
    if (result != fruits.end())
    {
        // Calculate position
        int position = result - fruits.begin();
        std::cout << "Found '" << searchFruit << "' at position " << position << std::endl;
        
        // Modify the found element
        *result = "mango";
        std::cout << "Changed it to 'mango'" << std::endl;
        
        std::cout << "Updated fruits: ";
        for (const auto& fruit : fruits)
            std::cout << fruit << " ";
        std::cout << std::endl;
    }
    else
    {
        std::cout << "'" << searchFruit << "' not found" << std::endl;
    }
    
    return 0;
}

Output:

Found 'orange' at position 2
Changed it to 'mango'
Updated fruits: apple banana mango grape kiwi 

Iterators vs range-based for loops

Compare different traversal methods:

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> numbers = {1, 2, 3, 4, 5};
    
    // Method 1: Traditional for loop (only for random access containers)
    std::cout << "Traditional for: ";
    for (size_t i = 0; i < numbers.size(); ++i)
    {
        std::cout << numbers[i] << " ";
    }
    std::cout << std::endl;
    
    // Method 2: Iterator-based loop
    std::cout << "Iterator-based: ";
    for (auto it = numbers.begin(); it != numbers.end(); ++it)
    {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    
    // Method 3: Range-based for loop (C++11+)
    std::cout << "Range-based: ";
    for (const auto& num : numbers)
    {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    // Method 4: Range-based for with modification
    std::cout << "Modifying with range-based: ";
    for (auto& num : numbers) // Note: non-const reference
    {
        num *= 2;
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

Output:

Traditional for: 1 2 3 4 5 
Iterator-based: 1 2 3 4 5 
Range-based: 1 2 3 4 5 
Modifying with range-based: 2 4 6 8 10 

When to use each method:

• Traditional for: When you need the index or random access
• Iterator-based: When you need fine control or work with algorithms
• Range-based for: When you just need to process each element (most common)

Working with bidirectional iterators

Some containers only support bidirectional iterators:

#include <iostream>
#include <list>
#include <set>

int main()
{
    std::list<int> numbers = {1, 2, 3, 4, 5};
    
    std::cout << "Forward traversal: ";
    for (auto it = numbers.begin(); it != numbers.end(); ++it)
    {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    
    std::cout << "Backward traversal: ";
    auto it = numbers.end();
    while (it != numbers.begin())
    {
        --it; // Move backward
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    
    // Bidirectional iterators don't support random access
    // auto middle = numbers.begin() + 2; // Error! No random access
    
    // Instead, use advance to move iterators
    auto middle = numbers.begin();
    std::advance(middle, 2); // Move forward by 2 positions
    std::cout << "Middle element: " << *middle << std::endl;
    
    return 0;
}

Output:

Forward traversal: 1 2 3 4 5 
Backward traversal: 5 4 3 2 1 
Middle element: 3

Advanced iterator operations

The <iterator> header provides useful utilities:

#include <iostream>
#include <vector>
#include <list>
#include <iterator>

int main()
{
    std::vector<int> vec = {1, 2, 3, 4, 5};
    std::list<int> lst = {10, 20, 30};
    
    // std::distance - calculate distance between iterators
    auto vec_distance = std::distance(vec.begin(), vec.end());
    std::cout << "Vector size using distance: " << vec_distance << std::endl;
    
    // std::advance - move iterator by n positions
    auto it = vec.begin();
    std::advance(it, 3);
    std::cout << "Element at position 3: " << *it << std::endl;
    
    // std::next - get iterator n positions ahead (C++11)
    auto next_it = std::next(vec.begin(), 2);
    std::cout << "Element at position 2: " << *next_it << std::endl;
    
    // std::prev - get iterator n positions behind (C++11)
    auto prev_it = std::prev(vec.end(), 1);
    std::cout << "Last element: " << *prev_it << std::endl;
    
    return 0;
}

Output:

Vector size using distance: 5
Element at position 3: 4
Element at position 2: 3
Last element: 5

Iterator best practices

Do:

• Use auto to simplify iterator declarations
• Prefer range-based for loops when you don't need iterator control
• Use const iterators when you don't need to modify elements
• Check for container emptiness before using iterators
• Be aware of iterator invalidation

Don't:

• Assume all iterators support random access
• Use invalidated iterators
• Dereference end() iterators
• Mix iterators from different containers

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> numbers;
    
    // Good: Check if container is empty
    if (!numbers.empty())
    {
        auto first = numbers.begin();
        std::cout << "First element: " << *first << std::endl;
    }
    else
    {
        std::cout << "Container is empty" << std::endl;
    }
    
    numbers = {1, 2, 3, 4, 5};
    
    // Good: Use const iterator for read-only access
    for (auto it = numbers.cbegin(); it != numbers.cend(); ++it)
    {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    
    // Bad: Don't dereference end() iterator
    // std::cout << *(numbers.end()); // Undefined behavior!
    
    return 0;
}

Output:

Container is empty
1 2 3 4 5 

Summary

Iterators are a fundamental concept in C++ that provide:

• Unified interface: Same syntax works with all container types
• Flexibility: Different iterator categories for different needs
• Abstraction: Hide implementation details of container traversal
• STL compatibility: Essential for using standard algorithms
• Safety: Better than raw pointers in many cases

Key iterator concepts:

• Categories: Input, output, forward, bidirectional, random access
• Operations: begin(), end(), *it, ++it, --it
• Const iterators: Use when you don't need to modify elements
• Reverse iterators: For backward traversal
• Iterator invalidation: Be careful with operations that modify containers

Understanding iterators is crucial because:

1. They're required for STL algorithms
2. They provide container-independent code
3. They enable generic programming
4. They're the foundation of modern C++ iteration

In the next lesson, you'll learn about standard library algorithms that use iterators to provide powerful, reusable operations on containers.

Quiz

1. What are the five categories of iterators, and what are their capabilities?
2. What's the difference between begin() and cbegin()?
3. Why can't you use it + 5 with a std::list iterator?
4. What operations can invalidate iterators in a std::vector?
5. When would you choose iterators over range-based for loops?

Practice exercises

Try these exercises to master iterators:

1. Custom find function: Write a template function that uses iterators to find the first occurrence of a value in any container type.

2. Iterator distance calculator: Create a function that calculates the distance between two iterators without using std::distance.

3. Safe element access: Write a function that safely accesses an element at a given position using iterators, returning a default value if the position is out of bounds.

4. Container reverser: Implement a function that uses reverse iterators to reverse the contents of any container in-place.