Iterator Pattern

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. This pattern promotes loose coupling between the aggregate (the collection) and the client code that iterates through it. It encapsulates the traversal logic within an iterator object, allowing different iterators to provide different traversal strategies.

What is Iterator Pattern

The Iterator pattern addresses the problem of how to traverse elements within a collection without exposing the collection’s internal structure. Without the Iterator pattern, client code would need to know the specific implementation details of the collection (e.g., whether it’s an array, a linked list, or a tree) to access its elements. This creates a tight coupling between the client and the collection, making it difficult to change the collection’s implementation without affecting the client code.

The Iterator pattern solves this problem by:

Abstraction: It abstracts the traversal logic into a separate iterator object.
Encapsulation: It encapsulates the traversal algorithm within the iterator.
Flexibility: It allows for multiple iterators to be defined for the same collection, each providing a different traversal order or filtering criteria.
Single Responsibility Principle: The collection is responsible for managing its data, while the iterator is responsible for traversing it.

In-depth Explanations:

The core idea is to separate the concerns of how the collection is organized (the aggregate) from how the collection is traversed (the iterator). This separation provides several benefits:

Reduced Complexity: Client code doesn’t need to understand the internal details of the collection.
Increased Reusability: Iterators can be reused across different collections of the same type.
Improved Maintainability: Changes to the collection’s implementation don’t necessarily require changes to the client code, as long as the iterator interface remains the same.

Edge Cases:

Empty Collections: The iterator should handle empty collections gracefully, typically by returning false from the hasNext() method or throwing an exception from the next() method (although the latter is generally discouraged).
Concurrent Modification: If the collection is modified while the iterator is traversing it, the results are unpredictable. Implementations should consider thread safety and potentially throw exceptions or use locking mechanisms to prevent concurrent modification.
Large Collections: For very large collections, iterators can be memory-efficient, as they only need to keep track of the current element, rather than loading the entire collection into memory.

Performance Considerations:

Traversal Overhead: The Iterator pattern introduces a small overhead due to the extra layer of indirection (calling methods on the iterator object instead of directly accessing the collection’s elements). However, this overhead is usually negligible compared to the benefits of decoupling and flexibility.
Iterator Implementation: The performance of the iterator depends on its implementation. Simple iterators (e.g., for arrays) can be very efficient, while more complex iterators (e.g., for trees) may have higher traversal costs.

Syntax and Usage

The Iterator pattern typically involves the following components:

Aggregate: The interface that defines the method for creating an iterator. In C++, this is often an abstract class or a template class.
ConcreteAggregate: A concrete class that implements the Aggregate interface and represents the collection of objects.
Iterator: The interface that defines the methods for accessing and traversing the elements of the collection. Typically includes methods like hasNext(), next(), and getCurrent().
ConcreteIterator: A concrete class that implements the Iterator interface and provides the specific traversal logic for the collection.


// Forward declarations
template <typename T> class Iterator;
template <typename T> class Aggregate;
 
template <typename T>
class Iterator {
public:
  virtual bool hasNext() = 0;
  virtual T next() = 0;
  virtual T getCurrent() = 0;
  virtual ~Iterator() = default;
 
protected:
  Iterator() = default;
};
 
template <typename T>
class Aggregate {
public:
  virtual Iterator<T>* createIterator() = 0;
  virtual ~Aggregate() = default;
 
protected:
  Aggregate() = default;
};

Basic Example

This example demonstrates the Iterator pattern with a simple List class.


#include <iostream>
#include <vector>
 
template <typename T>
class ListIterator : public Iterator<T> {
private:
  std::vector<T>& list;
  int currentPosition;
 
public:
  ListIterator(std::vector<T>& list) : list(list), currentPosition(0) {}
 
  bool hasNext() override {
    return currentPosition < list.size();
  }
 
  T next() override {
    if (!hasNext()) {
      throw std::out_of_range("No more elements in the list.");
    }
    return list[currentPosition++];
  }
 
  T getCurrent() override {
    if (currentPosition >= 1 && currentPosition <= list.size())
      return list[currentPosition-1];
    else if (currentPosition==0 && list.size() > 0)
      return list[currentPosition];
    else
      throw std::out_of_range("Invalid current position.");
  }
};
 
template <typename T>
class List : public Aggregate<T> {
private:
  std::vector<T> data;
 
public:
  List(std::initializer_list<T> init_list) : data(init_list) {}
 
