【C++要笑着学】迭代器适配器 | 内嵌类型实现反向迭代器 | 迭代器萃取
时间：2023-04-26 15:37:01
表情包趣味教程??《C 要笑着学》
?? 写在前面
上一章讲解 list 模拟实现时，我们简单的提到了反向迭代器，我们说反向迭代器其实就是对正向迭代器的一种封装 —— 适配器模式(配接器模式)。当时我们做的是简单的理解，本章我们将讨论这部分知识。
本博客全站热榜排名：16
0x00 适配器是什么？
上一章讲解 list 在实现迭代器时，我们提到了反向迭代器的实现。
?? 代码：reverse_iterator (我们自己实现的)
namespace chaos { /* 定义反向迭代器 */ template class reverse_iterator { typedef reverse_iterator self; public: reverse_iterator(Iterator it) :_it(it) {} Ref operator*() { //return *_it; Iterator prev = _it; return *--prev; } Ptr operator->() { return &operator*(); } self& operator () { --_it; return *this; } self& operator--() { _it; return *this; } bool operator!= (const self& rit) const { return _it != (const self& rit) const { return _it != rit._it; } private: Iterator _it; }; } ? 思考：先说一个问题，迭代器适配器是什么？
想了解这里的 "适配器"，最好先看看电源适配器，看完再去理解。
(电源适配器)
【百度百科】电源适配器，又称外部电源，是小型便携式电子设备和电子电器的供电电压变换设备，常见于手机、液晶显示器、笔记本电脑等小型电子产品。
进行电源适配器 "转换" 是的，本质上可以理解为变压器。
标准家用电压为，我们的设备用电不需要那么高，
电源适配器可以将较高的交流电压降低到适合手机电池的直流工作电压。
换句话说，电源适配器是用来的 "转换" 的。
??
正如我们在上一章中提到的，反向迭代器与正向迭代器非常相似！
?? 区别：反向迭代器的方向与正向迭代器不同(唯一的区别)。
(即正向迭代器 是向后，反向迭代器 是向前走）
由于这一系列原因，在实现反向迭代器时，不需要像正向迭代器那样包装和重新实现。
?? 举个例子：
我们可以封装它 "转换" ，例如，我们需要它 list 反向迭代器，
我们将 list 正向迭代器传输 Iterator，来实例化 Iterator。
然后通过包装转换出你需要的 list 反向迭代器：
namespace chaos { /* 反向迭代器 */ template class reverse_iterator { typedef reverse_iterator self; public: reverse_iterator(Iterator it) : _it(it) {} 如果你 vector 如果需要反向迭代器，请使用它 vector 正向迭代器传输 Iterator，
它可以通过正向迭代器转换 vector 反向迭代器。
也就是说，我们实现的反向迭代器和包装不是针对某个容器，而是针对所有容器。
只要你实现了正向迭代器，任何容器都可以适应反向迭代器。
它的本质是一种复用，一种适应和转换。这是迭代适配器！
0x01 反向迭代器的错位访问
我们上一章提到过 operator* 回到这里的是*--prev，是有意的 "错位" 。
它引用的不是当前的位置，而是前一个位置。
对于 list 正向迭代器 begin 和 end 位置如下：
我们的反向迭代器 rbegin 和 rend 在哪里？按照我们的常识，应该是这样的:
rbegin 和 rend 是和 end 和 begin 以相对称的形式设计，
你的 end 就是我的 rbegin，你的 begin 就是我的 rend。
这时，就出现了一个错位问题，我们解引用的时候就不对了，举个例子:
rit 在 rbegin() 的位置，rbegin 在头结点，解引引用位置吗？
不，我们是反向迭代器，我们要拿的是最后一个位置！为什么要取头结点？……
?? 解决方案：为了解决这个问题，我们在 operator* 上动手脚，让其返回 *--prev：
这样取的就是前一个位置了，rbegin() 位置的前一个位置正是我们想要取的地方！
0x02 利用内嵌类型实现反向迭代器
实际上，STL3.0 的反向迭代器只有一个模板参数：
而我们上一章模拟实现 list 的反向迭代器时，设计了 3 个模板参数
这是因为在上一章为了更方便地区讲解 list 的模拟实现，我们将其简化了。
库里面的实在是让人头皮发麻，我们现在来学习下库里面是如何实现的：
它没有传 Ref 和 Ptr，也就意味着不能显式地去传，自己去控制（详细请阅读上一章内容）。
比如，如果你是普通迭代器的反向迭代器，传的就是 T& 和 T* ：
如果你是 const 迭代器的反向迭代器，传的就是 const T& 和 const T* ：
我们这么做是为了更清楚地表示，降低学习的成本。
而库中采用了一种更难的方式去实现，不传 Ref 和 Ptr 这两个模板参数，只用了一个模板参数。
这就意味着要去取 pointer 和 reference，因为它们要做 operator* 和 operator-> 的返回值。
❓ 而这里只有迭代器 Iterator，我们该怎么去取呢？
💡 大哥是这么做的，他在其中定义了一个内嵌类型：
把 Ptr 和 Ref 定义成了 pointer 和 reference，这样我们就可以从内嵌类型中去取这个类型了。
💬 代码：不传 Ptr 和 Ref 这两个模板参数去实现反向迭代器
namespace chaos
{
//template
template
class reverse_iterator {
typedef reverse_iterator self;
typedef Iterator::Ref reference; // 取内嵌类型
typedef Iterator::Ptr pointer;
public:
reverse_iterator(Iterator it)
:_it(it)
{}
...
}
} 如果你自己试一试你就会发现一个问题：
Iterator 是一个模板参数，你要取模板参数中的内嵌类型 Ref，编译器这里就编不过去了。
如果你对模板参数取 typedef，没有任何问题。但是你要取它的内嵌类型，就有问题了：
因为编译器编译到这一块的时候，模板参数还没有实例化！
既然没有实例化，那编译器也不知道这个 Iterator 的类型是什么，typedef 一下没什么问题。
但是你去 : : 取 Iterator 里面的东西，模板都还没实例化，编译器怎么知道里面到底是什么呢？
那我们该怎么让编译器知道呢？
凡是要取一个模板、类模板或模板参数的内嵌类型（内部类），就可以用 typename：
对于现阶段而言，这种写法是有缺陷的。vector、string 的迭代器怎么适配？
这里在取内嵌类型，只有自定义类型才能在里面搞内嵌类型。如果是一个原生指针呢？
原生指针哪来的内嵌类型？这里不就抓瞎了么。
如果仅看这一部分的实现，自然还是三个模板参数更爽，自己控制。
但是 STL 是非常复杂的，它还要考虑去兼顾全局，不是说只有迭代器和容器，
像 vector、string 这样的容器的迭代器是原生指针，无法取内嵌类型。那么上面的方式就寄了。
0x03 浅谈迭代器萃取
基于这一系列的原因，STL 源码中使用了一个叫 "迭代器萃取" 的技术解决的。
📚 原理：再套一层，去萃取迭代器中的 reference 和 pointer（迭代器管理的数据中的 T& 和 T* 或 const T* 和 constT& 等取出来）。相当于把其他容器的迭代器传给 iterator_traits，在其中再套一层，对于链表而言最终还是要取：
对于 vector、string 这样的原生指针，iterator_traits 里有使用了一个技术 —— "模板特化技术"
大概意思是当你这里是原生指针时，这里会直接自己套一层取解决。萃取的本质就是特化。
（这里先了解一下，关于这里的深入实现我们后面模板的进阶章节会详细讲解）
（迭代器萃取的知识难度较大，我们后期再专门开一个章节去讲）
🔺 总结：list 用一个参数实现还行，但是 vector 和 string 这样的原生指针还是用一个参数去实现会牵扯到更复杂的迭代器萃取。就目前而言，学会实现 3 个模板参数的反向迭代器即可。
📌 [ 笔者 ] 王亦优
📃 [ 更新 ] 2022.6.15
❌ [ 勘误 ] /* 暂无 */
📜 [ 声明 ] 由于作者水平有限，本文有错误和不准确之处在所难免，
本人也很想知道这些错误，恳望读者批评指正！| 📜 参考资料 C++reference[EB/OL]. []. http://www.cplusplus.com/reference/. Microsoft. MSDN(Microsoft Developer Network)[EB/OL]. []. . 百度百科[EB/OL]. []. https://baike.baidu.com/. 比特科技. C++[EB/OL]. 2021[2021.8.31]. |
