Iterator Pattern

Overview

The Iterator pattern is a behavioral design pattern that provides a way to access the elements of an aggregate object sequentially without exposing its underlying representation. It decouples algorithms from containers, enabling you to traverse different data structures with a uniform interface.

Intent

• Provide a way to access the elements of an aggregate object sequentially without exposing its underlying representation
• Support multiple simultaneous traversals of aggregate objects
• Provide a uniform interface for traversing different aggregate structures (polymorphic iteration)

Problem

When you have a collection of objects, you need to provide a way to access its elements without exposing the underlying representation (list, stack, tree, etc.). You might need:

• Different ways to traverse the same collection (forward, backward, filtered)
• Multiple simultaneous traversals
• A uniform interface for different collection types
• To keep the collection interface simple and focused on storage

Directly exposing the collection's internal structure: - Violates encapsulation - Couples clients to specific collection implementations - Makes it difficult to change the collection's internal structure - Clutters the collection interface with traversal methods

Solution

The Iterator pattern suggests extracting the traversal behavior of a collection into a separate object called an iterator. The iterator object encapsulates all the details of accessing and traversing the collection.

Iterators implement various traversal algorithms, but most importantly, they all provide the same interface for accessing elements. This makes the client code compatible with any collection type or any traversal algorithm.

Structure

Components

1. Iterator: Declares an interface for accessing and traversing elements

   • current(): Returns the current element
   • next(): Moves to the next element
   • hasNext(): Checks if there are more elements
   • reset(): Resets the iterator to the beginning

2. ConcreteIterator: Implements the Iterator interface and keeps track of the current position in the traversal

3. Aggregate: Declares an interface for creating an Iterator object

4. ConcreteAggregate: Implements the Iterator creation interface to return an instance of the proper ConcreteIterator

Implementation Details

Basic Iterator Interface

template<typename T>
class Iterator {
public:
    virtual ~Iterator() = default;
    virtual T& current() = 0;
    virtual void next() = 0;
    virtual bool hasNext() const = 0;
    virtual void reset() = 0;
};

Aggregate Interface

template<typename T>
class Aggregate {
public:
    virtual ~Aggregate() = default;
    virtual std::unique_ptr<Iterator<T>> createIterator() = 0;
};

Concrete Iterator

template<typename T>
class ConcreteIterator : public Iterator<T> {
private:
    ConcreteAggregate<T>* aggregate_;
    size_t currentIndex_;

public:
    explicit ConcreteIterator(ConcreteAggregate<T>* aggregate)
        : aggregate_(aggregate), currentIndex_(0) {}

    T& current() override {
        if (!hasNext()) {
            throw std::out_of_range("Iterator out of range");
        }
        return (*aggregate_)[currentIndex_];
    }

    void next() override {
        if (hasNext()) {
            currentIndex_++;
        }
    }

    bool hasNext() const override {
        return currentIndex_ < aggregate_->size();
    }

    void reset() override {
        currentIndex_ = 0;
    }
};

Concrete Aggregate

template<typename T>
class ConcreteAggregate : public Aggregate<T> {
private:
    std::vector<T> items_;

public:
    void add(const T& item) {
        items_.push_back(item);
    }

    size_t size() const {
        return items_.size();
    }

    T& operator[](size_t index) {
        return items_[index];
    }

    std::unique_ptr<Iterator<T>> createIterator() override {
        return std::make_unique<ConcreteIterator<T>>(this);
    }
};

Real-World Example: Book Library

Implementation

class Library : public BookCollection {
private:
    std::vector<Book> books_;

public:
    void addBook(const Book& book) override {
        books_.push_back(book);
    }

    size_t size() const override {
        return books_.size();
    }

    std::unique_ptr<Iterator<Book>> createIterator() override {
        return std::make_unique<LibraryIterator>(this);
    }

    std::unique_ptr<Iterator<Book>> createReverseIterator() override {
        return std::make_unique<ReverseLibraryIterator>(this);
    }
};

// Usage
Library library;
library.addBook(Book("Design Patterns", "Gang of Four", 1994));
library.addBook(Book("Clean Code", "Robert C. Martin", 2008));

auto iterator = library.createIterator();
while (iterator->hasNext()) {
    iterator->current().display();
    iterator->next();
}

