文章目录
-
- 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 机制
文章图片 ①声明一个迭代器所指对象的类型为c++内置类型的成员/参数,使用模板函数的推导机制进行,在函数实现过程中加入对底层模板函数的封装; |
文章图片 ②返回值是迭代器所指自定义类型(class type)中的内嵌类型,使用关键字typename来声明算法中出现的成员或返回值是迭代器所指对象的内嵌类型。 其中typename用法见typename关键字 |
③偏特化(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种类型在特征萃取机中都有内嵌类型定义 |
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(位于 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种分类 |
文章图片 迭代器的分类和从属关系 |
std::iterator
如下,如果每个新设计的迭代器继承自它,就可保证STL所需之规范:文章图片
之前的ListIter可以改写为:
template
struct ListIter : public std::iterator::forward_iterator_tag, Item> {
//...
};
4. 总结
- 设计适当的迭代器相应内嵌类型,是迭代器的责任;同时设计适当的迭代器,是容器设计者的责任。
- 唯有容器本身,才知道应当设计怎样的迭代器来遍历自己,还有如何运用相关的运算符;
- 【#|STL迭代器详解】有了traits技巧(其利用内嵌类型的编程技巧和template的参数推导功能),增强了c++未能提供的关于类型辨别方面的能力(c++是弱类型语言,能够进行隐式类型转换),完成了算法和容器间的解耦;其实个人感觉,traits技巧很像平台中间件的概念;
推荐阅读
- 蓝桥杯|ACwing789. 数的范围 (二分法典型例题)
- 算法笔记|HDU - 2041 超级楼梯 (简单DP)
- 特殊算法技巧|康托展开简单记录
- 初阶数据结构与算法|【初阶数据结构与算法】第七篇(二叉树和堆的基本概念+以及堆的实现)
- 每日刷题———蓝桥杯真题|蓝桥杯2020第十一届C语言B组省赛习题题解——习题A.门牌制作
- 蓝桥杯|2018年第九届C/C++ A组蓝桥杯省赛真题部分题解(C语言/C++)
- #|2020年第11届蓝桥杯C++B组 第一次省赛真题
- #|<<算法很美>>——(七)——DFS典题(二):数独游戏
- 课程设计实验报告|本科课程【数据结构与算法】实验8 - 拓扑排序