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 + n， p - n，p[n]，p1 - p2，p1 < 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_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 型别同样采用内存直接处理操作，获取最大效率

Comments