建网站需要注意什么,抖音seo培训,厦门网站建设解决方案,网站如何吸引人本篇聚焦于STL中的迭代器#xff0c;同样基于MSVC源码。 文章目录 迭代器模式应用场景实现方式优缺点 UML类图代码解析list 迭代器const 迭代器非 const 迭代器 vector 迭代器const 迭代器非const迭代器 反向迭代器 迭代器失效参考资料 迭代器模式
首先迭代器模式是设计模式中… 本篇聚焦于STL中的迭代器同样基于MSVC源码。 文章目录 迭代器模式应用场景实现方式优缺点 UML类图代码解析list 迭代器const 迭代器非 const 迭代器 vector 迭代器const 迭代器非const迭代器 反向迭代器 迭代器失效参考资料 迭代器模式
首先迭代器模式是设计模式中的一种属于行为型设计模式简单的迭代器模式结构如下。
应用场景
迭代器模式适合的应用场景有
当集合背后为复杂的数据结构且你希望对客户端隐藏其复杂性时(出于使用便利性或安全性的考虑)可以使用迭代器模式。 迭代器封装了与复杂数据结构进行交互的细节为客户端提供多个访问集合元素的简单方法即具体迭代器内部实现对用户是透明的用户不用去了解针对每个容器要怎么迭代只需要用迭代器的简单方法就能通杀。这种方式不仅对客户端来说非常方便而且能避免客户端在直接与集合交互时执行错误或有害的操作从而起到保护集合的作用。使用该模式可以减少程序中重复的遍历代码。 重要迭代算法的代码往往体积非常庞大。当这些代码被放置在程序业务逻辑中时它会让原始代码的职责模糊不清降低其可维护性。因此将遍历代码移到迭代器中可使程序代码更加精炼和简洁。如果你希望代码能够遍历不同的甚至时无法预知的数据结构可以使用迭代器模式。 该模式为集合和迭代器提供了一些通用接口。如果你在代码中使用了这些接口那么将其他实现了这些接口的集合和迭代器传递给它时它仍将可以正常运行。
实现方式
声明迭代器接口。该接口必须提供至少一个方法来获取集合中的下个元素。但为了使用方便可以添加一些其他方法例如获取前一个元素、记录当前位置和判断迭代是否结束。(后面也可以看到MSVC中的实现提供了不止一个方法)声明集合接口并描述一个获取迭代器的方法其返回值必须是迭代器接口。如果可能有多组不同的迭代器可以声明多个类似的方法(比如STL中的容器可以有 begin、cbegin()、rbegin() 等多种获取不同迭代器的方法)。为希望使用迭代器进行遍历的集合实现具体迭代器类。迭代器对象必须与单个集合实体链接。链接关系通常通过迭代器的构造函数建立。如STL中的不同容器有各自不同的迭代器后面就能看到。在你的集合类中实现集合接口。其主要思想是针对特定集合为客户端代码提供创建迭代器的快捷方式。集合对象必须将自身传递给迭代器的构造函数来创建两者之间的链接。这也好理解迭代器既然想迭代肯定要持有对应的容器/集合那么在什么时候给这个迭代器最好当然是在构造的时候就给迭代器了。检查客户端代码使用迭代器替代所有集合遍历代码。每当客户端需要遍历集合元素时都会获取一个迭代器。
优缺点
优点
单一职责原则通过将体积庞大的遍历算法代码抽取为独立的类可对客户端代码和集合进行整理。开闭原则可实现新型的集合和迭代器并将其传给现有代码无需修改现有代码。可以并行遍历同一集合因为每个迭代器对象都包含其自身的遍历状态(读操作并行写操作还是要同步)。可以暂停遍历并在需要时继续。
缺点
如果你的程序只与简单的集合进行交互应用该模式可能会事倍功半。对于某些特殊集合使用迭代器可能比直接遍历的效率低。 UML类图
下面整理了MSVC中迭代器实现的相关类图这里暂时先考虑 list 和 vector 两个容器的迭代器。
可以看到 list 的迭代器和 vector 的迭代器都有一个公共的基类 _Iterator_base。这里 list 有 unchecked 和 checked 两种迭代器checked 迭代器用于 Debug 版本下的运行时错误排查比如访问越界等。这里包括后面暂时不考虑这块代码这块具体可以看官方文档的解释。reverse_iterator 反向迭代器是通过持有正向迭代器然后重载相关的一些方法来实现逆向迭代的。const迭代器是非const迭代器的父类这个也好理解毕竟只是一个是只读一个是可读写的当然在功能上就是包含关系。 代码解析
下面主要分析下 list 和 vector 这两个容器的迭代器以及反向迭代器的实现。
list 迭代器
const 迭代器
构造函数第一部分有提到我们需要把容器和迭代器建立链接这块就是放在构造函数中做这里 _Adopt 就是用在 Debug 下的错误检查在 Release 下是一个空操作。 _List_unchecked_const_iterator() noexcept : _Ptr() {}_List_unchecked_const_iterator(_Nodeptr _Pnode, const _Mylist* _Plist) noexcept : _Ptr(_Pnode) {this-_Adopt(_Plist);}获取指向元素重载 operator* 因为是链表返回就是保存在每个节点中的值的引用这里因为是 const 迭代器其 reference 等于 const value_type如果保存的值是一个结构体/类也可以用 - 的方式访问其成员这里 **this 第一个 * 获取到迭代器本身第二个 * 调用了 operator* 获取到 _Ptr-_Myval而 pointer_to 相当于是一个取址我们就得到一个指向 _Ptr-_Myval 的指针。 _NODISCARD reference operator*() const noexcept {return _Ptr-_Myval;}_NODISCARD pointer operator-() const noexcept {return pointer_traitspointer::pointer_to(**this);}向后迭代这里有前置 和后置 前置的话就是返回自己的引用后置的是返回迭代前的副本。 _List_unchecked_const_iterator operator() noexcept {_Ptr _Ptr-_Next;return *this;}_List_unchecked_const_iterator operator(int) noexcept {_List_unchecked_const_iterator _Tmp *this;_Ptr _Ptr-_Next;return _Tmp;}向前迭代list 的迭代器是一个双向的迭代器所以也支持向前迭代那么其实就和向后迭代实现差不多了。 _List_unchecked_const_iterator operator--() noexcept {_Ptr _Ptr-_Prev;return *this;}_List_unchecked_const_iterator operator--(int) noexcept {_List_unchecked_const_iterator _Tmp *this;_Ptr _Ptr-_Prev;return _Tmp;}迭代器判等我们在用迭代器遍历容器的过程经常需要判断当前迭代器是否和 end 迭代器相等来判断遍历是否结束因此需要在迭代器中实现判断与另一个迭代器是否相等的方法对于 list 容器就是简单看迭代器持有的指针是否相等。 _NODISCARD bool operator(const _List_unchecked_const_iterator _Right) const noexcept {return _Ptr _Right._Ptr;}非 const 迭代器
非 const 迭代器其实和 const 迭代器的实现没啥区别里面也调用了 const 迭代器的方法除了我们获取内部元素时候const 迭代器返回的是一个常量引用/常量指针而非 const 当然应该返回非 const具体内部也是通过一个 const_cast 来做。 _NODISCARD reference operator*() const noexcept {return const_castreference(_Mybase::operator*());}_NODISCARD pointer operator-() const noexcept {return pointer_traitspointer::pointer_to(**this);}_List_unchecked_iterator operator() noexcept {_Mybase::operator();return *this;}_List_unchecked_iterator operator(int) noexcept {_List_unchecked_iterator _Tmp *this;_Mybase::operator();return _Tmp;}_List_unchecked_iterator operator--() noexcept {_Mybase::operator--();return *this;}_List_unchecked_iterator operator--(int) noexcept {_List_unchecked_iterator _Tmp *this;_Mybase::operator--();return _Tmp;}vector 迭代器
const 迭代器
首先对于构造函数、取元素、前向遍历和后向遍历都和 list 的迭代器差不多(因为随机迭代器的功能肯定包含双向迭代器)除了内部实现有点差别(因为 vector 容器是一块连续的内存所以用一个指针而不是节点就能找到/遍历这个容器而指针本身就支持 --)。 _CONSTEXPR20 _Vector_const_iterator() noexcept : _Ptr() {}_CONSTEXPR20 _Vector_const_iterator(_Tptr _Parg, const _Container_base* _Pvector) noexcept : _Ptr(_Parg) {this-_Adopt(_Pvector);}_NODISCARD _CONSTEXPR20 reference operator*() const noexcept {return *_Ptr;}_NODISCARD _CONSTEXPR20 pointer operator-() const noexcept {return _Ptr;}_CONSTEXPR20 _Vector_const_iterator operator() noexcept {_Ptr;return *this;}_CONSTEXPR20 _Vector_const_iterator operator(int) noexcept {_Vector_const_iterator _Tmp *this;*this;return _Tmp;}_CONSTEXPR20 _Vector_const_iterator operator--() noexcept {--_Ptr;return *this;}_CONSTEXPR20 _Vector_const_iterator operator--(int) noexcept {_Vector_const_iterator _Tmp *this;--*this;return _Tmp;}_NODISCARD _CONSTEXPR20 bool operator(const _Vector_const_iterator _Right) const noexcept {_Compat(_Right);return _Ptr _Right._Ptr;}而随机迭代器相较于双向迭代器提供额外的一些功能以支持随机访问。 - - 操作用于一定的随机访问而对于 vector 容器来说指针本身就指针这样的操作所以实现起来也很简单。 _CONSTEXPR20 _Vector_const_iterator operator(const difference_type _Off) noexcept {_Ptr _Off;return *this;}_NODISCARD _CONSTEXPR20 _Vector_const_iterator operator(const difference_type _Off) const noexcept {_Vector_const_iterator _Tmp *this;_Tmp _Off;return _Tmp;}_NODISCARD_FRIEND _CONSTEXPR20 _Vector_const_iterator operator(const difference_type _Off, _Vector_const_iterator _Next) noexcept {_Next _Off;return _Next;}_CONSTEXPR20 _Vector_const_iterator operator-(const difference_type _Off) noexcept {return *this -_Off;}_NODISCARD _CONSTEXPR20 _Vector_const_iterator operator-(const difference_type _Off) const noexcept {_Vector_const_iterator _Tmp *this;_Tmp - _Off;return _Tmp;}_NODISCARD _CONSTEXPR20 difference_type operator-(const _Vector_const_iterator _Right) const noexcept {return static_castdifference_type(_Ptr - _Right._Ptr);}迭代器的比较这里不仅支持了相等的判断而支持了 的判断实现也就是指针的大小判断。 _NODISCARD bool operator(const _Vector_const_iterator _Right) const noexcept {return _Ptr _Right._Ptr;}_NODISCARD bool operator(const _Vector_const_iterator _Right) const noexcept {return _Right *this;}_NODISCARD bool operator(const _Vector_const_iterator _Right) const noexcept {return !(_Right *this);}_NODISCARD bool operator(const _Vector_const_iterator _Right) const noexcept {return !(*this _Right);}基于索引的随机访问作为随机迭代器当然应该支持基于索引的随机访问 _NODISCARD _CONSTEXPR20 reference operator[](const difference_type _Off) const noexcept {return *(*this _Off);}非const迭代器
和 const 迭代器差不多也就是返回的是一个非常量引用/非常量指针。 _NODISCARD _CONSTEXPR20 reference operator*() const noexcept {return const_castreference(_Mybase::operator*());}_NODISCARD _CONSTEXPR20 pointer operator-() const noexcept {return this-_Ptr;}_CONSTEXPR20 _Vector_iterator operator() noexcept {_Mybase::operator();return *this;}_CONSTEXPR20 _Vector_iterator operator(int) noexcept {_Vector_iterator _Tmp *this;_Mybase::operator();return _Tmp;}_CONSTEXPR20 _Vector_iterator operator--() noexcept {_Mybase::operator--();return *this;}_CONSTEXPR20 _Vector_iterator operator--(int) noexcept {_Vector_iterator _Tmp *this;_Mybase::operator--();return _Tmp;}_CONSTEXPR20 _Vector_iterator operator(const difference_type _Off) noexcept {_Mybase::operator(_Off);return *this;}_NODISCARD _CONSTEXPR20 _Vector_iterator operator(const difference_type _Off) const noexcept {_Vector_iterator _Tmp *this;_Tmp _Off;return _Tmp;}_NODISCARD_FRIEND _CONSTEXPR20 _Vector_iterator operator(const difference_type _Off, _Vector_iterator _Next) noexcept {_Next _Off;return _Next;}_CONSTEXPR20 _Vector_iterator operator-(const difference_type _Off) noexcept {_Mybase::operator-(_Off);return *this;}_NODISCARD _CONSTEXPR20 _Vector_iterator operator-(const difference_type _Off) const noexcept {_Vector_iterator _Tmp *this;_Tmp - _Off;return _Tmp;}_NODISCARD _CONSTEXPR20 reference operator[](const difference_type _Off) const noexcept {return const_castreference(_Mybase::operator[](_Off));}反向迭代器
反向迭代器 reverse_iterator 持有正向迭代器通过实现新的上面的迭代方法实现方向迭代。
构造函数会有一个 current 成员来保存正向迭代器那么构造函数中就需要传入这个正向迭代器。当然相应的可以通过一个 base 方法获取到其持有的反向迭代器。 _CONSTEXPR17 reverse_iterator() default;_CONSTEXPR17 explicit reverse_iterator(_BidIt _Right) noexcept(is_nothrow_move_constructible_v_BidIt) // strengthened: current(_STD move(_Right)) {}template class _Other_CONSTEXPR17 reverse_iterator(const reverse_iterator_Other _Right) noexcept(is_nothrow_constructible_v_BidIt, const _Other) // strengthened: current(_Right.current) {}template class _Other_CONSTEXPR17 reverse_iterator operator(const reverse_iterator_Other _Right) noexcept(is_nothrow_assignable_v_BidIt, const _Other) /* strengthened */ {current _Right.current;return *this;}_NODISCARD _CONSTEXPR17 _BidIt base() const noexcept(is_nothrow_copy_constructible_v_BidIt) /* strengthened */ {return current;}获取元素下面看到 operator* 实现的内容和我们正向迭代器不太一样首先获取到一个正向迭代器的副本然后先前置 -- 然后解引用可以想象对于一个 list 我们传入的一个正向迭代器然后对其相应的反向迭代器解引用得到的是前一个节点元素的引用。比如在 list 容器中提供的 rbegin 得到的是一个 reverse_iterator(end()) 那么解引用后就是链表的最后一个节点。对于 operator- 就是其实也是一样的这里用到了条件编译如果传入的本身就是个指针那么直接返回指针如果是个迭代器返回 _Tmp.operator-() 得到的指针。 _NODISCARD _CONSTEXPR17 reference operator*() const noexcept(is_nothrow_copy_constructible_v_BidIt // noexcept(*--(_STD declval_BidIt()))) /* strengthened */ {_BidIt _Tmp current;return *--_Tmp;}_NODISCARD _CONSTEXPR17 pointer operator-() constnoexcept(is_nothrow_copy_constructible_v_BidIt // noexcept(--(_STD declval_BidIt())) _Has_nothrow_operator_arrow_BidIt, pointer) /* strengthened */{_BidIt _Tmp current;--_Tmp;if constexpr (is_pointer_v_BidIt) {return _Tmp;} else {return _Tmp.operator-();}}正向/反向迭代逆向迭代器的正向迭代其实就相当于对其持有的正向迭代器进行反向迭代即 --current而逆向迭代器的反向迭代当然也就对应着其持有正向迭代器的正向迭代。 _CONSTEXPR17 reverse_iterator operator() noexcept(noexcept(--current)) /* strengthened */ {--current;return *this;}_CONSTEXPR17 reverse_iterator operator(int) noexcept(is_nothrow_copy_constructible_v_BidIt // noexcept(--current)) /* strengthened */ {reverse_iterator _Tmp *this;--current;return _Tmp;}_CONSTEXPR17 reverse_iterator operator--() noexcept(noexcept(current)) /* strengthened */ {current;return *this;}_CONSTEXPR17 reverse_iterator operator--(int) noexcept(is_nothrow_copy_constructible_v_BidIt // noexcept(current)) /* strengthened */ {reverse_iterator _Tmp *this;current;return _Tmp;}随机迭代也是和正向/反向迭代一样逆向的迭代器 的大小对应其持有正向迭代器 - 的大小而对于按索引的随机访问比如索引是 Off 对应正向迭代器中的索引就是 -_Off-1。 _NODISCARD _CONSTEXPR17 reverse_iterator operator(const difference_type _Off) constnoexcept(noexcept(reverse_iterator(current - _Off))) /* strengthened */ {return reverse_iterator(current - _Off);}_CONSTEXPR17 reverse_iterator operator(const difference_type _Off) noexcept(noexcept(current - _Off)) /* strengthened */ {current - _Off;return *this;}_NODISCARD _CONSTEXPR17 reverse_iterator operator-(const difference_type _Off) constnoexcept(noexcept(reverse_iterator(current _Off))) /* strengthened */ {return reverse_iterator(current _Off);}_CONSTEXPR17 reverse_iterator operator-(const difference_type _Off) noexcept(noexcept(current _Off)) /* strengthened */ {current _Off;return *this;}_NODISCARD _CONSTEXPR17 reference operator[](const difference_type _Off) constnoexcept(noexcept(_STD _Fake_copy_initreference(current[_Off]))) /* strengthened */ {return current[static_castdifference_type(-_Off - 1)];}迭代器失效
最后再看下迭代器失效的问题比如对于一个 vector 容器我们再用迭代器遍历它的过程中加入/删除元素就会有迭代器失效的问题对于加入元素因为 vector 容器本身是有扩容机制的那么当 sizecapacity 就会触发扩容那么会申请新的一块内存然后把元素移动到这个新内存区域。那么会导致我们容器给出的几个指针都发生了改变但我们的迭代器里还保存着这个旧的指针但旧的指针指向的已经是一块非法的内存区域了这就是 vector 插入引发的迭代器失效问题。
vector 如果是删除元素那么需要考虑到删除元素后会把后面的元素向前移动而当前迭代器持有的指针指向的元素可能会发生改变那么就可能产生出乎你意料的结果。
而对于 list 来说插入一般不会改变当前迭代器但删除会导致当前迭代器失效(如果删除了当前迭代器指向的节点那么当前迭代器持有的指针就是不合法的迭代器失效)。 参考资料
Checked Iterators 迭代器模式
