C++ STL容器(三) —— 迭代器底层剖析

本篇聚焦于STL中的迭代器，同样基于MSVC源码。

迭代器模式

首先迭代器模式是设计模式中的一种，属于行为型设计模式，简单的迭代器模式结构如下。

应用场景

迭代器模式适合的应用场景有：

1. 当集合背后为复杂的数据结构，且你希望对客户端隐藏其复杂性时(出于使用便利性或安全性的考虑)，可以使用迭代器模式。
   迭代器封装了与复杂数据结构进行交互的细节，为客户端提供多个访问集合元素的简单方法，即具体迭代器内部实现对用户是透明的，用户不用去了解针对每个容器要怎么迭代，只需要用迭代器的简单方法就能通杀。这种方式不仅对客户端来说非常方便，而且能避免客户端在直接与集合交互时执行错误或有害的操作，从而起到保护集合的作用。
2. 使用该模式可以减少程序中重复的遍历代码。
   重要迭代算法的代码往往体积非常庞大。当这些代码被放置在程序业务逻辑中时，它会让原始代码的职责模糊不清，降低其可维护性。因此，将遍历代码移到迭代器中可使程序代码更加精炼和简洁。
3. 如果你希望代码能够遍历不同的甚至时无法预知的数据结构，可以使用迭代器模式。
   该模式为集合和迭代器提供了一些通用接口。如果你在代码中使用了这些接口，那么将其他实现了这些接口的集合和迭代器传递给它时，它仍将可以正常运行。

实现方式

1. 声明迭代器接口。该接口必须提供至少一个方法来获取集合中的下个元素。但为了使用方便，可以添加一些其他方法，例如获取前一个元素、记录当前位置和判断迭代是否结束。(后面也可以看到MSVC中的实现提供了不止一个方法)
2. 声明集合接口并描述一个获取迭代器的方法，其返回值必须是迭代器接口。如果可能有多组不同的迭代器，可以声明多个类似的方法(比如STL中的容器可以有 begin、cbegin()、rbegin() 等多种获取不同迭代器的方法)。
3. 为希望使用迭代器进行遍历的集合实现具体迭代器类。迭代器对象必须与单个集合实体链接。链接关系通常通过迭代器的构造函数建立。如STL中的不同容器，有各自不同的迭代器，后面就能看到。
4. 在你的集合类中实现集合接口。其主要思想是针对特定集合为客户端代码提供创建迭代器的快捷方式。集合对象必须将自身传递给迭代器的构造函数来创建两者之间的链接。这也好理解，迭代器既然想迭代，肯定要持有对应的容器/集合，那么在什么时候给这个迭代器，最好当然是在构造的时候就给迭代器了。
5. 检查客户端代码，使用迭代器替代所有集合遍历代码。每当客户端需要遍历集合元素时都会获取一个迭代器。

优缺点

优点：

• 单一职责原则：通过将体积庞大的遍历算法代码抽取为独立的类，可对客户端代码和集合进行整理。
• 开闭原则：可实现新型的集合和迭代器并将其传给现有代码，无需修改现有代码。
• 可以并行遍历同一集合，因为每个迭代器对象都包含其自身的遍历状态(读操作并行，写操作还是要同步)。
• 可以暂停遍历，并在需要时继续。

缺点：

• 如果你的程序只与简单的集合进行交互，应用该模式可能会事倍功半。
• 对于某些特殊集合，使用迭代器可能比直接遍历的效率低。

UML类图

下面整理了MSVC中迭代器实现的相关类图，这里暂时先考虑 list 和 vector 两个容器的迭代器。

1. 可以看到 list 的迭代器和 vector 的迭代器，都有一个公共的基类 _Iterator_base。
2. 这里 list 有 unchecked 和 checked 两种迭代器，checked 迭代器用于 Debug 版本下的运行时错误排查，比如访问越界等。这里包括后面暂时不考虑这块代码，这块具体可以看官方文档的解释。
3. reverse_iterator 反向迭代器是通过持有正向迭代器，然后重载相关的一些方法来实现逆向迭代的。
4. const迭代器是非const迭代器的父类，这个也好理解，毕竟只是一个是只读，一个是可读写的，当然在功能上就是包含关系。