Advanced Patterns

1. Filtered Iterator

Iterates only over elements that match a predicate:

template<typename T>
class FilteredIterator : public Iterator<T> {
private:
    std::unique_ptr<Iterator<T>> baseIterator_;
    bool (*predicate_)(const T&);

    void advanceToNext() {
        while (baseIterator_->hasNext() && 
               !predicate_(baseIterator_->current())) {
            baseIterator_->next();
        }
    }

public:
    FilteredIterator(std::unique_ptr<Iterator<T>> baseIterator,
                     bool (*predicate)(const T&))
        : baseIterator_(std::move(baseIterator))
        , predicate_(predicate) {
        advanceToNext();
    }

    T& current() override {
        return baseIterator_->current();
    }

    void next() override {
        baseIterator_->next();
        advanceToNext();
    }

    bool hasNext() const override {
        return baseIterator_->hasNext();
    }
};

// Usage
auto baseIterator = library.createIterator();
FilteredIterator<Book> filtered(
    std::move(baseIterator),
    [](const Book& book) { return book.getYear() < 2000; }
);

2. Tree Traversal Iterators

Depth-First Iterator (Pre-order)

template<typename T>
class DepthFirstIterator : public Iterator<TreeNode<T>> {
private:
    std::vector<std::shared_ptr<TreeNode<T>>> stack_;
    std::shared_ptr<TreeNode<T>> current_;

public:
    explicit DepthFirstIterator(std::shared_ptr<TreeNode<T>> root) {
        if (root) {
            stack_.push_back(root);
            current_ = root;
        }
    }

    TreeNode<T>& current() override {
        return *current_;
    }

    void next() override {
        if (stack_.empty()) {
            current_ = nullptr;
            return;
        }

        auto node = stack_.back();
        stack_.pop_back();

        // Add children in reverse order
        for (auto it = node->children.rbegin(); 
             it != node->children.rend(); ++it) {
            stack_.push_back(*it);
        }

        current_ = stack_.empty() ? nullptr : stack_.back();
    }

    bool hasNext() const override {
        return !stack_.empty();
    }
};

Breadth-First Iterator (Level-order)

template<typename T>
class BreadthFirstIterator : public Iterator<TreeNode<T>> {
private:
    std::vector<std::shared_ptr<TreeNode<T>>> queue_;
    size_t currentIndex_;
    std::shared_ptr<TreeNode<T>> current_;

public:
    explicit BreadthFirstIterator(std::shared_ptr<TreeNode<T>> root)
        : currentIndex_(0) {
        if (root) {
            queue_.push_back(root);
            current_ = root;
        }
    }

    TreeNode<T>& current() override {
        return *current_;
    }

    void next() override {
        if (currentIndex_ >= queue_.size()) {
            current_ = nullptr;
            return;
        }

        auto node = queue_[currentIndex_];
        currentIndex_++;

        // Add all children to queue
        for (const auto& child : node->children) {
            queue_.push_back(child);
        }

        current_ = currentIndex_ < queue_.size() 
                   ? queue_[currentIndex_] : nullptr;
    }

    bool hasNext() const override {
        return currentIndex_ < queue_.size();
    }
};

Applicability

Use the Iterator pattern when:

1. You want to access contents without exposing internal structure: The collection's interface remains simple and focused on storage.

2. You need multiple traversal algorithms: Different iterators can implement different traversal strategies (forward, backward, filtered, etc.).

3. You want to provide a uniform interface: Same interface for different collection types enables polymorphic iteration.

4. You need multiple simultaneous traversals: Each iterator maintains its own state independently.

5. You want to decouple traversal from collection: Enables adding new traversal algorithms without modifying the collection.

Advantages

1. Single Responsibility Principle: Separates collection storage from traversal algorithms.

2. Open/Closed Principle: Introduce new iterators without changing existing code.

3. Multiple Simultaneous Traversals: Each iterator maintains independent state.

4. Uniform Interface: Same interface for different collection types.

5. Encapsulation: Hides internal structure of collections.

6. Simplified Collection Interface: Collection doesn't need traversal methods.

7. Lazy Evaluation: Can implement iterators that generate elements on-demand.

Disadvantages

1. Overkill for Simple Collections: For simple collections with straightforward traversal, the pattern may add unnecessary complexity.

