Iterator Design Pattern in Modern C++

Iterator Design Pattern in Modern C++ is a heavily used pattern i.e. provides facility to traverse data containers sophistically. For simplicity, you can consider a pointer moving across an array, but the real magic comes when you get to the next element of a container, in that case, you need not know anything about how the container is constructed(like sequential(not necessarily be contiguous), associative or hashed). This is handled by the iterator.

By the way, If you haven’t check out my other articles on Behavioural Design Patterns, then here is the list:

The code snippets you see throughout this series of articles are simplified not sophisticated. So you often see me not using keywords like override, final, public(while inheritance) just to make code compact & consumable(most of the time) in single standard screen size. I also prefer struct instead of class just to save line by not writing “public:” sometimes and also miss virtual destructor, constructor, copy constructor, prefix std::, deleting dynamic memory, intentionally. I also consider myself a pragmatic person who wants to convey an idea in the simplest way possible rather than the standard way or using Jargons.

Note:

If you stumbled here directly, then I would suggest you go through What is design pattern? first, even if it is trivial. I believe it will encourage you to explore more on this topic.
All of this code you encounter in this series of articles are compiled using C++20(though I have used Modern C++ features up to C++17 in most cases). So if you don’t have access to the latest compiler you can use https://wandbox.org/ which has preinstalled boost library as well.

Intent

To facilitate the traversal of data structure.

Iterator is a core functionality of various containers provided in the standard C++ library. There are lots of cases where you’re using iterators without really knowing what you’re using them. For instance, if you use a range-based for-loop what you’re essentially using is begin, end & operator++ but you don’t see any of it.
Another example is coroutines that’s also something where you have a method which returns a generator but the generator actually gives you the ability to iterate itself and you don’t see the iterators explicitly in this case either.

Iterator Design Pattern Examples in C++

A typical example to illustrate iterator is to use single dimensional array & traverse it using pointer(with the same type as the element of the array). But this is a very simple & straight forward scenario where you can not imagine how important iterators are? So we will see the example of basic associative container i.e. Binary Tree.

Binary Tree Iterator

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
template<typename T>
struct BinaryTree;

template<typename T>
struct Node {
    T                   m_value = T();
    Node<T>*            m_parent{nullptr};
    Node<T>*            m_left{nullptr};
    Node<T>*            m_right{nullptr};
    BinaryTree<T>*      m_tree{nullptr};

    Node(const T& v): m_value(v) {}
    Node(const T& v, Node<T> *const l, Node<T> *const r): m_value(v), m_left(l), m_right(r) {
        this->m_left->m_tree = this->m_right->m_tree = m_tree;
        this->m_left->m_parent = this->m_right->m_parent = this;
    }
    ~Node() { delete m_left; delete m_right; }

    void set_tree(BinaryTree<T> *t) {
        m_tree = t;
        if (m_left) m_left->set_tree(t);
        if (m_right) m_right->set_tree(t);
    }
};

template<typename T>
struct BinaryTree {
    Node<T>*        m_root = nullptr;

    BinaryTree(Node<T> *const r) : m_root{r} {
        m_root->set_tree(this);
    }
    ~BinaryTree() { delete m_root; }

    /* ---------------------------- Iterator Implementation ----------------------------- */

    template<typename U>
    struct PreOrderIterator {
        Node<U> *current;

        PreOrderIterator(Node<U> *c): current(c) {}

        bool operator!=(const PreOrderIterator<U>& rhs) { return current != rhs.current; }

        PreOrderIterator<U>& operator++() {
            if (current->m_right) {
                current = current->m_right;
                while (current->m_left)
                    current = current->m_left;
            } else {
                Node<T> *p = current->m_parent;
                while (p && current == p->m_right) {
                    current = p;
                    p = p->m_parent;
                }
                current = p;
            }
            return *this;
        }

        Node<U>& operator*() { return *current; }
    };

    using iterator = PreOrderIterator<T>;

    iterator begin() {
        Node<T> *n = m_root;

        if (n)
            while (n->m_left)
                n = n->m_left;
        return iterator{n};
    }

    iterator end() { return iterator{nullptr}; }
    /* ---------------------------------------------------------------------------------- */
};

int main() {
    //         me
    //        /  \
    //   mother   father
    //      / \
    //   m'm   m'f

    BinaryTree<string> family {
        new Node<string>{"me",
            new Node<string>{"mother",
                new Node<string>{"mother's mother"},
                new Node<string>{"mother's father"}
            },
            new Node<string>{"father"}
        }
    };

    for_each(begin(family), end(family), // Works with STL algo
    [](auto&& n) {
        cout << n.m_value << endl;
    });

    for (const auto& it: family) // Works with range-based for loop as well
        cout << it.m_value << endl;

    return EXIT_SUCCESS;
}
/*  
mother's mother
mother
mother's father
me
father
mother's mother
mother
mother's father
me
father
*/

The most difficult thing in the above example is implementing PreOrderIterator::operator++. So when we’re traversing the tree in pre-order. What’s happening is every time somebody calls plus-plus we need to move to the subsequent elements of the tree and this is a particularly tricky operation.
So as you can see because we don’t have any way of asynchronously yielding the elements. It becomes a really ugly chunk of code. I mean I can go through this particular implementation. But essentially it’s just the preorder traversal as we use to do.

Binary Tree Iterator with C++20 Co-routines

In a previous example, I’ve deliberately skipped talking about how the traversal was actually implemented. Because if you go up and look at the PreOrderIterator::operator++, you can see that it’s a lot of manipulations around the current pointer & is very ugly.
If you ever came across recursive pre-order traversal, you know that it is very intuitive & concise as follows:

1
2
3
4
5
6
void pre_order(root) { 
    if (root == NULL) return;    
    cout << *root << endl;
    pre_order(root->left);
    pre_order(root->right);
} 

