ToB企服应用市场:ToB评测及商务社交产业平台

标题: C++ 如何快速实现一个容器的迭代器 [打印本页]
作者: 泉缘泉    时间: 2023-5-19 20:05
标题: C++ 如何快速实现一个容器的迭代器
C++ 如何快速实现一个容器的迭代器

引言

C++的标准库中的容器都会提供迭代器，如果一个容器满足forward_range，那么这个容器一般会提供以下成员类型和函数：
如果该容器还满足bidirectional_range，那么该容器还会额外提供以下成员类型和函数：
笔者曾经在网上搜索过如何实现C++迭代器的文章，但是大多数文章都只是实现了一个最普通的迭代器，从学习原理的角度来说是非常好的，但是相比于标准库或者其他工业化的库来说可能是非常不完整的，所以笔者打算在本文中尽可能将容器中的迭代器部分完整地实现出来。
大多数人可能由于种种原因，C++的标准还停留在C++11，所以我们这里分别使用C++11和最新的标准来编写迭代器。
什么是迭代器

我们这里引用cppreference原话：
  1. Iterators are a generalization of pointers that allow a C++ program to work with different data structures (for example, containers and ranges (since C++20)) in a uniform manner.
复制代码
从定义不难看出，迭代器是一个泛化的指针。
指针

既然迭代器是泛化的指针，那么我们可以通过指针来了解迭代器。我们知道指针共有两个位置可以添加const关键字，共有4种可能，我们将他们对应到迭代器类型：
对于指针类型，const在前面表示说不可以通过该指针去修改所指的变量，而const在后面则表示该指针只能指向某个变量，不能修改指针本身，但是可以修改变量。我们在实现迭代器成员类型和函数的时候只需要关注前两者即可，后面的可以按照C++正常的写法来，可以加const的地方直接加上即可。
基于C++11的具体实现

由于我们的重点在于迭代器部分，所以我们尽可能地选取一个简单的数据结构来实现容器，这里我们实现一个双链表。同时我们也假设读者阅读过关于迭代器实现的文章，对迭代器的核心实现有一定的了解。
首先定义一下链表基本的实现：
  1. template <typename T>
  2. class LinkList {
  3.    
  4.     struct ListNodeBase {
  6.         ListNodeBase* m_next;
  7.         ListNodeBase* m_prev;
  9.         ListNodeBase() { reset(); }
  11.         void reset() { m_prev = m_next = this; }
  12.     };
  14.     struct ListNode : ListNodeBase {
  15.         T m_value;
  16.     };
  18.     // 循环链表头结点，next指向第一个元素，prev指向最后一个元素
  19.     ListNodeBase m_header;  
  20. }
复制代码
接下来是实现迭代器部分，对于很多容器来说，iterator和const_iterator是两个不同类，但是实际上这两个类里面的实现几乎是完全一样的，这也许很容易让人想到继承的写法，但是在C++中我们还有一个更好的方法，那就是使用模板，使用模板的代码量也许会少于使用继承。如果读者是一个非常排斥使用模板的人，不妨尝试着去接受一下，毕竟模板是C++中非常重要的一部分，同时作者也相信在注释和自身基本功到位的情况下，模板的编写和维护也不是非常困难的。
  1. template <bool Const>
  2. struct LinkListIterator {
  3.     // ...
  4. };
  6. using iterator = LinkListIterator<false>;
  7. using const_iterator = LinkListIterator<true>;
复制代码
我们使用一个bool类型的变量（Const）来让LinkListIterator在二者之间进行切换，当该变量为true时，他是const_iterator，否则是iterator。
迭代器一般会定义以下成员类型：
value_type在容器的迭代器中一般是当前容器元素的类型。
reference在容器的迭代器中一般是当前容器元素的引用类型。
pointer在容器的迭代器中一般是当前容器元素的指针类型，C++20之后无需定义。
difference_type表示两个迭代器距离的类型，在容器中一般是ptrdiff_t。
iterator_category表示该迭代器的种类。
需要注意的是，容器中的迭代器并不能够代表所有的情况，比如迭代器reference并不一定是引用类型，iterator_category也仅仅只是一个必要条件。
  1. using value_type = typename std::conditional<Const, const T, T>::type;
  2. using reference = value_type&;
  3. using pointer = value_type*;   
  4. using difference_type = std::ptrdiff_t;
  5. using iterator_category = std::bidirectional_iterator_tag;
复制代码
然后是定义构造函数：
  1. node_type* m_ptr;
  3. LinkListIterator() = default;
  5. LinkListIterator(const LinkListIterator&) = default;
  7. LinkListIterator(node_type* ptr) : m_ptr(ptr) { }
  9. // 我们可以使用一个int* 来初始化一个const int*
  10. // 同理，我们可以使用iterator来初始化一个const_iterator
  11. template <bool IsConst, typename = typename std::enable_if<(Const && !IsConst)>::type>
  12. LinkListIterator(const LinkListIterator<IsConst>& other)
  13.     : m_ptr(other.m_ptr) { }