2. Less Efficient: May be less efficient than direct access for some specialized traversals.

3. Increased Complexity: Introduces additional classes and interfaces.

4. State Management: Iterator state must be carefully managed, especially with concurrent modifications.

5. Iterator Invalidation: Modifying the collection while iterating can invalidate iterators.

Relations with Other Patterns

• Composite: Iterators are often used to traverse Composite structures.

• Factory Method: Collections can use Factory Method to create iterators.

• Memento: Can be used together with Iterator to capture and restore the iterator's state.

• Visitor: Visitor can be used along with Iterator to perform operations on elements during traversal.

• Command: Commands can be stored in a collection and executed using an iterator.

Iterator in C++ STL

The C++ Standard Template Library (STL) extensively uses the Iterator pattern:

// Vector iterator
std::vector<int> vec = {1, 2, 3, 4, 5};
for (auto it = vec.begin(); it != vec.end(); ++it) {
    std::cout << *it << " ";
}

// Range-based for loop (uses iterators internally)
for (const auto& item : vec) {
    std::cout << item << " ";
}

// Algorithms work with iterators
auto it = std::find(vec.begin(), vec.end(), 3);
std::sort(vec.begin(), vec.end());

// Reverse iterator
for (auto it = vec.rbegin(); it != vec.rend(); ++it) {
    std::cout << *it << " ";
}

STL iterator categories: - Input Iterator: Read-only, forward-only - Output Iterator: Write-only, forward-only - Forward Iterator: Read/write, forward-only, multi-pass - Bidirectional Iterator: Forward and backward movement - Random Access Iterator: Jump to any position in constant time

Best Practices

1. Provide const iterators: For read-only access to collections.

2. Handle concurrent modification: Define behavior when collection is modified during iteration (fail-fast, snapshot, etc.).

3. Use smart pointers: Manage iterator lifetime with smart pointers.

4. Document iterator invalidation: Clearly specify when iterators become invalid.

5. Consider iterator categories: Choose appropriate iterator capabilities for your use case.

6. Implement standard interface: Follow established conventions (begin(), end(), operator++, etc.).

7. Support range-based for: Make your collections compatible with C++ range-based for loops.

8. Exception safety: Ensure iterators maintain valid state even when exceptions occur.

Example Usage Scenarios

1. Database Result Sets

class ResultSetIterator : public Iterator<Row> {
    // Lazy loading: fetches rows on demand
    void next() override {
        if (!cursor_.fetch()) {
            hasMore_ = false;
        }
    }
};

2. File System Navigation

class DirectoryIterator : public Iterator<FileInfo> {
    // Recursive traversal
    void next() override {
        if (current_.isDirectory()) {
            // Dive into subdirectory
        }
    }
};

3. Network Stream Processing

class PacketIterator : public Iterator<Packet> {
    // Buffered reading from network
    void next() override {
        if (buffer_.empty()) {
            buffer_ = readNextChunk();
        }
        current_ = buffer_.front();
        buffer_.pop();
    }
};

4. GUI Widget Trees

class WidgetIterator : public Iterator<Widget> {
    // Traverse UI component hierarchy
    void next() override {
        // Visit children, then siblings
    }
};

Performance Considerations

1. Iterator Creation Cost: Consider pooling or caching iterators for frequently accessed collections.

2. State Overhead: Each iterator maintains position state. For large collections with many simultaneous iterations, this can be significant.

3. Virtual Function Calls: Abstract iterators use virtual functions, which have a small overhead. For performance-critical code, consider template-based iterators.

4. Cache Locality: Sequential iteration has better cache performance than random access.

5. Lazy Evaluation: Iterators can implement lazy evaluation to avoid loading all data upfront.

Conclusion

The Iterator pattern is one of the most widely used design patterns, particularly in collections and data structures. It provides a clean separation between data storage and data traversal, enabling:

• Uniform access to different collection types
• Multiple traversal strategies
• Independent iteration state
• Simplified collection interfaces

While the pattern adds some complexity, the benefits in terms of flexibility, maintainability, and reusability make it invaluable for working with collections of objects. The pattern is so fundamental that it's built into most modern programming languages, including C++ (STL iterators), Java (Iterator interface), Python (iterator protocol), and many others.