代码解析

下面主要分析下 list 和 vector 这两个容器的迭代器以及反向迭代器的实现。

list 迭代器

const 迭代器

1. 构造函数，第一部分有提到，我们需要把容器和迭代器建立链接，这块就是放在构造函数中做，这里 _Adopt 就是用在 Debug 下的错误检查，在 Release 下是一个空操作。

    _List_unchecked_const_iterator() noexcept : _Ptr() {}_List_unchecked_const_iterator(_Nodeptr _Pnode, const _Mylist* _Plist) noexcept : _Ptr(_Pnode) {this->_Adopt(_Plist);}

2. 获取指向元素，重载 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_traits<pointer>::pointer_to(**this);}

3. 向后迭代，这里有前置 ++ 和后置 ++ 前置的话就是返回自己的引用，后置的是返回迭代前的副本。

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

4. 向前迭代，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;}

5. 迭代器判等，我们在用迭代器遍历容器的过程经常需要判断当前迭代器是否和 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_cast<reference>(_Mybase::operator*());}_NODISCARD pointer operator->() const noexcept {return pointer_traits<pointer>::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;}

而随机迭代器，相较于双向迭代器，提供额外的一些功能以支持随机访问。

1. + += - -= 操作用于一定的随机访问，而对于 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_cast<difference_type>(_Ptr - _Right._Ptr);}

2. 迭代器的比较，这里不仅支持了相等的判断，而支持了 < <= > >= 的判断，实现也就是指针的大小判断。

    _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);}

3. 基于索引的随机访问，作为随机迭代器，当然应该支持基于索引的随机访问

    _NODISCARD _CONSTEXPR20 reference operator[](const difference_type _Off) const noexcept {return *(*this + _Off);}

非const迭代器

和 const 迭代器差不多，也就是返回的是一个非常量引用/非常量指针。

    _NODISCARD _CONSTEXPR20 reference operator*() const noexcept {return const_cast<reference>(_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_cast<reference>(_Mybase::operator[](_Off));}

反向迭代器

反向迭代器 reverse_iterator 持有正向迭代器，通过实现新的上面的迭代方法，实现方向迭代。

1. 构造函数，会有一个 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;}

2. 获取元素，下面看到 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->();}}

3. 正向/反向迭代，逆向迭代器的正向迭代，其实就相当于对其持有的正向迭代器进行反向迭代，即 --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;}

4. 随机迭代，也是和正向/反向迭代一样，逆向的迭代器 + 的大小，对应其持有正向迭代器 - 的大小，而对于按索引的随机访问，比如索引是 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_init<reference>(current[_Off]))) /* strengthened */ {return current[static_cast<difference_type>(-_Off - 1)];}

迭代器失效

最后再看下迭代器失效的问题，比如对于一个 vector 容器，我们再用迭代器遍历它的过程中，加入/删除元素就会有迭代器失效的问题，对于加入元素，因为 vector 容器本身是有扩容机制的，那么当 size>capacity 就会触发扩容，那么会申请新的一块内存，然后把元素移动到这个新内存区域。那么会导致我们容器给出的几个指针都发生了改变，但我们的迭代器里还保存着这个旧的指针，但旧的指针指向的已经是一块非法的内存区域了，这就是 vector 插入引发的迭代器失效问题。

vector 如果是删除元素，那么需要考虑到删除元素后，会把后面的元素向前移动，而当前迭代器持有的指针指向的元素可能会发生改变，那么就可能产生出乎你意料的结果。

而对于 list 来说，插入一般不会改变当前迭代器，但删除会导致当前迭代器失效(如果删除了当前迭代器指向的节点，那么当前迭代器持有的指针就是不合法的，迭代器失效)。

参考资料

Checked Iterators
迭代器模式