#|STL迭代器详解 c++|迭代器|stl|traits|iterator|STL学

文章目录

- 1. 迭代器(iterator)是一种智能指针(smart pointer)
- 2. 迭代器相应类型(associate types) 及类型的取用
- - 2.1 迭代器相应类型概念、应用场景 & 偏特化概念
  - 2.2 迭代器相关类型的取用——iterator_traits机制
- 3. std::iterator的保证
- 4. 总结

不同于OOP(Object Oriented Programming)将数据(datas)和行为(methods)组织在一起的思想，STL的中心思想GP(Generic Programming)在于：将数据容器(containers)和算法(algorithms)分开，彼此独立设计，最后再以胶着剂将它们撮合在一起。那么之间的胶着剂就是迭代器(iterator)。

文章图片
GP的思路具体为：containers和algorithms团队可以各自闭门造车，其间以iterator进行沟通。algorithms通过iterators确定操作范围，并通过iterators提领取用containers中的数据。那么如何设计好迭代器是一个难题。
1. 迭代器(iterator)是一种智能指针(smart pointer) 智能指针：在c++中，动态内存的管理是通过new和delete来完成的，实际上new和delete运算符最终调用的是malloc()和free()两个函数。对于动态内存的管理很容易出问题，想要确保在正确时间释放内存考验功力。若是忘记释放会导致内存泄漏，若是提早释放，即尚有指针引用的情况下就释放内存，会产生引用非法内存的指针。针对这一问题，应运而生出了智能指针的概念，即其行为类似常规指针，但是它能够负责自动释放所指向的对象，形式通常为一个struct或class的自定义数据类型所实例化出的对象。新标准库提供了三种智能指针，分别是shared_ptr(允许多个指针指向同一对象)和unique_ptr(独占所指向的对象)，还有weak_ptr(伴随类，弱引用，指向shared_ptr所管理的对象)。
迭代器是一种行为类似指针的对象(智能指针对象)，其行为包括内容提领(deference)和成员访问(member access)，所以迭代器要对operator&()和operator*()进行重载，同时要兼顾自身的有效性(析构)的问题。
以上概念明确之后，可以尝试为单向链表设计一迭代器。

//定义single linked list的基本数据结构 template class List { public: void insert_front(T value); void insert_end(T value); void display(std::ostream &os = std::out) const; //... private: ListItem* _end(); ListItem* _front(); long _size; }; template class ListItem { public: T value() const { return _value; } ListItem* next const { return _next; } //... private: T _value; ListItem* _next; }; //------------------------------------------------------------------------------------ //List的iterator实现 //主要功能为： //1.deference迭代器时返回ListItem对象；2.递增迭代器时，返回_next节点 //为使迭代器适应多种内嵌数据类型的List，将其设计为class template template //Item可以是单向链表节点或是双向链表节点 struct ListIter { //此处的迭代器只为链表服务，因为其operator++的功能 Item* ptr; //保持与容器的一个联系(keep a reference to Container) ListIter(Item* p = 0) : ptr(p) {} //default ctor //不必实现copy ctor，因为编译器提供的缺省行为已足够 //不必实现operator=，因为编译器提供的缺省行为已足够 Item& operator*() const { return *ptr; } Item* operator->() const { return ptr; } //以下两个operator++遵循标准做法 //（1）pre-increment operator ListIter& operator++() { ptr = ptr->next(); return *this; } //(2)post-increment operator ListIter operator++(int) { ItemIter tmp = *this; ++*this; return tmp; } bool operator==(const ListIter& i) { return ptr == i.ptr; } bool operator!=(const ListIter& i) { return ptr != i.ptr; } //... };

从以上实现中，可以看到为完成ListIter的设计，其中暴露了许多List的实现细节，包括数据成员ListItem及其成员函数。对于调用者而言，这些都应该是屏蔽掉的。但是要设计出ListIter，就难免暴露出这些实现细节，也就是说要对List有丰富的了解。因此，惯常做法是由容器的设计者开发该容器的迭代器。如此，所有实现细节对使用者屏蔽，这也是为什么每种STL容器都有专属迭代器的原因。
2. 迭代器相应类型(associate types) 及类型的取用 2.1 迭代器相应类型概念、应用场景 & 偏特化概念
在实际的算法中，在运用迭代器时，会用到迭代器所指对象中的相应类型(associate type)。
那么算法实现中该如何满足声明一个以“迭代器所指对象(中)的类型”为类型的成员/参数，或返回值是“迭代器所指对象(中)的类型”的类型的需求呢？
可分为以下三种情况：

① 迭代器所指对象是c++内置类型；
② 迭代器所指对象是自定义类型(class type)情形;
③ 迭代器所指对象是原生指针(naive pointer)情形;

对应的运用以下三种方法解决：

① function template的参数推导(augument deducation)机制；
② 声明内嵌类型；
③ 利用泛化中偏特化(partial secification)(下面有解释) ；
envolve to ：萃取机 iterator_traits 机制

注意：这三种方法是逐步整合为最终的实现的方案就是 iterator_traits萃取机 机制，它包含了函数模板的参数推导，声明内嵌类型和偏特化所有内容，也同时解决了以上的三个场景的实现需求。

