#|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)。
#|STL迭代器详解
文章图片
GP的思路具体为:containers和algorithms团队可以各自闭门造车,其间以iterator进行沟通。algorithms通过iterators确定操作范围,并通过iterators提领取用containers中的数据。那么如何设计好迭代器是一个难题。
1. 迭代器(iterator)是一种智能指针(smart pointer) 智能指针:在c++中,动态内存的管理是通过newdelete来完成的,实际上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萃取机 机制,它包含了函数模板的参数推导,声明内嵌类型和偏特化所有内容,也同时解决了以上的三个场景的实现需求。
#|STL迭代器详解
文章图片
①声明一个迭代器所指对象的类型为c++内置类型的成员/参数,使用模板函数的推导机制进行,在函数实现过程中加入对底层模板函数的封装;
#|STL迭代器详解
文章图片
②返回值是迭代器所指自定义类型(class type)中的内嵌类型,使用关键字typename来声明算法中出现的成员或返回值是迭代器所指对象的内嵌类型。
其中typename用法见typename关键字
需要注意的是,并不是所有的迭代器都是class type的。比如说原生指针(naive pointer),就无法将其定义为内嵌类型。所以还要对上述的一般化概念中的特殊情况做特殊化处理。
偏特化(template partial specification):如果class template拥有一个以上的template参数,可以对其中某个(或数个,但非全部)template进行特化工作,其中偏特化有两种形式:
  • 1. 对template参数的部分个参数进行特化;
  • 2. 对template参数的范围进行限定;
两种形式见下图所示:
#|STL迭代器详解
文章图片
偏特化其实就可以理解为“针对任何template参数进一步地进行条件限制所设计出的特化版本”。那么对应的,全特化(full specification) 就是指对模板参数不做任何限制。
如上,利用对(常量)指针类型的偏特化,解决了内嵌类型无法解决的迭代器所指对象是原生指针类型的问题。
2.2 迭代器相关类型的取用——iterator_traits机制
在《Effective C++》条款47:请使用traits classes表现类型信息中对萃取机制也有详细解答,先抛开这些,从头开始讲起。
结合以上三种情况和三种解决方法,最终设计出了迭代器萃取机这一中间层,其作用是萃取出迭代器的相关特性(也即是相应类型的取用),以屏蔽迭代器实现对算法实现的影响。如左下图所示:
#|STL迭代器详解
文章图片
iterator_traits示意图,可将算法向迭代器询问的关于容器特性给"萃取"出来
#|STL迭代器详解
文章图片
迭代器常用的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()为例:
#|STL迭代器详解
文章图片

对于原生指针,c++内建了ptrdiff_t(位于头文件内)作为原生指针的difference type(在iterator_traits<(const) T*>中使用);
当需要迭代器I的difference type,可以写typename iterator_traits::difference_type,如上图中例;
reference 首先根据迭代器能否更改所指的对象,可以分为constant iteratorsmutable iterators两种;
对应两种迭代器:
如果iterator是const的,那么若是其value_type是T,那么返回值应当是const T&;
如果iterator是mutable的,那么若是其value_type是T,那么返回值应当为T&
pointer 指向迭代器所指之物/对象的类型的指针的类型;
iterator_category 对于迭代器种类,若是良好的利用好category的继承关系,可以极大地提高算法的效率,种类的具体解释和继承关系如下面图中所示。以advance()函数为例可以探讨category对算法的影响,详细内容见《STL源码剖析》p93,运用到了类的多态性,向上类型转换(派生类转基类,is-a继承关系)。
#|STL迭代器详解
文章图片
迭代器的5种分类
#|STL迭代器详解
文章图片
迭代器的分类和从属关系
3. std::iterator的保证 为符合规范,任何迭代器都应提供五个内嵌相应类别,以利于traits萃取。STL为此提供了一个iterators class,也即std::iterator如下,如果每个新设计的迭代器继承自它,就可保证STL所需之规范:
#|STL迭代器详解
文章图片
之前的ListIter可以改写为:
template struct ListIter : public std::iterator::forward_iterator_tag, Item> { //... };

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

    推荐阅读