STL style iterator template for arbitrary trees in C++20

Question

In different code bases I regularly encounter tree data structures of different design and usually need to traverse it at some point. I finally got tired of writing yet another iterative traversal by hand. While that’s not too complicated, it’s still relatively easy to mess up. Also such basic algorithmic code is out of place in high-level domain logic.

That lead me to the design criteria for this iterator: An STL compatible iterator with support for the most common traversal algorithms and minimal assumptions about the tree data structure designs. Generality is more important than maximum performance. For very specialized use cases I assume you’d want full control and roll your own traversal anyway.

I chose the index based child access to make the iterator a bit more robust against invalidation. Also, the single-class design using concepts to switch features is deliberate. I wanted to see how far that approach would get me easily. Backwards breadth-first iteration turned out to be the limit.

I’m still thinking about the chaining operator->(). It violates the STL iterator requirements, but I’m regularly annoyed by the non-chaining iterators from the standard library. What problems could that cause?

The iterator is part of my personal useful stuff library. The code below is slightly adapted to make it standalone.

tree_iterator.hpp

#pragma once
#include <algorithm>
#include <cassert>
#include <iterator>
#include <memory>
#include <stddef.h>
#include <type_traits>
#include <utility>
#include <vector>
// Simplistic replacement for the assertion from the USL library.
#define USL_ASSERT_MSG(cond, msg) assert(cond)
namespace usl
{
[[noreturn]] inline void unreachable()
{
#if defined(__GNUC__) || defined(__clang__)
 __builtin_unreachable();
#elif defined(_MSC_VER)
 __assume(0);
#endif
}
namespace private_
{
template<typename T>
concept has_arrow_operator = requires(T t) {
 {
 t.operator->()
 };
};
} // namespace private_
enum class TreeTraversal
{
 pre_order,
 post_order,
 breadth_first,
};
/**
An iterator for traversing a tree.
The tree is defined by a root node that may be a node within a larger tree. The iterator visits that
node and all its descendants in the order defined by the selected traversal algorithm.
Template parameters:
`TreeNode`
 The type of a, possibly const and or volatile, node in the tree.
`NodeTraits`
 Supplies information about a tree node’s children. Must be a type compatible with this struct:
 struct NodeTraits
 {
 // Always required.
 size_t child_count(const TreeNodeNode&);
 // Required only for iterators to non-const TreeNode.
 TreeNode& child_at(TreeNode& parent, size_t child_index);
 // Required only for iterators to const TreeNode.
 const TreeNode& child_at(const TreeNode& parent, size_t child_index);
 };
 If you have iterators to both const and non-const `TreeNode`, use a single `NodeTraits` with
 both `child_at()` functions. Otherwise converting from a non-const iterator to the const one
 does not compile.
`algo`
 The `TreeTraversal` algorithm defining the order the tree nodes are iterated in.
`Category`
 Defines whether the iterator is a forward or bidirectional iterator. Must be either
 `std::forward_iterator_tag` or `std::bidirectional_iterator_tag`. Breadth-first iterators
 (`TreeTraversal::breadth_first`) can only be forward iterators.
The iterator is invalidated if any of the following is true:
- Pointers to the current node or any of its ancestors up to and including the iteration root node
 become invalid.
- The current node or any of its ancestors up to but excluding the iteration root node is reparented.
- Siblings of the current node are inserted or removed.
*/
template<typename TreeNode, typename NodeTraits, TreeTraversal algo, typename Category>
class TreeIter
{
 static constexpr bool is_fwd = std::is_same_v<Category, std::forward_iterator_tag>;
 static constexpr bool is_bidir = std::is_same_v<Category, std::bidirectional_iterator_tag>;
public:
 static_assert(not std::is_pointer_v<TreeNode> && not std::is_reference_v<TreeNode>);
 static_assert(
 is_fwd || is_bidir,
 "Category must be std::forward_iterator_tag or std::bidirectional_iterator_tag.");
 static_assert(
 (algo != TreeTraversal::breadth_first) || is_fwd,
 "A breadth-first iterator cannot be bidirectional.");
 using value_type = TreeNode;
 using pointer = value_type*;
 using reference = value_type&;
 using difference_type = ptrdiff_t;
 using iterator_category = Category;
 using iterator_concept = Category;
 static constexpr TreeTraversal traversal_algorithm = algo;
 /**
 Creates an iterator pointing at the first node in traversal order, which may or may not be the
 root node depending on the traversal algorithm.
 For an empty tree pass `nullptr` as `root`.
 */
 [[nodiscard]] static TreeIter create_begin(TreeNode* root, NodeTraits traits = NodeTraits())
 {
 return TreeIter{root, root, std::move(traits)};
 }
 /**
 Creates an iterator pointing past the last node in traversal order.
 Bidirectional iterators can decrement any end iterator to advance to the last node in traversal
 order, no matter if that end iterator was produced by this function or by incrementing an
 iterator to the last node.
 For an empty tree pass `nullptr` as `root`.
 */
 [[nodiscard]] static TreeIter create_end(TreeNode* root, NodeTraits traits = NodeTraits())
 {
 return TreeIter{root, nullptr, std::move(traits)};
 }
 [[nodiscard]] TreeNode& operator*() const
 {
 USL_ASSERT_MSG(m_current, "End iterator cannot be dereferenced.");
 return *m_current;
 }
 [[nodiscard]] TreeNode& operator->() const
 requires private_::has_arrow_operator<TreeNode>
 {
 USL_ASSERT_MSG(m_current, "End iterator cannot be dereferenced.");
 return *m_current;
 }
 [[nodiscard]] TreeNode* operator->() const
 {
 USL_ASSERT_MSG(m_current, "End iterator cannot be dereferenced.");
 return m_current;
 }
 [[nodiscard]] friend constexpr bool operator==(const TreeIter& lhs, const TreeIter& rhs)
 {
 return (lhs.m_current == rhs.m_current);
 }
 TreeIter operator++(int)
 {
 TreeIter tmp{*this};
 ++(*this);
 return tmp;
 }
 TreeIter operator--(int)
 requires (is_bidir)
 {
 TreeIter tmp{*this};
 --(*this);
 return tmp;
 }
 TreeIter& operator++()
 requires (traversal_algorithm == TreeTraversal::pre_order)
 {
 USL_ASSERT_MSG(m_current, "End iterator cannot be incremented.");
 if (m_traits.child_count(*m_current) > 0) {
 m_traversal_state.emplace_back(m_current, 0);
 m_current = std::addressof(m_traits.child_at(*m_current, 0));
 return *this;
 }
 while (not m_traversal_state.empty()) {
 auto& [parent, child_index] = m_traversal_state.back();
 ++child_index;
 if (child_index < m_traits.child_count(*parent)) {
 m_current = std::addressof(m_traits.child_at(*parent, child_index));
 return *this;
 }
 m_current = parent;
 m_traversal_state.pop_back();
 }
 m_current = nullptr;
 return *this;
 }
 TreeIter& operator--()
 requires ((traversal_algorithm == TreeTraversal::pre_order) && is_bidir)
 {
 USL_ASSERT_MSG(m_current != m_root, "Begin iterator cannot be decremented.");
 if (not m_current) {
 m_current = m_root;
 traverse_to_last_leaf_from_current();
 return *this;
 }
 auto& [parent, child_index] = m_traversal_state.back();
 if (child_index > 0) {
 --child_index;
 m_current = std::addressof(m_traits.child_at(*parent, child_index));
 traverse_to_last_leaf_from_current();
 }
 else {
 m_current = parent;
 m_traversal_state.pop_back();
 }
 return *this;
 }
 TreeIter& operator++()
 requires (traversal_algorithm == TreeTraversal::post_order)
 {
 USL_ASSERT_MSG(m_current, "End iterator cannot be incremented.");
 if (m_traversal_state.empty()) {
 m_current = nullptr;
 return *this;
 }
 auto& [parent, child_index] = m_traversal_state.back();
 ++child_index;
 if (child_index < m_traits.child_count(*parent)) {
 m_current = std::addressof(m_traits.child_at(*parent, child_index));
 traverse_to_first_leaf_from_current();
 }
 else {
 m_current = parent;
 m_traversal_state.pop_back();
 }
 return *this;
 }
 TreeIter& operator--()
 requires ((traversal_algorithm == TreeTraversal::post_order) && is_bidir)
 {
 if (not m_current) {
 m_current = m_root;
 return *this;
 }
 if (auto child_count = m_traits.child_count(*m_current)) {
 m_traversal_state.emplace_back(m_current, child_count - 1);
 m_current = std::addressof(m_traits.child_at(*m_current, child_count - 1));
 return *this;
 }
 while (not m_traversal_state.empty()) {
 auto& [parent, child_index] = m_traversal_state.back();
 if (child_index > 0) {
 --child_index;
 m_current = std::addressof(m_traits.child_at(*parent, child_index));
 return *this;
 }
 m_current = parent;
 m_traversal_state.pop_back();
 }
 USL_ASSERT_MSG(false, "Begin iterator cannot be decremented.");
 unreachable();
 }
 TreeIter& operator++()
 requires (traversal_algorithm == TreeTraversal::breadth_first)
 {
 USL_ASSERT_MSG(m_current, "End iterator cannot be incremented.");
 while (not m_traversal_state.empty()) {
 auto& [parent, child_index] = m_traversal_state.front();
 ++child_index;
 if (child_index < m_traits.child_count(*parent)) {
 m_current = std::addressof(m_traits.child_at(*parent, child_index));
 if (m_traits.child_count(*m_current) > 0) {
 m_traversal_state.emplace_back(m_current, no_child);
 }
 return *this;
 }
 m_traversal_state.erase(m_traversal_state.begin());
 }
 m_current = nullptr;
 return *this;
 }
 operator TreeIter<const TreeNode, NodeTraits, algo, Category>() const
 requires (not std::is_const_v<TreeNode>)
 {
 using ConstTreeIter = TreeIter<const TreeNode, NodeTraits, algo, Category>;
 ConstTreeIter result{};
 result.m_current = m_current;
 result.m_traversal_state.reserve(m_traversal_state.size());
 std::ranges::transform(
 m_traversal_state,
 std::back_inserter(result.m_traversal_state),
 [](const TraversalPos& src) {
 return typename ConstTreeIter::TraversalPos{src.parent, src.child_index};
 });
 result.m_traits = m_traits;
 result.m_root = m_root;
 return result;
 }
private:
 // needed for converting non-const to const iter
 TreeIter() = default;
 friend class TreeIter<std::remove_const_t<TreeNode>, NodeTraits, algo, Category>;
 // must be size_t max because relies on unsigned wraparound
 static constexpr size_t no_child = static_cast<size_t>(-1);
 void traverse_to_first_leaf_from_current()
 {
 while (m_traits.child_count(*m_current) > 0) {
 m_traversal_state.emplace_back(m_current, 0);
 m_current = std::addressof(m_traits.child_at(*m_current, 0));
 }
 }
 void traverse_to_last_leaf_from_current()
 {
 while (auto child_count = m_traits.child_count(*m_current)) {
 m_traversal_state.emplace_back(m_current, child_count - 1);
 m_current = std::addressof(m_traits.child_at(*m_current, child_count - 1));
 }
 }
 TreeIter(TreeNode* root, TreeNode* current, NodeTraits&& traits)
 : m_current{current}, m_traits{std::move(traits)}
 {
 if constexpr (is_bidir) {
 m_root = root;
 }
 if constexpr (traversal_algorithm == TreeTraversal::post_order) {
 if (m_current) {
 traverse_to_first_leaf_from_current();
 }
 }
 else if constexpr (traversal_algorithm == TreeTraversal::breadth_first) {
 if (m_current) {
 m_traversal_state.emplace_back(m_current, no_child);
 }
 }
 }
 struct TraversalPos
 {
 TreeNode* parent;
 size_t child_index;
 };
 struct Empty
 {
 };
 TreeNode* m_current;
 std::vector<TraversalPos> m_traversal_state{};
 [[no_unique_address]] NodeTraits m_traits;
 // Only bidir iterators need to store the root. The construct below makes sure fwd iterators
 // do not pay the size penalty of the additional member.
 [[no_unique_address]] std::conditional_t<is_bidir, TreeNode*, Empty> m_root;
};
template<typename TreeNode, typename NodeTraits, typename Category = std::forward_iterator_tag>
using PreOrderTreeIter = TreeIter<TreeNode, NodeTraits, TreeTraversal::pre_order, Category>;
template<typename TreeNode, typename NodeTraits, typename Category = std::forward_iterator_tag>
using PostOrderTreeIter = TreeIter<TreeNode, NodeTraits, TreeTraversal::post_order, Category>;
template<typename TreeNode, typename NodeTraits, typename Category = std::forward_iterator_tag>
using BreadthFirstTreeIter = TreeIter<TreeNode, NodeTraits, TreeTraversal::breadth_first, Category>;
} // namespace usl

