STL 剖析:迭代器(iterators)

 
 
C++
 5.6k
 

在实现 TinySTL 过程中对思路的一些梳理,并不涉及代码(大概),如有兴趣可以跳至相关实现。本篇主要讲述 STL 中的迭代器,迭代器是一种抽象概念,在《Design Patterns》(23 种设计模式的出处)一书中有关于 iterator 模式的完整描述,想要了解文字定义的就自己去搜吧😏

2024-08-08 21:28:54

目录:

1 迭代器设计思维——STL 的关键所在

2 Traits 编程技巧——STL 源代码门钥

2.1 迭代器相应型别之一:value type

2.2 迭代器相应型别之二:difference type

2.3 迭代器相应型别之三:reference type

2.4 迭代器相应型别之四:pointer type

2.5 迭代器相应性别之五:iterator_category

3 SGI STL 的私房菜:__type_traits


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 + np - np[n]p1 - p2p1 < p2

迭代器的分类和从属关系如下图,其中直线与箭头代表的并非 C++ 的继承关系,而是所谓 concept(概念)与 refinement(强化)的关系

172291598388617229144529421722914452785.png

概念 是一种用于指定模板参数要求的抽象。它们允许我们定义模板参数的约束条件,从而使得模板更加健壮和易于理解。概念可以看作是模板参数必须满足的一组条件或属性

强化 是指一个概念对另一个概念进行扩展或增强,从而定义一个更具体的概念。强化的概念必须满足被强化的概念的所有要求,并可能添加更多的约束

任何一个迭代器,其类型永远应该落在 “该迭代器所隶属之各种类型中,最强化的那个”,例如int*既是 Random Access Iterator,又是 BIdirectional Iterator,同时也是 Forward Iterator,而且也是 Input Iterator,那么其类型应该归属为 Random Access Iterator

STL 算法有一个命名规则:以算法所能接受的最低阶迭代器类型来为其迭代器型别参数命名

为了符合规范,任何迭代器都应该提供五个内嵌相应型别,以利于 traits 萃取,否则便是自别于整个 STL 架构,可能无法与其它 STL 组件顺利搭配。写代码难免会有粗心大意的时候,导致缺少一些规范中的型别定义。如何解决呢?STL 提供了一个 iterator class 如下(采用更加现代的 C++ 语法进行了仿写),如果每个新设计的迭代器都继承自它,就可保证符合 STL 所需之规范

1
2
3
4
5
6
7
8
template<typename Category, typename T, typename Distance = ptrdiff_t, typename Pointer = T *, typename Reference = T &>
struct iterator {
using iterator_category = Category;
using value_type = T;
using difference_type = Distance;
using pointer = Pointer;
using reference = Reference;
};

回到本节开头,假设算法中有必要声明一个变量,以 value type 为型别,如何是好?要知道的是 C++ 只支持sizeof(),并未支持typeof()。即使动用 RTTI 性质中的typeid(),获得的也只是型别名称,不能拿来做变量声明之用

RTTI(Run-Time Type Information,运行时类型信息),一种在程序运行时提供有关对象类型信息的机制

解决办法是:利用 function template 的参数推导(argument deducation)机制,例如:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template<typename I, typename T>
void func_impl(I iter, T t) {
T imp; // 于此解决问题, T 即为 value type,本例中为 int
... // 这里做原本 func() 应该做的所有工作
}

template<typename I>
void func(I iter) {
func_impl(iter, *iter); // 将 func() 的工作全部转移至 func_impl() 中
}

int main() {
int i;
func(&i);
}

但并非所有的迭代器型别都适用 template 的参数推导机制,因为其也只是针对参数进行推导,无法推导函数的返回型别等。我们需要其它方法,内嵌型别似乎是个好主意,像这样:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
template<typename T>
struct MyIter {
using value_type = T; // 内嵌型别声明(nested type)
T *ptr;
MyIter(T *p = nullptr) : ptr(p) {}
T &operator*() const {
return *ptr;
}
};

template<typename I>
typename I::value_type // func 的返回值型别,typename 的用意在于告诉编译器这是一个型别,而不是 data member 或者 member function,如此才能顺利通过编译
func_nested(I ite) {
return *ite;
}

int main() {
MyIter<int> ite(new int(8));
std::cout << func_nested(ite);
}

看起来不错,但是这里有一个隐晦的陷阱:并不是所有迭代器都是 class type。原生指针就不是!如果不是 class type,就无法为它定义内嵌型别。但 STL(以及整个泛型思维)必须接受原生指针作为一种迭代器,所以有没有办法让上述的一般化概念针对特定情况(例如针对原生指针)做特殊化处理呢?

原生指针是一种基础类型,它的设计目的是简单而高效地指向内存地址。它们不具备 class type 的复杂特性和封装能力,因此不能包含内嵌类型。内嵌类型需要一种复杂的结构来管理,而原生指针并不适合这种用途

这描述看着有点眼熟对吧,是的,template partial specialization 可以做到,假设有一个 class template 如下:

1
2
template<typename U, typename V, typename T>
class C {...};

partial specialization 的字面意思容易误导我们认为所谓的 “偏特化” 一定是对 template 参数 U 或 V 或 T(或某种组合)指定某个参数值,其实不然,个人认为《泛型思维》一书中对 partial specialization 的定义十分恰当:“针对(任何)template 参数更进一步的条件限制所设计出来的一个特化版本”。由此:

1
2
3
4
5
6
7
/* 面对下面这么个 class template */
template<typename T>
class C {...}; // 这个泛化版本接受 T 为任何型别

/* 我们很容易接受它有一个形式如下的 partial specialization */
template<typename T>
class C <T*>{...}; // 这个特化版本仅接受" T 为原生指针"的情况," T 为原生指针"便是" T 为任何型别"的一个更进一步的条件限制

有了这项利器,我们便可以解决上文所述的问题,原生指针并非 class type,因此不能为它们内嵌型别。而现在,我们可以针对 “迭代器的 template 参数为指针” 设计特化版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/* iterator 模板 */
template<typename Category, typename T, typename Distance = ptrdiff_t, typename Pointer = T *, typename Reference = T &>
struct iterator {
using value_type = T;
...
};

/* 下面这个 class template 专门用来萃取迭代器的型别,这么设计好处是让 traits 可以拥有特化版本 */
template<typename Iterator>
struct iterator_traits {
using value_type = typename Iterator::value_type; // 通过这个 traits 萃取出来的 value_type 就是 Iterator 定义的 value_type
};

/* 针对 native pointer 设计的 traits template partial specialization */
template<typename T>
struct iterator_traits<T *> {
using value_type = T;
};

总结

设计适当的相应型别(associated type),是迭代器的责任。设计适当的迭代器,则是容器的责任。唯有容器本身才找到设计出怎样的迭代器遍历自己,并执行迭代器该有的各种行为(前进,后退,取值,取用成员···)。至于算法完全可以独立于容器和迭代器之外自行发展,只要设计时以迭代器为为对外接口就行

3 SGI STL 的私房菜:__type_traits

SGI 将 traits 技法进一步扩展到迭代器以外的世界,于是有了所谓的__type_traitsiterator_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 型别同样采用内存直接处理操作,获取最大效率

Comments