Now the problem here for not having recursion is that you simply have an operator plus-plus. That gets executed at a time and you need to somehow preserve the state between those consecutive executions.
But there was no way of suspending execution and then resuming till C++20. Because if you could do that, you could write a proper recursive algorithm that people could actually read. And instead, we have this monstrosity which I’m not going to go through.
Since C++20, we have a feature in C++ by which we can write above algorithm in an idiomatic way where you can actually read the algorithm and it looks like the algorithm that reflects what you read in Wikipedia or computer science books and the way this is made possible is thanks to C++ coroutines[TODO].

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <iostream>
#include <experimental/coroutine>
using namespace std;

/* Note:
include file https://github.com/lewissbaker/cppcoro/blob/master/include/cppcoro/generator.hpp
if you are not able to use `experimental::generator`.
I have used clang 9.0.0 with cppcoro library for compilation
*/

template<typename T>
struct BinaryTree;

template<typename T>
struct Node {
    T                   m_value = T();
    Node<T>*            m_parent{nullptr};
    Node<T>*            m_left{nullptr};
    Node<T>*            m_right{nullptr};
    BinaryTree<T>*      m_tree{nullptr};

    Node(const T& v): m_value(v) {}
    Node(const T& v, Node<T> *const l, Node<T> *const r): m_value(v), m_left(l), m_right(r) {
        this->m_left->m_tree = this->m_right->m_tree = m_tree;
        this->m_left->m_parent = this->m_right->m_parent = this;
    }
    ~Node() { delete m_left; delete m_right; }

    void set_tree(BinaryTree<T> *t) {
        m_tree = t;
        if (m_left) m_left->set_tree(t);
        if (m_right) m_right->set_tree(t);
    }
};

template<typename T>
struct BinaryTree {
    Node<T> *root = nullptr;

    BinaryTree(Node<T> *const r) : root{r} {
        root->set_tree(this);
    }
    ~BinaryTree() { delete root; }

    /* ------------------------------- C++ co-routines -------------------------------- */
    experimental::generator<Node<T>*> pre_order() { return pre_order_impl(root); }

    experimental::generator<Node<T>*> pre_order_impl(Node<T>* node) {
        if (node) {
            for (auto x : pre_order_impl(node->m_left))
                co_yield x;
            for (auto y : pre_order_impl(node->m_right))
                co_yield y;
            co_yield node;
        }
    }
    /* ---------------------------------------------------------------------------------- */
};

int main() {
    //         me
    //        /  \
    //   mother   father
    //      / \
    //   m'm   m'f

    BinaryTree<string> family {
        new Node<string>{"me",
            new Node<string>{"mother",
                new Node<string>{"mother's mother"},
                new Node<string>{"mother's father"}
            },
            new Node<string>{"father"}
        }
    };

    for (auto it: family.pre_order())
        cout << it->m_value << endl;

    return EXIT_SUCCESS;
}
/*
mother's mother
mother's father
mother
father
me
*/

If you are unable to understand pre_order_impl, I would suggest you go through this talk. After that pre_order_impl would be self explainable.
Moreover, I have compiled above snipped using cppcoro library with clang 9.0.0 on wandbox.

Boost Iterator Facade Design Pattern in C++

If you have gone through my Facade Design Pattern article, you know that the first word in the above title i.e. Facade pronounces as `fa;sa;d`.
Boost Iterator Facade is quite simply a very useful base class that you can add to an iterator very quickly and intuitively i.e. define the operations which make up that iterator. And to explain that I have taken a simple singly-linked list example as below:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <string>
#include <algorithm>
#include <boost/iterator/iterator_facade.hpp>
using namespace std;

struct Node {
    string      m_value;
    Node*       m_next = nullptr;

    Node(const string& v): m_value(v) {}
    Node(const string &v, Node *const parent): m_value(v) { parent->m_next = this; }
};

struct ListIterator: boost::iterator_facade<ListIterator, Node, boost::forward_traversal_tag> {
    Node*       m_current;

    ListIterator(Node *const c = nullptr): m_current(c) {}

	friend class boost::iterator_core_access;

    void increment() { m_current = m_current->m_next; }
    bool equal(const ListIterator &other) const { return other.m_current == m_current; };
    Node& dereference() const { return *m_current; }
};

int main() {
    Node alpha { "alpha" };
    Node beta { "beta", &alpha };
    Node gamma { "gamma", &beta };

    for_each(ListIterator{&alpha}, ListIterator{}, 
	[ ](const Node& n) {
		cout << n.m_value << endl;
	});

    return EXIT_SUCCESS;
}

Some quick things to note here:
- Inheritance mention the type of traversal by boost::forward_traversal_tag.
- We have some override methods like increment(), equal(), dereference(), etc.

You can read more about it in boost Iterator Facade Documentation.

Benefits of Iterator Design Pattern

Maintains good cohesion which means code is easier to understand, use & test since the iterator uses the Single Responsibility Principle and Open-Closed Principle.
Loose coupling between data structures & algorithm as an algorithm does not have to know the way of traversal & even underlying data structure in some cases.
You can extend the Iterators to traverse collection & collection of the collections.
You can combine the Visitor & Iterator Design Pattern to traverse & execute some operation over the collection of different types.

Summary by FAQs

What is the purpose of Iterator Design Pattern?

To abstract away the underlying structure in which the data are kept for traversal & operations.

How do I use Iterator for traversing the collection of the collections?

Composite design pattern

Intent#

Iterator Design Pattern Examples in C++#

Binary Tree Iterator#

Binary Tree Iterator with C++20 Co-routines#

Boost Iterator Facade Design Pattern in C++#

Benefits of Iterator Design Pattern#

Summary by FAQs#