Step 2 of 5

Writing an iterator class

When the data isn't in one contiguous block, like a linked list, a tree or a file, a raw pointer can't be the iterator: ++ on a pointer would move to the next address in memory, not the next node. So you write an iterator class that knows how to move through your structure.

A forward iterator needs just three operators:

• operator* returns the current element,
• operator++ (prefix) moves to the next one and returns *this,
• operator== compares positions. C++20 generates != from it automatically.

#include <iostream>
#include <string>

// Iterates over the words of a sentence without copying them.
class Words {
public:
    explicit Words(const std::string& s) : s_(s) {}

    class Iterator {
    public:
        Iterator(const std::string* s, std::size_t pos) : s_(s), pos_(pos) {}
        std::string operator*() const { return s_->substr(pos_, s_->find(' ', pos_) - pos_); }
        Iterator& operator++() {
            std::size_t space = s_->find(' ', pos_);
            pos_ = (space == std::string::npos) ? s_->size() : space + 1;
            return *this;
        }
        bool operator==(const Iterator& o) const { return pos_ == o.pos_; }

    private:
        const std::string* s_;
        std::size_t pos_;
    };

    Iterator begin() const { return Iterator(&s_, 0); }
    Iterator end() const { return Iterator(&s_, s_.size()); }

private:
    const std::string& s_;
};

int main() {
    std::string text = "iterators are just objects";
    for (const std::string& w : Words(text)) std::cout << "[" << w << "]";
    std::cout << "\n";
}

[iterators][are][just][objects]

How it works

• The iterator stores where it is: here, a position in the string. For a linked list it would store a Node*.
• operator++ does the structure-specific work of finding the next position. For a list that's simply node_ = node_->next;.
• end() is an iterator in the "past the last element" position. For this class that's the string's length; for a linked list it's an iterator holding nullptr, because following next from the last node gives nullptr.
• operator* returns the current element. For a container that stores elements, return a reference (int&) so loops can modify them.

Your task

Your IntList::Iterator holds a Node*. operator* returns node_->value as int&, operator++ follows next (a unique_ptr, so use .get() to get the raw pointer), and operator== compares the node pointers. begin() wraps head_.get(); end() wraps nullptr.

Your turn: finish the Iterator inside IntList and add begin() and end().

Previous: Making a class iterable Next: Iterator concepts and algorithms