实现你本人的迭代器 II
实现一个树结构容器，而后为其实现 STL 格调的迭代器实例。
本文是为了给上一篇文章 浅谈如何实现自定义的 iterator 提供补充案例。
tree_t 的实现
我打算实现一个简略而又不简略的树容器，让它成为规范的文件目录结构式的容器类型。但简略就在于，我只筹备实现最最必要的几个树结构的接口，诸如遍历啦什么的。
这是一个很规范的文件目录的仿真品，致力于齐全仿照文件夹的体现。它和什么 binary tree，AVL，又或是红黑树什么的齐全是驴唇不对马嘴。
首先能够确定的是 tree_t 依赖于 generic_node_t，tree_t 本身并不真的负责树的算法，它只是持有一个 root node 指针。所有与树操作相干的内容都在 generic_node_t 中。
tree_t
因而上面首先给出 tree_t 的具体实现：
namespace dp::tree{ template<typename Data, typename Node = detail::generic_node_t<Data>> class tree_t : detail::generic_tree_ops<Node> { public: using Self = tree_t<Data, Node>; using BaseT = detail::generic_tree_ops<Node>; using NodeT = Node; using NodePtr = Node *; using iterator = typename Node::iterator; using const_iterator = typename Node::const_iterator; using reverse_iterator = typename Node::reverse_iterator; using const_reverse_iterator = typename Node::const_reverse_iterator; using difference_type = std::ptrdiff_t; using value_type = typename iterator::value_type; using pointer = typename iterator::pointer; using reference = typename iterator::reference; using const_pointer = typename iterator::const_pointer; using const_reference = typename iterator::const_reference; ~tree_t() { clear(); } void clear() override { if (_root) delete _root; BaseT::clear(); } void insert(Data const &data) { if (!_root) { _root = new NodeT{data}; return; } _root->insert(data); } void insert(Data &&data) { if (!_root) { _root = new NodeT{data}; return; } _root->insert(std::move(data)); } template<typename... Args> void emplace(Args &&...args) { if (!_root) { _root = new NodeT{std::forward<Args>(args)...}; return; } _root->emplace(std::forward<Args>(args)...); } Node const &root() const { return *_root; } Node &root() { return *_root; } iterator begin() { return _root->begin(); } iterator end() { return _root->end(); } const_iterator begin() const { return _root->begin(); } const_iterator end() const { return _root->end(); } reverse_iterator rbegin() { return _root->rbegin(); } reverse_iterator rend() { return _root->rend(); } const_reverse_iterator rbegin() const { return _root->rbegin(); } const_reverse_iterator rend() const { return _root->rend(); } private: NodePtr _root{nullptr}; }; // class tree_t} // namespace dp::tree其中的必要的接口基本上都转向到 _root 中了。
generic_node_t
再来钻研 node 的实现。
一个树节点持有如下的数据：
namespace dp::tree::detail{ template<typename Data> struct generic_node_t { using Node = generic_node_t<Data>; using NodePtr = Node *; //std::unique_ptr<Node>; using Nodes = std::vector<NodePtr>; private: Data _data{}; NodePtr _parent{nullptr}; Nodes _children{}; // ... }}据此咱们能够实现节点的插入、删除以及根本的拜访操作。
这些内容因为篇幅起因就略去了。
如果你感兴趣的话，请查阅源代码 dp-tree.hh 和 tree.cc。
正向迭代器
上面给出它的正向迭代器的残缺实现，以便对上一篇文章做出更残缺的交代。
正向迭代器是指 begin() 和 end() 及其代表的若干操作。简略来说，它反对从开始到完结的单向的容器元素遍历。
对于树结构来说，begin() 是指根节点。遍历算法是根 - 左子树 - 右子树，也就是前序遍历算法。这和 AVL 等次要应用中序遍历有着齐全不同的思路。
据此，end() 指的是 right of 最右最低的子树的最右最低叶子节点。什么意思？在最初一个叶子节点向后再递增一次，本质上是将 _invalid 标记置为 true 来示意曾经到达起点。
为了防止 STL end() 迭代器求值会产生拜访异样的状况，咱们实现的 end() 是能够平安求值的，只管求值后果实际上没有意义（end() - 1才是正确的back()元素）。
namespace dp::tree::detail{ template<typename Data> struct generic_node_t { // ... struct preorder_iter_data { // iterator traits using difference_type = std::ptrdiff_t; using value_type = Node; using pointer = value_type *; using reference = value_type &; using iterator_category = std::forward_iterator_tag; using self = preorder_iter_data; using const_pointer = value_type const *; using const_reference = value_type const &; preorder_iter_data() {} preorder_iter_data(pointer ptr_, bool invalid_ = false) : _ptr(ptr_) , _invalid(invalid_) {} preorder_iter_data(const preorder_iter_data &o) : _ptr(o._ptr) , _invalid(o._invalid) {} preorder_iter_data &operator=(const preorder_iter_data &o) { _ptr = o._ptr, _invalid = o._invalid; return *this; } bool operator==(self const &r) const { return _ptr == r._ptr && _invalid == r._invalid; } bool operator!=(self const &r) const { return _ptr != r._ptr || _invalid != r._invalid; } reference data() { return *_ptr; } const_reference data() const { return *_ptr; } reference operator*() { return data(); } const_reference operator*() const { return data(); } pointer operator->() { return &(data()); } const_pointer operator->() const { return &(data()); } self &operator++() { return _incr(); } self operator++(int) { self copy{_ptr, _invalid}; ++(*this); return copy; } static self begin(const_pointer root_) { return self{const_cast<pointer>(root_)}; } static self end(const_pointer root_) { if (root_ == nullptr) return self{const_cast<pointer>(root_)}; pointer p = const_cast<pointer>(root_), last{nullptr}; while (p) { last = p; if (p->empty()) break; p = &((*p)[p->size() - 1]); } auto it = self{last, true}; ++it; return it; } private: self &_incr() { if (_invalid) { return (*this); } auto *cc = _ptr; if (cc->empty()) { Node *pp = cc; size_type idx; go_up_level: pp = pp->parent(); idx = 0; for (auto *vv : pp->_children) { ++idx; if (vv == _ptr) break; } if (idx < pp->size()) { _ptr = &((*pp)[idx]); } else { if (pp->parent()) { goto go_up_level; } _invalid = true; } } else { _ptr = &((*cc)[0]); } return (*this); } pointer _ptr{}; bool _invalid{}; // size_type _child_idx{}; }; using iterator = preorder_iter_data; using const_iterator = iterator; iterator begin() { return iterator::begin(this); } const_iterator begin() const { return const_iterator::begin(this); } iterator end() { return iterator::end(this); } const_iterator end() const { return const_iterator::end(this); } // ... }}这个正向迭代器从根节点开始从上至下、从左至右对树结构进行遍历。
有句话怎么说的来着，高手随随便便一站着全身都是漏洞而后就全数都冇漏洞了。对于 preorder_iter_data 来说也有点这个滋味：细节太多之后，让他们全都圆满之后，而后就无奈评讲代码实现的理由了。
只是讲笑，实际上是讲述起来太消耗篇幅，所以你间接看代码，我就省笔墨。
反向迭代器
相似于正向迭代器，然而具体算法不同。
本文中限于篇幅不予列出，如果你感兴趣的话，请查阅源代码 dp-tree.hh 和 tree.cc。
须要关照到的事件
再次复述齐全手写迭代器的注意事项，并且补充一些上回文中没有精密讲解的内容，包含：
- begin() 和 end()
迭代器嵌入类（不用被限定为嵌入），至多实现：
- 递增运算符重载，以便行走
- 递加运算符重载，如果是双向行走（bidirectional_iterator_tag）或随机行走（random_access_iterator_tag）
operator*运算符重载，以便迭代器求值：使能(*it).xxx- 配套实现
operator->，以使能it->xxx operator!=运算符重载，以便计算迭代范畴；必要时也能够显式重载operator==（默认时编译器主动从!=运算符上生成一个配套替代品）
补充阐明：
为了能与 STL 的
<algorithm>算法兼容，你须要手动定义 iterator traits，如同这样：struct preorder_iter_data { // iterator traits using difference_type = std::ptrdiff_t; using value_type = Node; using pointer = value_type *; using reference = value_type &; using iterator_category = std::forward_iterator_tag;}这么做的目标在于让 std::find_if 等等 algorithms 可能透过你宣告的
iterator_catagory而正确援用 distance、advance、++ or -- 等等实现。如果你的 iterator 不反对双向行走，那么 -- 会被模仿：从容器的第一个元素开始遍历并注销，直到行走到 it 所在的地位，而后将 last_it 返回。其它的少数谓词也都会有相似的模仿版本。
本来，这些 traits 是通过从 std::iterator 派生而主动被定义的。然而自 C++17 起，临时倡议间接手工编写和定义它们。
你能够不用定义它们，这并不是强制。
绝大多数状况下，你申明 std::forward_iterator_tag 类型，并定义 ++ 运算符与其配套；如果你定义为 std::bidirectional_iterator_tag 类型，那么还须要定义 -- 运算符。
自增自减运算符须要同时定义前缀与后缀，请参考上一篇文章 浅谈如何实现自定义的 iterator 中的无关章节。
- 在迭代器中，定义 begin() 与 end()，以便在容器类中借用它们（在本文的 tree_t 示例中，容器类指的是 generic_node_t。
- 如果你想要定义 rbegin/rend，它们并不是 -- 的替代品，它们通常须要你齐全独立于正向迭代器而独自定义另外一套。在 tree_t 中对此有明确的实现，但本文中限于篇幅不予列出，如果你感兴趣的话，请查阅源代码 dp-tree.hh 和 tree.cc。
应用/测试代码
一些测试用的代码列举一下：
void test_g_tree() { dp::tree::tree_t<tree_data> t; UNUSED(t); assert(t.rbegin() == t.rend()); assert(t.begin() == t.end()); std::array<char, 128> buf; // 1 // 2 3 4 5 6 7 for (auto v : {1, 2, 3, 4, 5, 6, 7}) { std::sprintf(buf.data(), "str#%d", v); // t.insert(tree_data{v, buf.data()}); tree_data vd{v, buf.data()}; t.insert(std::move(vd)); // tree_info(t); } { auto v = 8; std::sprintf(buf.data(), "str#%d", v); tree_data td{v, buf.data()}; t.insert(td); v = 9; std::sprintf(buf.data(), "str#%d", v); t.emplace(v, buf.data()); { auto b = t.root().begin(), e = t.root().end(); auto &bNode = (*b), &eNode = (*e); std::cout << "::: " << (*bNode) << '\n'; // print bNode.data() std::cout << "::: " << (eNode.data()) << '\n'; } { int i; i = 0; for (auto &vv : t) { std::cout << i << ": " << (*vv) << ", " << '\n'; if (i == 8) { std::cout << ' '; } i++; } std::cout << '\n'; } using T = decltype(t); auto it = std::find_if(t.root().begin(), t.root().end(), [](typename T::NodeT &n) -> bool { return (*n) == 9; }); v = 10; std::sprintf(buf.data(), "str#%d", v); it->emplace(v, buf.data()); v = 11; std::sprintf(buf.data(), "str#%d", v); (*it).emplace(v, buf.data()); #if defined(_DEBUG) auto const itv = t.find([](T::const_reference n) { return (*n) == 10; }); assert(*(*itv) == 10); #endif } // int i; i = 0; for (auto &v : t) { std::cout << i << ": " << (*v) << ", " << '\n'; if (i == 8) { std::cout << ' '; } i++; } std::cout << '\n'; i = 0; for (auto it = t.rbegin(); it != t.rend(); ++it, ++i) { auto &v = (*it); std::cout << i << ": " << (*v) << ", " << '\n'; if (i == 8) { std::cout << ' '; } } std::cout << '\n';}这些代码只是单纯地展现了用法，并没有依照单元测试的做法来书写——也无此必要。
后记
本文给出了一个实在工作的容器类曾经相应的迭代器实现，我置信它们将是你的绝佳的编码实现范本。
- 源代码 dp-tree.hh 和 tree.cc