hedzr

hedzr

#modern-c++ #golang #rust #kotlin #dotnetcore #devops

实现你自己的迭代器 II

实现一个树结构容器，然后为其实现 STL 风格的迭代器实例。

本文是为了给上一篇文章 浅谈如何实现自定义的 iterator 提供补充案例。

tree_t 的实现

我打算实现一个简单而又不简单的树容器，让它成为标准的文件目录结构式的容器类型。但简单就在于，我只准备实现最最必要的几个树结构的接口，诸如遍历啦什么的。

这是一个很标准的文件目录的仿真品，致力于完全仿照文件夹的表现。它和什么 binary tree，AVL，又或是红黑树什么的完全是风马牛不相及。

首先可以确定的是 tree_t 依赖于 generic_node_t，tree_t 自身并不真的负责树的算法，它只是持有一个 root node 指针。所有与树操作相关的内容都在 generic_node_t 中。

tree_t

因此下面首先给出 tree_t 的具体实现：



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



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 的实现。

一个树节点持有如下的数据：



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15



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() 元素）。



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



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。

需要照顾到的事情

再次复述完全手写迭代器的注意事项，并且补充一些上回文中没有精细解说的内容，包括：

  1. begin() 和 end()
  2. 迭代器嵌入类（不必被限定为嵌入），至少实现：
    1. 递增运算符重载，以便行走
    2. 递减运算符重载，如果是双向行走（bidirectional_iterator_tag）或随机行走（random_access_iterator_tag）
    3. operator* 运算符重载，以便迭代器求值：使能 (*it).xxx
    4. 配套实现 operator-> ，以使能 it->xxx
    5. operator!= 运算符重载，以便计算迭代范围；必要时也可以显式重载 operator==（默认时编译器自动从 != 运算符上生成一个配套替代品）

补充说明：

  1. 为了能与 STL 的 <algorithm> 算法兼容，你需要手动定义 iterator traits，如同这样：

    

    1
2
3
4
5
6
7
8
9

    		

    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 起，暂时建议直接手工编写和定义它们。

    你可以不必定义它们，这并不是强制。

  2. 绝大多数情况下，你声明 std::forward_iterator_tag 类型，并定义 ++ 运算符与其配套；如果你定义为 std::bidirectional_iterator_tag 类型，那么还需要定义 – 运算符。

    自增自减运算符需要同时定义前缀与后缀，请参考上一篇文章 浅谈如何实现自定义的 iterator 中的有关章节。

  3. 在迭代器中，定义 begin() 与 end()，以便在容器类中借用它们（在本文的 tree_t 示例中，容器类指的是 generic_node_t。

  4. 如果你想要定义 rbegin/rend，它们并不是 – 的替代品，它们通常需要你完全独立于正向迭代器而单独定义另外一套。在 tree_t 中对此有明确的实现，但本文中限于篇幅不予列出，如果你感兴趣的话，请查阅源代码 dp-tree.hh 和 tree.cc。

使用/测试代码

一些测试用的代码列举一下：



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



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';
}

这些代码只是单纯地展示了用法，并没有按照单元测试的做法来书写——也无此必要。

后记

本文给出了一个真实工作的容器类已经相应的迭代器实现，我相信它们将是你的绝佳的编码实现范本。

:end:

留下评论

猜您还喜欢

关于 std:barrier

4 分钟阅读

关于 std::barrier 和 std::latch，在 C++20 构造新版本的带同步功能的线程池（略略略），conditional_wait 等等 …