在实现 TinySTL 过程中对思路的一些梳理,并不涉及代码(大概),如有兴趣可以跳至相关实现。本篇主要讲述 STL 中的迭代器,迭代器是一种抽象概念,在《Design Patterns》(23 种设计模式的出处)一书中有关于 iterator 模式的完整描述,想要了解文字定义的就自己去搜吧😏
2024-08-08 21:28:54
目录:
2.2 迭代器相应型别之二:difference type
2.3 迭代器相应型别之三:reference type
2.5 迭代器相应性别之五:iterator_category
1 迭代器设计思维——STL 的关键所在
STL 的中心思想在于:将容器(containers)和算法(algorithms)分开,彼此独立设计,最后再以一剂粘合剂将它们粘在一起。
迭代器(iterators)的作用就是充当两者之间的粘合剂,在《STL 源码剖析》中侯捷先生提到:迭代器是一种 smart poiner,也就是auto_ptr
。这里将迭代器类比为智能指针只是为了理解它们的指针行为,它们都是一种行为类似指针的对象,可以被赋值、比较和传递。需要明确的是,迭代器并不管理对象的生命周期(内存管理)。指针的各种行为中最重要也是最常见的是内容解引用和成员访问,因此,迭代器最重要的编程工作就是对operator*
和operator->
进行重载工作
auto_ptr
在 C++ 11中被弃用,在 C++ 17 中被移除。这是因为其存在一些严重的缺陷,它通过拷贝构造和拷贝赋值(复制)来转移所有权,也就是隐式转移所有权,这将会导无法轻松追踪对象的所有权变化,容易导致所有权不清晰的问题,以至于未定义行为。也因此通过移动构造和移动赋值(std::move
)显示转移所有权的unique_ptr
取代了auto_ptr
2 Traits 编程技巧——STL 源代码门钥
在算法中运用迭代器时,很可能会用到其相应型别,什么是相应型别?
2.1 迭代器相应型别之一:value type
所谓 value type,是指迭代器所指对象的型别
2.2 迭代器相应型别之二:difference type
difference type 用来表示两个迭代器之间的距离,因此它也可以用来表示一个容器的最大容量,因为对于连续空间的容器而言,头尾之间的距离就是其最大容量。如果一个泛型算法提供计数功能,例如 STL count()
,其传回值就必须使用迭代器的 difference type
2.3 迭代器相应型别之三:reference type
2.4 迭代器相应型别之四:pointer type
2.5 迭代器相应性别之五:iterator_category
根据移动特性与施行操作,迭代器被分为五类:
- Input Iterator:这种迭代器的对象,不允许外界改变。只读
- Output Iterator:只写
- Forward Iterator:允许“写入型”算法(例如
replace()
)在此种迭代器所形成的区间上进行读写操作 - Bidirectional Iterator:可双向移动
- Random Access Iterator:前四种迭代器都只提供一部分指针算术能力(前三种支持
operator++
,第四种再加上operator--
),第五种则涵盖所有指针算术能力,包括p + n
,p - n
,p[n]
,p1 - p2
,p1 < p2
迭代器的分类和从属关系如下图,其中直线与箭头代表的并非 C++ 的继承关系,而是所谓 concept(概念)与 refinement(强化)的关系
概念 是一种用于指定模板参数要求的抽象。它们允许我们定义模板参数的约束条件,从而使得模板更加健壮和易于理解。概念可以看作是模板参数必须满足的一组条件或属性
强化 是指一个概念对另一个概念进行扩展或增强,从而定义一个更具体的概念。强化的概念必须满足被强化的概念的所有要求,并可能添加更多的约束
任何一个迭代器,其类型永远应该落在 “该迭代器所隶属之各种类型中,最强化的那个”,例如int*
既是 Random Access Iterator,又是 BIdirectional Iterator,同时也是 Forward Iterator,而且也是 Input Iterator,那么其类型应该归属为 Random Access Iterator
STL 算法有一个命名规则:以算法所能接受的最低阶迭代器类型来为其迭代器型别参数命名
为了符合规范,任何迭代器都应该提供五个内嵌相应型别,以利于 traits 萃取,否则便是自别于整个 STL 架构,可能无法与其它 STL 组件顺利搭配。写代码难免会有粗心大意的时候,导致缺少一些规范中的型别定义。如何解决呢?STL 提供了一个 iterator class 如下(采用更加现代的 C++ 语法进行了仿写),如果每个新设计的迭代器都继承自它,就可保证符合 STL 所需之规范
1 | template<typename Category, typename T, typename Distance = ptrdiff_t, typename Pointer = T *, typename Reference = T &> |
回到本节开头,假设算法中有必要声明一个变量,以 value type 为型别,如何是好?要知道的是 C++ 只支持sizeof()
,并未支持typeof()
。即使动用 RTTI 性质中的typeid()
,获得的也只是型别名称,不能拿来做变量声明之用
RTTI(Run-Time Type Information,运行时类型信息),一种在程序运行时提供有关对象类型信息的机制
解决办法是:利用 function template 的参数推导(argument deducation)机制,例如:
1 | template<typename I, typename T> |
但并非所有的迭代器型别都适用 template 的参数推导机制,因为其也只是针对参数进行推导,无法推导函数的返回型别等。我们需要其它方法,内嵌型别似乎是个好主意,像这样:
1 | template<typename T> |
看起来不错,但是这里有一个隐晦的陷阱:并不是所有迭代器都是 class type。原生指针就不是!如果不是 class type,就无法为它定义内嵌型别。但 STL(以及整个泛型思维)必须接受原生指针作为一种迭代器,所以有没有办法让上述的一般化概念针对特定情况(例如针对原生指针)做特殊化处理呢?
原生指针是一种基础类型,它的设计目的是简单而高效地指向内存地址。它们不具备 class type 的复杂特性和封装能力,因此不能包含内嵌类型。内嵌类型需要一种复杂的结构来管理,而原生指针并不适合这种用途
这描述看着有点眼熟对吧,是的,template partial specialization 可以做到,假设有一个 class template 如下:
1 | template<typename U, typename V, typename T> |
partial specialization 的字面意思容易误导我们认为所谓的 “偏特化” 一定是对 template 参数 U 或 V 或 T(或某种组合)指定某个参数值,其实不然,个人认为《泛型思维》一书中对 partial specialization 的定义十分恰当:“针对(任何)template 参数更进一步的条件限制所设计出来的一个特化版本”。由此:
1 | /* 面对下面这么个 class template */ |
有了这项利器,我们便可以解决上文所述的问题,原生指针并非 class type,因此不能为它们内嵌型别。而现在,我们可以针对 “迭代器的 template 参数为指针” 设计特化版
1 | /* iterator 模板 */ |
总结
设计适当的相应型别(associated type),是迭代器的责任。设计适当的迭代器,则是容器的责任。唯有容器本身才找到设计出怎样的迭代器遍历自己,并执行迭代器该有的各种行为(前进,后退,取值,取用成员···)。至于算法完全可以独立于容器和迭代器之外自行发展,只要设计时以迭代器为为对外接口就行
3 SGI STL 的私房菜:__type_traits
SGI 将 traits 技法进一步扩展到迭代器以外的世界,于是有了所谓的__type_traits
。iterator_traits
负责萃取迭代器的特性,__type_traits
则负责萃取型别的特性。这里所关注的特性是指:这个型别是否具有 trivial default constructor,是否具备 trivial copy constructor,是否具备 trivial assignment operator,是否具备 trivial destructor?如果答案是肯定,那么我们就可以直接采用内存直接处理操作如malloc()
、memcpy()
等等,获得最高效率,而不是调用身居高位、不谋实事的那些constructor()
、destructor()
trivial 是指这些特殊成员函数由编译器自动生成,且只执行最简单的操作,不涉及复杂的初始化、拷贝、赋值或析构逻辑。它们主要保证对象的基础生命周期管理,但不进行任何资源管理或自定义行为
这里稍微讲述一下 POD 型别,因为__type_traits
的代码设计中涉及到了。POD 是指 Plain Old Data,也就是标量型别(scalar types)或传统的 C struct 型别。POD 型别必然拥有 trivial constructor/copy/assignment/destructor 函数,因此,对于 POD 型别同样采用内存直接处理操作,获取最大效率