STL源码剖析--读书笔记（2）

谁践踏了优雅 2021-11-10 14:18 259阅读 0赞

# 写在前面的话 #

上一篇博文写了STL的**分配器**，这一篇着重介绍一下**迭代器**。

# 迭代器介绍 #

我们都知道，STL中将容器和算法分离开来，彼此独立设计，以达到泛化的效果，而在使用的时候又需要将这两种东西撮合到一起，实现这个撮合功能的就是迭代器。也就是说迭代器是介于容器与算法之间的一种东西，它可以把实现某个算法所需要的容器里面的信息传递给算法，从而达到一种“桥梁”的效果。  
迭代器可以看作是一种“智能指针”。它是一种行为类似指针的对象，而指针的各种行为中最常见的也是最重要的便是内容提取和成员访问，因此，迭代器最重要的编程工作就是对 operator✳ 和 operator->进行重载。关于这一点，其实跟真证的智能指针（share\_ptr等）没有区别。既然迭代器实现的功能和指针一样，那为什么不直接用指针来代替迭代器呢？何必还要多此一举。这是因为，指针只能在连续空间上前进和后退，而不能随意的跳转，例如在双向链表的每一个节点中，都有两个指针，分别指向前一个元素和后一个元素，除此之外每个节点中还有另外的空间来存储数据，当指针+1的时候，它只能在该节点的连续空间上移动，而当设计好相应功能的迭代器+1的时候，可以直接跳到下一个节点，也就是说，迭代器可以实现跨区域跳转，这就是它与指针之间最大的不同。

# 迭代器的相应型别 #

我们发现，在算法中运用迭代器时，会用到迭代器的相应型别，什么是相应型别？迭代器所指之物的型别就是其中的一种。常用迭代器的相应型别有五种，分别是：value type; difference type; reference type; pointer type; iterator\_category.接下来分别介绍这五种相应型别。

## value type ##

所谓 value type，就是指迭代器所指对象的型别，任何一个打算与 STL 算法有完美搭配的类，都应该定义自己的 value type 内嵌型别。

## difference type ##

difference type 用来表示两个迭代器之间的距离，因此它也可以用来表示一个容器的最大容量，因为对于连续空间的容器而言，头尾之间的距离就是其最大容量，如果一个泛型算法提供计数功能，例如 STL 的 count(), 其传回值就必须使用迭代器的 difference type。

## reference type ##

在 C++ 中，函数要传回左值，都是以传引用的方式进行，所以当 p 是个可修改值的迭代器时，如果其 value type 是 T,那么 ✳p 的型别不应该是 T，应该是 T&.同理，如果 p 是一个不可修改值的迭代器，其 value type 是 T，那么 ✳p 的型别不应该是 const T,而应该是 const T&。这里讨论的 ✳p 的型别，即所谓的 reference type。

## pointer type ##

指针和引用有着非常密切的关系。如果传回一个左值，令它代表 p 所指之物是可能的，那么传回一个左值，令它代表 p 所指之物的地址也一定可以。也就是说，我们能够传回一个指针，指向迭代器所指之物。

## iterator\_category ##

这个型别表明了迭代器的类别。根据移动特性和施行操作，迭代器被分为五类：input iterator（只读，即这种迭代器所指的对象不允许外界改变）；output iterator（只写，即该迭代器所指的对象只能被外界改变，不能读取）；forward iterator（单向读写）；bidirectional iterator（双向读写）；random access iterator（随机读写）。  
　　以上五种迭代器的类别，前三种支持 operator++，第四种再加上 operator–，第五种则涵盖所有指针算术能力，包括 p+n, p-n, p\[n\], p1-p2, p1<p2。在设计算法时，应该尽量对迭代器的类型做一个明确的规定，这样才能在不同情况下提供最大的效率。假设有个算法可接受 forward iterator ,你给它传一个 random access iteator 进去，它当然也会接受，因为一个 random access iteator 必然是一个 forward iteator,但是从效率上来讲，这并不是最佳的方案。

## Traits编程技法 ##

traits用来提取对象的型别，对应的模板参数不管是泛化版本还是特化版本，通通都能准确的萃取出来。如果传进来的参数 I 定义有自己的 value type，那么通过 traits,萃取出来的 value type 就是 I::value type。如果是特化版本，例如 T✳，则萃取出来的 value type 就是 T。特别注意，const T✳，萃取出来后也是 T 而非 const T,这是因为我们的本意就是声明一个临时变量，使之与迭代器的 value type 相同，而如果声明一个无法赋值的变量，没有什么作用，因此，对于 const 类型的变量，萃取出来的 value type就会变成 non-const类型。