tests.cpp

#include "tree_iterator.hpp"
#include <catch2/catch_template_test_macros.hpp>
#include <catch2/catch_test_macros.hpp>
struct Node
{
 /*
 Creates this tree:
 A
 +-------+-------+
 B C D
 | +--+--+ |
 E F G H I
 +---+ |
 J K L
 */
 Node() : parent{nullptr}, payload{'A'}
 {
 Node& root = *this;
 root.children = {
 Node{&root, 'B'},
 Node{&root, 'C'},
 Node{&root, 'D'},
 };
 Node& left_child = root.children[0];
 left_child.children = {Node{&left_child, 'E'}};
 Node& middle_child = root.children[1];
 middle_child.children = {
 Node{&middle_child, 'F'},
 Node{&middle_child, 'G'},
 Node{&middle_child, 'H'},
 };
 Node& right_child = root.children[2];
 right_child.children = {Node{&right_child, 'I'}};
 Node& left_grandchild = left_child.children[0];
 left_grandchild.children = {
 Node{&left_grandchild, 'J'},
 Node{&left_grandchild, 'K'},
 };
 Node& middle_grandchild_1 = middle_child.children[1];
 middle_grandchild_1.children = {
 Node{&middle_grandchild_1, 'L'},
 };
 }
 Node(Node* parent_, char payload_) : parent{parent_}, payload{payload_} {}
 struct Traits
 {
 size_t child_count(const Node& node) { return node.children.size(); }
 Node& child_at(Node& p, size_t child_index) { return p.children[child_index]; }
 const Node& child_at(const Node& p, size_t child_index) { return p.children[child_index]; }
 };
 using PreIter = usl::PreOrderTreeIter<Node, Traits, std::bidirectional_iterator_tag>;
 using ConstPreIter = usl::PreOrderTreeIter<const Node, Traits, std::bidirectional_iterator_tag>;
 using PostIter = usl::PostOrderTreeIter<Node, Traits, std::bidirectional_iterator_tag>;
 using ConstPostIter =
 usl::PostOrderTreeIter<const Node, Traits, std::bidirectional_iterator_tag>;
 using BreadthIter = usl::BreadthFirstTreeIter<Node, Traits>;
 using ConstBreadthIter = usl::BreadthFirstTreeIter<const Node, Traits>;
 Node* parent{};
 char payload{'0円'};
 std::vector<Node> children{};
};
TEMPLATE_TEST_CASE(
 "forward tree traversal",
 "[iterators]",
 Node::PreIter,
 Node::ConstPreIter,
 Node::PostIter,
 Node::ConstPostIter,
 Node::BreadthIter,
 Node::ConstBreadthIter)
{
 using IterT = TestType;
 using NodeT = typename IterT::value_type;
 NodeT root{};
 SECTION("tree is traversed forward from the begin iterator") {
 const auto end = IterT::create_end(&root);
 std::vector<char> actual_preincrement{};
 std::vector<char> actual_postincrement{};
 for (auto iter = IterT::create_begin(&root); iter != end; ++iter) {
 actual_preincrement.push_back(iter->payload);
 }
 for (auto iter = IterT::create_begin(&root); iter != end; iter++) {
 actual_postincrement.push_back((*iter).payload);
 }
 std::vector<char> expected;
 if constexpr (IterT::traversal_algorithm == usl::TreeTraversal::pre_order) {
 expected = {'A', 'B', 'E', 'J', 'K', 'C', 'F', 'G', 'L', 'H', 'D', 'I'};
 }
 else if constexpr (IterT::traversal_algorithm == usl::TreeTraversal::post_order) {
 expected = {'J', 'K', 'E', 'B', 'F', 'L', 'G', 'H', 'C', 'I', 'D', 'A'};
 }
 else if constexpr (IterT::traversal_algorithm == usl::TreeTraversal::breadth_first) {
 expected = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L'};
 }
 CHECK(actual_preincrement == expected);
 CHECK(actual_postincrement == expected);
 }
 SECTION("traversal does not ascend through a root with a parent") {
 auto& subroot = root.children[1];
 const auto end = IterT::create_end(&subroot);
 std::vector<char> actual{};
 for (auto iter = IterT::create_begin(&subroot); iter != end; ++iter) {
 actual.push_back(iter->payload);
 }
 std::vector<char> expected;
 if constexpr (IterT::traversal_algorithm == usl::TreeTraversal::pre_order) {
 expected = {'C', 'F', 'G', 'L', 'H'};
 }
 else if constexpr (IterT::traversal_algorithm == usl::TreeTraversal::post_order) {
 expected = {'F', 'L', 'G', 'H', 'C'};
 }
 else if constexpr (IterT::traversal_algorithm == usl::TreeTraversal::breadth_first) {
 expected = {'C', 'F', 'G', 'H', 'L'};
 }
 REQUIRE(actual == expected);
 }
}
TEMPLATE_TEST_CASE(
 "backward tree traversal",
 "[iterators]",
 Node::PreIter,
 Node::ConstPreIter,
 Node::PostIter,
 Node::ConstPostIter
 // Bidirectional not implemented for breadth-first.
)
{
 using IterT = TestType;
 using NodeT = typename IterT::value_type;
 NodeT root{};
 SECTION("tree is traversed in reverse from the end iterator") {
 const auto begin = IterT::create_begin(&root);
 std::vector<char> actual_predecrement{};
 std::vector<char> actual_postdecrement{};
 {
 auto iter = IterT::create_end(&root);
 do {
 --iter;
 actual_predecrement.push_back(iter->payload);
 } while (iter != begin);
 }
 {
 auto iter = IterT::create_end(&root);
 do {
 iter--;
 actual_postdecrement.push_back(iter->payload);
 } while (iter != begin);
 }
 std::vector<char> expected;
 if constexpr (IterT::traversal_algorithm == usl::TreeTraversal::pre_order) {
 expected = {'I', 'D', 'H', 'L', 'G', 'F', 'C', 'K', 'J', 'E', 'B', 'A'};
 }
 else if constexpr (IterT::traversal_algorithm == usl::TreeTraversal::post_order) {
 expected = {'A', 'D', 'I', 'C', 'H', 'G', 'L', 'F', 'B', 'E', 'K', 'J'};
 }
 CHECK(actual_predecrement == expected);
 CHECK(actual_postdecrement == expected);
 }
 SECTION("tree is traversed from begin to end and back") {
 const auto begin = IterT::create_begin(&root);
 const auto end = IterT::create_end(&root);
 auto iter = IterT::create_begin(&root);
 std::vector<char> actual;
 while (iter != end) {
 actual.push_back(iter->payload);
 ++iter;
 }
 do {
 --iter;
 actual.push_back(iter->payload);
 } while (iter != begin);
 std::vector<char> expected;
 if constexpr (IterT::traversal_algorithm == usl::TreeTraversal::pre_order) {
 expected = {
 'A', 'B', 'E', 'J', 'K', 'C', 'F', 'G', 'L', 'H', 'D', 'I', // forward
 'I', 'D', 'H', 'L', 'G', 'F', 'C', 'K', 'J', 'E', 'B', 'A', // reverse
 };
 }
 else if constexpr (IterT::traversal_algorithm == usl::TreeTraversal::post_order) {
 expected = {
 'J', 'K', 'E', 'B', 'F', 'L', 'G', 'H', 'C', 'I', 'D', 'A', // forward
 'A', 'D', 'I', 'C', 'H', 'G', 'L', 'F', 'B', 'E', 'K', 'J', // reverse
 };
 }
 REQUIRE(actual == expected);
 }
 SECTION("direction can be reversed mid-traversal") {
 auto iter = IterT::create_begin(&root);
 ++iter;
 ++iter;
 ++iter; // pointing to 'J'
 std::vector<char> actual{iter->payload};
 --iter;
 actual.push_back(iter->payload);
 ++iter;
 actual.push_back(iter->payload);
 ++iter;
 actual.push_back(iter->payload);
 --iter;
 actual.push_back(iter->payload);
 std::vector<char> expected;
 if constexpr (IterT::traversal_algorithm == usl::TreeTraversal::pre_order) {
 expected = {'J', 'E', 'J', 'K', 'J'};
 }
 else if constexpr (IterT::traversal_algorithm == usl::TreeTraversal::post_order) {
 expected = {'B', 'E', 'B', 'F', 'B'};
 }
 REQUIRE(actual == expected);
 }
}
TEST_CASE("non-const tree iter converts to const tree iter", "[iterators]")
{
 Node root{};
 // Post-order makes sure we start with a populated traversal stack.
 auto iter = Node::PostIter::create_begin(&root);
 ++iter;
 const auto cend = Node::ConstPostIter::create_end(&root);
 std::vector<char> actual{};
 for (Node::ConstPostIter citer = iter; citer != cend; ++citer) {
 actual.push_back(citer->payload);
 }
 const std::vector<char> expected{'K', 'E', 'B', 'F', 'L', 'G', 'H', 'C', 'I', 'D', 'A'};
 CHECK(actual == expected);
}

