BehavioralC++verifiedVerified

Iterator Pattern in C++

Provides a way to sequentially access elements of a collection without exposing its underlying representation.

How to Implement the Iterator Pattern in C++

1Step 1: Define a tree node structure

struct TreeNode {
    std::string value;
    std::vector<std::unique_ptr<TreeNode>> children;

    TreeNode(std::string v) : value(std::move(v)) {}
    void addChild(std::unique_ptr<TreeNode> child) {
        children.push_back(std::move(child));
    }
};

2Step 2: Depth-first iterator

class DFSIterator {
    std::vector<const TreeNode*> stack_;
public:
    explicit DFSIterator(const TreeNode* root) {
        if (root) stack_.push_back(root);
    }

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

    const TreeNode* next() {
        if (stack_.empty()) return nullptr;
        auto* node = stack_.back();
        stack_.pop_back();
        // Push children in reverse so leftmost is processed first
        for (auto it = node->children.rbegin(); it != node->children.rend(); ++it)
            stack_.push_back(it->get());
        return node;
    }
};

3Step 3: Iterate over the tree

int main() {
    auto root = std::make_unique<TreeNode>("A");
    auto b = std::make_unique<TreeNode>("B");
    b->addChild(std::make_unique<TreeNode>("D"));
    b->addChild(std::make_unique<TreeNode>("E"));
    root->addChild(std::move(b));
    root->addChild(std::make_unique<TreeNode>("C"));

    DFSIterator it(root.get());
    while (it.hasNext()) {
        std::cout << it.next()->value << " ";
    }
    std::cout << "\n"; // A B D E C
}

#include <iostream>
#include <string>
#include <vector>
#include <memory>
#include <format>
#include <iterator>
#include <functional>
#include <concepts>

// [step] Define a generic tree with STL-compatible iterators
template <typename T>
struct TreeNode {
    T value;
    std::vector<std::unique_ptr<TreeNode<T>>> children;

    explicit TreeNode(T val) : value(std::move(val)) {}

    TreeNode<T>& addChild(T val) {
        children.push_back(std::make_unique<TreeNode<T>>(std::move(val)));
        return *children.back();
    }
};

// [step] STL-compatible DFS iterator using input_iterator
template <typename T>
class DFSIterator {
    std::vector<const TreeNode<T>*> stack_;
    const TreeNode<T>* current_ = nullptr;

    void advance() {
        if (stack_.empty()) { current_ = nullptr; return; }
        current_ = stack_.back();
        stack_.pop_back();
        for (auto it = current_->children.rbegin();
             it != current_->children.rend(); ++it)
            stack_.push_back(it->get());
    }

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

    DFSIterator() = default;  // end sentinel
    explicit DFSIterator(const TreeNode<T>* root) {
        if (root) { stack_.push_back(root); advance(); }
    }

    reference operator*() const { return current_->value; }
    pointer operator->() const { return &current_->value; }

    DFSIterator& operator++() { advance(); return *this; }
    DFSIterator operator++(int) { auto tmp = *this; advance(); return tmp; }

    bool operator==(const DFSIterator& other) const {
        return current_ == other.current_;
    }
    bool operator!=(const DFSIterator& other) const {
        return !(*this == other);
    }
};

// [step] Range adaptor for range-based for loops
template <typename T>
class DFSRange {
    const TreeNode<T>* root_;
public:
    explicit DFSRange(const TreeNode<T>* root) : root_(root) {}
    DFSIterator<T> begin() const { return DFSIterator<T>(root_); }
    DFSIterator<T> end() const { return DFSIterator<T>(); }
};

// [step] BFS iterator
template <typename T>
class BFSIterator {
    std::vector<const TreeNode<T>*> queue_;
    size_t pos_ = 0;
    const TreeNode<T>* current_ = nullptr;

    void advance() {
        if (pos_ >= queue_.size()) { current_ = nullptr; return; }
        current_ = queue_[pos_++];
        for (const auto& child : current_->children)
            queue_.push_back(child.get());
    }

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

    BFSIterator() = default;
    explicit BFSIterator(const TreeNode<T>* root) {
        if (root) { queue_.push_back(root); advance(); }
    }

    reference operator*() const { return current_->value; }
    BFSIterator& operator++() { advance(); return *this; }
    bool operator==(const BFSIterator&) const { return current_ == nullptr; }
    bool operator!=(const BFSIterator& o) const { return !(*this == o); }
};

template <typename T>
class BFSRange {
    const TreeNode<T>* root_;
public:
    explicit BFSRange(const TreeNode<T>* root) : root_(root) {}
    BFSIterator<T> begin() const { return BFSIterator<T>(root_); }
    BFSIterator<T> end() const { return BFSIterator<T>(); }
};

// [step] Demonstrate both traversal orders with range-based for
int main() {
    TreeNode<std::string> root("A");
    auto& b = root.addChild("B");
    b.addChild("D");
    b.addChild("E");
    auto& c = root.addChild("C");
    c.addChild("F");

    std::cout << "DFS: ";
    for (const auto& val : DFSRange(&root))
        std::cout << val << " ";
    std::cout << "\n";

    std::cout << "BFS: ";
    for (const auto& val : BFSRange(&root))
        std::cout << val << " ";
    std::cout << "\n";
}

Iterator Pattern Architecture

hourglass_empty

Rendering diagram...

lightbulb

Iterator Pattern in the Real World

“Think of a TV remote control. Whether your playlist is on a Blu-ray disc, a streaming service, or a USB drive, you use the same next and previous buttons to cycle through content. The remote (iterator interface) abstracts away the completely different internal mechanisms each media source uses to retrieve the next item.”