  Iterator<T>* createIterator() override {
    return new ListIterator<T>(data);
  }
 
  int size() const { return data.size(); }
};
 
int main() {
  List<int> myList = {1, 2, 3, 4, 5};
  Iterator<int>* iterator = myList.createIterator();
 
  while (iterator->hasNext()) {
    std::cout << iterator->next() << " ";
  }
  std::cout << std::endl;
 
  delete iterator; // Important to prevent memory leaks
 
  return 0;
}

Explanation:

ListIterator: A concrete iterator that traverses a std::vector<T>. It keeps track of the current position using currentPosition. The next() method increments the position and returns the element at the new position. The getCurrent() method returns the current element.
List: A concrete aggregate that represents a list of elements stored in a std::vector<T>. The createIterator() method creates and returns a new ListIterator object.
In main(), we create a List object and obtain an iterator from it. We then use the iterator to traverse the list and print each element. Critically, we delete iterator to prevent a memory leak.

Advanced Example

This example demonstrates a more advanced use case with a Binary Tree and an Inorder Iterator.


#include <iostream>
#include <stack>
 
template <typename T>
struct TreeNode {
  T data;
  TreeNode<T>* left;
  TreeNode<T>* right;
 
  TreeNode(T data) : data(data), left(nullptr), right(nullptr) {}
};
 
template <typename T>
class InorderIterator : public Iterator<T> {
private:
  TreeNode<T>* current;
  std::stack<TreeNode<T>*> stack;
 
public:
  InorderIterator(TreeNode<T>* root) : current(root) {
    while (current != nullptr) {
      stack.push(current);
      current = current->left;
    }
  }
 
  bool hasNext() override {
    return !stack.empty();
  }
 
  T next() override {
    if (!hasNext()) {
      throw std::out_of_range("No more elements in the tree.");
    }
 
    TreeNode<T>* node = stack.top();
    stack.pop();
    T value = node->data;
 
    if (node->right != nullptr) {
      current = node->right;
      while (current != nullptr) {
        stack.push(current);
        current = current->left;
      }
    }
 
    return value;
  }
 
  T getCurrent() override {
      throw std::runtime_error("getCurrent() not supported for InorderIterator.");
  }
};
 
template <typename T>
class BinaryTree : public Aggregate<T> {
private:
  TreeNode<T>* root;
 
public:
  BinaryTree(TreeNode<T>* root) : root(root) {}
  ~BinaryTree() {
      // Simple recursive deletion (not thread-safe or exception-safe)
      std::function<void(TreeNode<T>*)> delete_tree = [&](TreeNode<T>* node) {
          if (node) {
              delete_tree(node->left);
              delete_tree(node->right);
              delete node;
          }
      };
      delete_tree(root);
  }
 
  Iterator<T>* createIterator() override {
    return new InorderIterator<T>(root);
  }
};
 
 
int main() {
  TreeNode<int>* root = new TreeNode<int>(1);
  root->left = new TreeNode<int>(2);
  root->right = new TreeNode<int>(3);
  root->left->left = new TreeNode<int>(4);
  root->left->right = new TreeNode<int>(5);
 
  BinaryTree<int> tree(root);
  Iterator<int>* iterator = tree.createIterator();
 
  while (iterator->hasNext()) {
    std::cout << iterator->next() << " ";
  }
  std::cout << std::endl;
 
  delete iterator;
 
  return 0;
}

Common Use Cases

Traversing Collections: The most common use case is to iterate over elements in various data structures like lists, arrays, trees, and graphs.
Database Result Sets: Iterating through the results of a database query.
File Systems: Navigating directories and files in a file system.

Best Practices

Use Standard Library Iterators: Leverage C++‘s standard library iterators (std::begin(), std::end(), range-based for loops) whenever possible for common collection types.
Consider Const Iterators: Provide const iterators (e.g., cbegin(), cend()) for read-only access to collections.
Handle Iterator Invalidation: Be aware of iterator invalidation when modifying the underlying collection.

Common Pitfalls

Iterator Invalidation: Modifying the collection while iterating can invalidate iterators, leading to undefined behavior.
Memory Leaks: Forgetting to delete dynamically allocated iterators.
Incorrect Iterator Implementation: Implementing the traversal logic incorrectly, resulting in incorrect or incomplete iteration.

Key Takeaways

The Iterator pattern decouples the collection and the traversal logic.
It provides a consistent interface for accessing elements in different types of collections.
It promotes code reusability and maintainability.