minimal CMakeLists.txt (just for convenience)

cmake_minimum_required(VERSION 3.12)
set(CMAKE_CXX_STANDARD 20)
set(CMAKE_CXX_STANDARD_REQUIRED ON)
set(CMAKE_CXX_EXTENSIONS OFF)
project(tree_iterator)
find_package(Catch2 3 REQUIRED)
add_executable(tree_iterator tree_iterator.hpp tests.cpp)
target_link_libraries(tree_iterator PRIVATE Catch2::Catch2WithMain)

Answer 1

Prefer a range interface over iterators

You are providing an iterator interface, but iterators are often harder to work with directly than with a range interface. Instead of:

using IterT = usl::PreOrderTreeIter<Node, Traits, std::bidirectional_iterator_tag>;
for (auto iter = IterT::create_begin(&root); iter != end; ++iter) {
 actual_preincrement.push_back(iter->payload);
}

It would be much nicer to be able to write a function that returns a range (or more specifically, a view):

for (auto& payload: usl::pre_order_view(root)) {
 actual_preincrement.push_back(payload);
}

Which could then be simplified even further with various range algorithms, for example like so:

std::ranges::copy(usl::pre_order_view(root), std::back_inserter(actual_preincrement));

Or even:

auto actual_preincrement = usl::pre_order_view(root) | std::ranges::to<std::vector>();