复制代码
C++迭代器的操作一般是基于运算符的，所以我们需要对相应的运算符进行重载。bidirectional_iterator需要重载以下操作符。
  1. // C++11
  2. bool operator==(const LinkListIterator& other) const {
  3.     return m_ptr == other.m_ptr;
  4. }
  6. bool operator!=(const LinkListIterator& other) const {
  7.     return !this->operator==(other);
  8. }
  10. reference operator*() const { return m_ptr->m_value; }
  12. pointer operator->() const { return &this->operator*(); }
  14. LinkListIterator& operator++() {
  15.     m_ptr = m_ptr->m_next;
  16.     return *this;
  17. }
  19. // it++
  20. LinkListIterator operator++(int) {
  21.     auto old = *this;
  22.     ++*this;
  23.     return old;
  24. }
  26. // --it
  27. LinkListIterator& operator--() {
  28.     m_ptr = m_ptr->m_prev;
  29.     return *this;
  30. }
  32. // it--
  33. LinkListIterator operator--(int) {
  34.     auto old = *this;
  35.     --*this;
  36.     return old;
  37. }
复制代码
到此为止，一个双链表的迭代器就全部实现完毕了，至于reversed_iterator，标准库为我们提供了std::reverse_iterator，我们只需要将我们的迭代器传给它即可。
  1. using iterator = LinkListIterator<false>;
  2. using const_iterator = LinkListIterator<true>;
  3. using reverse_iterator = std::reverse_iterator<iterator>;
  4. using const_reverse_iterator = std::reverse_iterator<const_iterator>;
复制代码
最后我们提供一下相关的成员函数：
  1. iterator begin() { return m_header.m_next; }
  2. iterator end() { return &m_header; }
  4. const_iterator begin() const { return const_cast<LinkList&>(*this).begin(); }
  5. const_iterator end() const { return const_cast<LinkList&>(*this).end(); }
  7. const_iterator cbegin() const { return begin(); }
  8. const_iterator cend() const { return end(); }
  10. reverse_iterator rbegin() { return end(); }
  11. reverse_iterator rend() { return begin(); }
  13. const_reverse_iterator rbegin() const { return end(); }
  14. const_reverse_iterator rend() const { return begin(); }
  16. const_reverse_iterator rcbegin() const { return end(); }
  17. const_reverse_iterator rcend() const { return begin(); }
复制代码
由于const版本的重载实现和non-const版本是完全一致的，并且我们也提供了构造函数使得iterator可以转化为const_iterator，所以我们直接使用const_cast实现了const版本的重载。
基于C++23的具体实现

随着技术的不断进步，很多时候我们不必再使用以往繁琐的方式来实现我们想要的东西。既然reverse_iterator可以直接使用标准库的组件完成，那么const_iterator是否也可以使用类似的方法来实现呢？毕竟看起来我们只需要对iterator进行简单封装就可以把它变成一个const_iterator。
答案是肯定的，那就是std::const_iterator。当然这个东西涉及的细节还是非常多的，不是看起来那么简单，读者有兴趣的话可以自行阅读相关文献。
我们来尝试简化一下上述代码：
  1. // template <bool Const>
  2. struct LinkListIterator {
  3.     using value_type = T;
  4.     using reference = value_type&;
  5.     // using pointer = value_type*;
  6.     using difference_type = ptrdiff_t;
  7.     using iterator_category = std::bidirectional_iterator_tag;
  9.     // 我们可以使用一个int* 来初始化一个const int*
  10.     // 同理，我们可以使用iterator来初始化一个const_iterator
  11.     // template <bool IsConst, typename = typename std::enable_if<(Const && !IsConst)>::type>
  12.     // LinkListIterator(const LinkListIterator<IsConst>& other)
  13.     //     : m_ptr(other.m_ptr) { }
  15. };
  17. using iterator = LinkListIterator;
  18. using const_iterator = std::const_iterator<iterator>;
  19. using reverse_iterator = std::reverse_iterator<iterator>;
  20. using const_reverse_iterator = std::reverse_iterator<const_iterator>;
复制代码
我们只需要实现一个普通的iterator即可，因为标准库已经为我们提供了新的组件，同时额外的构造函数也自然不再需要。
pointer这一成员类型也是不必要的，std::iterator_traits会自动帮我们推导。没有pointer之后我们可以直接使用auto来完成->运算符重载。
  1. auto operator->() const { return &this->operator*(); }
复制代码
同时对于==这一运算符，许多实现无非就是简单比较每一个成员字段是否相等，而!=等于运算符往往也是等价于==运算结果取反。
  1. bool operator==(const LinkListIterator& other) const = default;
  3. // 不写则自动生成
  4. // bool operator!=(const LinkListIterator& other) const { ... }
复制代码
默认生成的==运算符的，有如下规则：
  1. A class can define operator== as defaulted, with a return value of bool. This will generate an equality comparison of each base class and member subobject, in their declaration order. Two objects are equal if the values of their base classes and members are equal. The test will short-circuit if an inequality is found in members or base classes earlier in declaration order.
复制代码
需要注意的是，数组类型的比较是按照range的规则来的，即比较数组中每一个元素是否相等，而非将数组看成一个指针进行比较：
  1. struct F
  2. {
  3.     int data[2];
  4.     constexpr F(int a, int b) : data{a, b} { }
  5.     constexpr bool operator==(const F&) const = default;
  6. };
  8. constexpr F f1(1, 2), f2(3, 4), f3(1, 2);
  10. static_assert(f1 != f2);
  11. static_assert(f1 == f3);
复制代码
我们的简化过程到此为止就结束了，剩下的部分保持不变即可。关于简化之后的代码，读者可以点击这里获取。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4