文章图片
①声明一个迭代器所指对象的类型为c++内置类型的成员/参数，使用模板函数的推导机制进行，在函数实现过程中加入对底层模板函数的封装；

文章图片
②返回值是迭代器所指自定义类型（class type）中的内嵌类型,使用关键字typename来声明算法中出现的成员或返回值是迭代器所指对象的内嵌类型。
其中typename用法见typename关键字

需要注意的是，并不是所有的迭代器都是class type的。比如说原生指针(naive pointer)，就无法将其定义为内嵌类型。所以还要对上述的一般化概念中的特殊情况做特殊化处理。
③偏特化(template partial specification)：如果class template拥有一个以上的template参数，可以对其中某个(或数个，但非全部)template进行特化工作，其中偏特化有两种形式：

1. 对template参数的部分个参数进行特化；
2. 对template参数的范围进行限定；

两种形式见下图所示：

文章图片
偏特化其实就可以理解为“针对任何template参数进一步地进行条件限制所设计出的特化版本”。那么对应的，全特化(full specification) 就是指对模板参数不做任何限制。
如上，利用对(常量)指针类型的偏特化，解决了内嵌类型无法解决的迭代器所指对象是原生指针类型的问题。
2.2 迭代器相关类型的取用——iterator_traits机制
在《Effective C++》条款47：请使用traits classes表现类型信息中对萃取机制也有详细解答，先抛开这些，从头开始讲起。
结合以上三种情况和三种解决方法，最终设计出了迭代器萃取机这一中间层，其作用是萃取出迭代器的相关特性（也即是相应类型的取用），以屏蔽迭代器实现对算法实现的影响。如左下图所示：

文章图片
iterator_traits示意图，可将算法向迭代器询问的关于容器特性给"萃取"出来

文章图片
迭代器常用的5种类型在特征萃取机中都有内嵌类型定义

在图中列出了原生指针(pointer)，还单独列出了常量指针(pointer-to-const)（对于const关键字的解析见：const限定符）。对于常量指针，泛化版本的iterator::traits value_type会返回一个const int，也即返回值是一个无法进行赋值的临时变量，所以针对常量指针的value_type类型应当特化为非常量类型，如下：

template struct iterator_traits { //偏特化版本——当迭代器是一个pointer-to-const时 typedef T value_type; //萃取出的类型应当是T而非常量const T //... }; //附上指针的偏特化萃取实现 struct iterator_traits { typedef T value_type; //... };

所以只要迭代器的实现者在实现过程中，将内嵌类型和原生类型遵循约定，以内嵌类型（nested typedef)的方式定义(typedef)出STL迭代器萃取机所规定的相关类型，就可以与STL标准实现兼容，实现算法实现和容器实现的剥离。
如右上图(iterator_traits对常用内嵌类型的typedef)所示，迭代器中最常用到的迭代器类型有五种，整理出如下表格：

迭代器相关类型	说明
value_type	所谓value type，指的是迭代器所指对象的类型。任何一个与STL有完美搭配的class，都应该定义value type内嵌类型
difference_type	difference type表示两个迭代器之间的距离，因此也可用来表示一个容器的最大容量（头尾距离），以alogrithm中的`count()`为例：文章图片对于原生指针，c++内建了ptrdiff_t（位于头文件内）作为原生指针的difference type（在`iterator_traits<(const) T>`中使用）；当需要迭代器I的difference type，可以写`typename iterator_traits::difference_type`，如上图中例；*
reference	首先根据迭代器能否更改所指的对象，可以分为`constant iterators`和`mutable iterators`两种；对应两种迭代器：如果iterator是const的，那么若是其value_type是T，那么返回值应当是`const T&`; 如果iterator是mutable的，那么若是其value_type是T，那么返回值应当为`T&`；
pointer	指向迭代器所指之物/对象的类型的指针的类型;
iterator_category	对于迭代器种类，若是良好的利用好category的继承关系，可以极大地提高算法的效率，种类的具体解释和继承关系如下面图中所示。以`advance()`函数为例可以探讨category对算法的影响，详细内容见《STL源码剖析》p93，运用到了类的多态性，向上类型转换(派生类转基类，is-a继承关系)。

文章图片
迭代器的5种分类

文章图片
迭代器的分类和从属关系

3. std::iterator的保证为符合规范，任何迭代器都应提供五个内嵌相应类别，以利于traits萃取。STL为此提供了一个iterators class，也即std::iterator如下，如果每个新设计的迭代器继承自它，就可保证STL所需之规范：

文章图片
之前的ListIter可以改写为：

template struct ListIter : public std::iterator::forward_iterator_tag, Item> { //... };

4. 总结

设计适当的迭代器相应内嵌类型，是迭代器的责任；同时设计适当的迭代器，是容器设计者的责任。
唯有容器本身，才知道应当设计怎样的迭代器来遍历自己，还有如何运用相关的运算符；
【#|STL迭代器详解】有了traits技巧(其利用内嵌类型的编程技巧和template的参数推导功能)，增强了c++未能提供的关于类型辨别方面的能力（c++是弱类型语言，能够进行隐式类型转换），完成了算法和容器间的解耦；其实个人感觉，traits技巧很像平台中间件的概念；