The number of times you actually need to use an iterator directly is small. Of course, a range is implemented on top of an iterator, so you still need it, just provide a range API on top of it.

Avoid unnecessary abbreviations

Abbreviations save some typing (although even that is dubious when almost any code editor supports tab completion nowadays), but they make the code harder to read. In general, avoid using them. There are some very common abbreviations that are fine (like i for a loop index, T for a template type if it's the only one, lhs and rhs for binary operator arguments). While you are not using too many abbreviations, there a still a few that could be removed:

• TreeIter -> TreeIterator
• algo -> algorithm
• is_fwd -> is_forward
• is_bidir -> is_bidirectional
• src -> source, although maybe position is better

Return type of operator->()

I’m still thinking about the chaining operator->(). It violates the STL iterator requirements, but I’m regularly annoyed by the non-chaining iterators from the standard library. What problems could that cause?

Violating the STL's requirements means that STL algorithms that do use that operator now no longer work with your iterator class. Also, programmers that are used to the behavior of operator->() for other iterators might be surprised by your class's behavior. They might write the wrong code, which might not even cause an immediate compile error.

It allocates memory

Your iterator keeps track of the path from the parent to the current position in the std::vector<TravelPos> m_travel_state. I understand why you do this. However, the drawback of this is that your iterator is now doing memory allocations, which themselves have a performance impact. Not just because of the memory allocation, but also because you cannot make many functions noexcept anymore. And while it simplifies the code somewhat, consider that you could also store the just a pointer to the root node and the current node in the iterator, and use a node's parent pointer to traverse back up. You get the same algorithmic complexity of \$O(\log N)\$ either way.

Robustness

I chose the index based child access to make the iterator a bit more robust against invalidation.

But you store pointers as well. So maybe it is more robust, but it's still not fully robust, so you should not allow the caller to modify the tree while you are iterating over it.

It assumes a tree is stored as nodes pointing to each other

I see you have already thought about making your code work for different possible tree implementations, and you can pass Traits to your iterators that tell it how to access children in a tree node. However, it still assumes that a tree is composed of individual node objects. There are other ways to store trees. Some of them have nodes that store multiple values, some are just a vector of values with an implicit tree structure (for example, a heap), and there are many other forms.

The biggest issue with your code is that you assume you can get the address of a Node. It might be better to treat nodes in Traits as opaque values, and not pass them as a references. For your Node in test.cpp, you could just use std::reference_wrapper<Node> to turn the reference into something value-like.

• besc: Thank you, especially for the ranges suggestion and the hint at non-node ways of storing trees. The latter will definitely need some more research. :)

Answer 2

This attribute is incorrect if we compile with any other compiler than the three that are specifically catered to:

[[noreturn]] inline void unreachable()
{
#if defined(__GNUC__) || defined(__clang__)
 __builtin_unreachable();
#elif defined(_MSC_VER)
 __assume(0);
#endif
}

I think we're missing a couple of lines:

#else
 assert(0);

---

The Category template argument seems like an unnecessary burden on the caller. Since bidirectional iterators are forward iterators, it makes sense to automatically use the most capable (i.e. bidirectional for the pre/post-order traversal, and forward for the breadth-first). Or provide the necessary functionality so that we can always be bidirectional.

On further reading, I see that this distinction allows us to optimise out a single pointer from our iterator class. But this seems somewhat premature given that it already contains a std::vector (and which violates user expectations that iterators are cheap to copy).

---

I'm not a big fan of providing alternative implementations this way:

TreeIter& operator++()
requires (traversal_algorithm == TreeTraversal::pre_order);
TreeIter& operator--()
requires ((traversal_algorithm == TreeTraversal::pre_order) && is_bidir);
TreeIter& operator++()
requires (traversal_algorithm == TreeTraversal::post_order);
TreeIter& operator--()
requires ((traversal_algorithm == TreeTraversal::post_order) && is_bidir);
TreeIter& operator++()
requires (traversal_algorithm == TreeTraversal::breadth_first);

It might be worth considering use of inheritance here to provide the common code as a base class (likely using CRTP for compile-time inheritance). Or perhaps simply add a few comments that alert the user that these are overload-like sets.

• besc: Thank you, and good point about the Category parameter. I’ll make them bidir whenever possible. I rather like the requires clauses, though, because they keep the code so nice and compact – at least in this relatively simply case. For something large and complicated, yes, I’d probably go for CRTP or at least a combination of both.
• Toby Speight: Yes, I see that, and once I realised what was going on, it made sense. I think I might have picked that up quicker if all the like-named members were together, rather than interleaved - but OTOH, I can see the value in putting them in their implementation pairs, too. Probably best resolved with a few small comments such as // pre-order increment and decrement and so on to introduce them.