当前位置:网站首页>【STL源码剖析】迭代器
【STL源码剖析】迭代器
2022-06-30 10:11:00 【Cloudeeeee】
【STL源码剖析】迭代器
- 第3章 迭代器(iterators)与traits编程技法(《STL源码剖析》 )
- 3.1 迭代器设计思维——STL关键所在
- 3.2 迭代器(iterator)是一种smart pointer
- 3.3 迭代器相应型别(associated types)
- 3.4 Traits编程技法——STL源码门钥
- 3.4.1 迭代器相应型别之一:value type
- 3.4.2 迭代器相应型别之二:difference type
- 3.4.3 迭代器相应型别之三:reference type
- 3.4.4 迭代器相应型别之四:pointer type
- 3.4.5 迭代器相应型别之五:iterator_category
- 3.4.5 迭代器相应型别之五:iterator_category
- 3.5 std::iterator 的保证
- 3.6 iterator源代码完整重列
- 3.7 SGI STL 的私房菜:__type_traits
第3章 迭代器(iterators)与traits编程技法(《STL源码剖析》 )
3.1 迭代器设计思维——STL关键所在
STL的中心思想在于:将数据容器和算法分开,彼此独立设计,最后在以一胶合剂将它们连接在一起。
3.2 迭代器(iterator)是一种smart pointer
dereference
译名较多,本书中为"内容提纲",也可译为反引用、解引用等等;具体指的是:
在 *p; 中,用 * 来取指针 p 的值这样一个动作
成员访问
指的是像 p->size() 这样用 -> 符号来访问成员变量、成员函数的动作。
auto_ptr是一种用来包装原生指针的对象,不需要自行释放内存,auto_ptr会自动释放内存,可以解决内存泄漏的问题
实现一个迭代器:
3.3 迭代器相应型别(associated types)
问题场景: 在算法中需要声明一个迭代器所指对象的类型(我们定义为value type)的变量,如何声明?
解决办法: 利用function template的参数推导(argument deducation)机制
3.4 Traits编程技法——STL源码门钥
在STL实现中,traits编程技术得到大量的运用,它利用了“内嵌类型”的编程技巧与C++的template参数推导功能,弥补了C++类型识别方面的不足。通过traits,算法可以原汁原味的将迭代器的属性萃取出来,帮助算法正确高效的运行。
问题场景: 当要以迭代器所指类型作为函数的返回类型时(如下),function template的参数推导(argument deducation)机制就无法完成任务了,那么要怎么办呢?
template<typename Iterator>
(*Iterator) func(Iterator iter)
{
//这样定义返回类型可以吗?
}
解决办法: 声明内嵌型别,在迭代器内部声明类型的型别,然后通过Iterator::value_type方法来调用这个类型:
template<typename T>
class Iterator
{
public:
typedef T value_type; //内嵌类型声明
};
template<typename Iterator>
// 通过Iterator::value_type方法来调用这个类型
typename Iterator::value_type func(Iterator iter)
{
return *iter;
}
问题场景: 不是所有迭代器都是类类型,如原生指针(如int*)就并非class,那样就无法使用内嵌型别说明了,那么要怎么办呢?
解决办法: 模板偏特化,即如果一个class template拥有多个template参数,我们可以针对其中的某个(或数个,但不能是全部)进行特化(即指定数据类型)。因此可以对迭代器的template参数为指针的情况,进行特化处理。
如下:
// 一个泛化版本
template<typename T>
Class C{
...};
// T为原生指针的特化版本
template<typename T>
Class C<T*>{
...};
traits(特性萃取机、特性提取机):
// 声明内嵌型别的方法
template<typename Iterator>
typename Iterator::value_type func(Iterator iter)
{
return *iter;
}
// 使用iterator_traits的方法
// 定义iterator_traits
template<typename Iterator>
struct iterator_traits
{
typedef typename Iterator::value_type value_type;
};
// 使用iterator_traits
template<typename Iterator>
typename iterator_traits<Iterator>::value_type func(Iterator iter)
{
return *iter;
}
此外要注意形参的const和非const版本是不一样的,因此要定义两个偏特化的版本来区分参数为const和非const的情况:
// 参数为非const
template<typename T>
struct iterator_traits<T*>
{
typedef T value_type;
}
// 参数为const的偏特化版本
template<typename T>
struct iterator_traits<const T*>
{
typedef T value_type;
}
STL中iterator_traits的完整定义:
tempalte<typename I>
struct iterator_traits
{
typedef typename I::iterator_category iterator_category;
typedef typename I::value_type value_type;
typedef typename I::difference_type difference_type;
typedef typename I::pointer pointer;
typedef typename I::reference reference;
};
接下来会对这五种特性一一进行介绍。
3.4.1 迭代器相应型别之一:value type
value type即迭代器所指对象的类型。
3.4.2 迭代器相应型别之二:difference type
两个迭代器之间的距离,因此它可以表示一个容器的最大容量;如果一个泛型算法提供计数功能,如count(),其返回值就必须使用迭代器的difference type;
定义difference_type:
// 泛化版本
template<class T>
struct iterator_traits{
...
typedef typename I::difference_type difference_type;
}
// 针对原生指针的偏特化版本(非const)
template<class T>
struct iterator_traits<T*>{
...
typedef ptrdiff_t difference_type;
}
// 针对原生指针的偏特化版本(const)
template<class T>
struct iterator_traits<const T*>{
...
typedef ptrdiff_t difference_type;
}
3.4.3 迭代器相应型别之三:reference type
根据迭代器所指对象能否改变,迭代器被分为两类:
- 不允许改变:constant iterators,如const int* pic;
- 允许改变:mutable iterators,如int* pi。
左值
如 i = 5 + 1,i 在运算符的左边,称为左值。
在C++中,如果函数要传回左值,都是以by reference的方式进行的:
- 如果p是一个对象值能改变的迭代器,设它的value type是T,那么*p的类型不能是T,而应该是T&;
- 如果p是一个对象值不能改变的迭代器,设它的value type是T,那么*p的类型不能是const T,而应该是const T&。
3.4.4 迭代器相应型别之四:pointer type
我们可以传回一个pointer,指向迭代器所指之物。
3.4.5 迭代器相应型别之五:iterator_category
根据移动特性与实施操作,迭代器被分为五类:
- Input Iterator:这种迭代器所指的对象,不允许外界改变,即read only;
- Output Iterator:write only;
- Forward Iterator:允许写入型算法在此种迭代器所形成的区间上进行读写操作;
- Bidirectional Iterator:可双向移动,即可以正向遍历,也可以反向遍历;
- Random Access Iterator:前四种迭代器只支持部分指针算术能力(前三种支持++,第四种在此基础上支持–),但是第五种则涵盖所有指针算术能力,如p+n、p-n、p[n]、p1-p2、p1<p2。
在编写代码的时候最好能够在编译期就能决定使用哪个版本,如果在运行期使用 if else 来判断,会影响效率,因此推荐使用重载函数来解决。
3.4.5 迭代器相应型别之五:iterator_category
根据移动特性与实施操作,迭代器被分为五类:
- Input Iterator:这种迭代器所指的对象,不允许外界改变,即read only;
- Output Iterator:write only;
- Forward Iterator:允许写入型算法在此种迭代器所形成的区间上进行读写操作;
- Bidirectional Iterator:可双向移动,即可以正向遍历,也可以反向遍历;
- Random Access Iterator:前四种迭代器只支持部分指针算术能力(前三种支持++,第四种在此基础上支持–),但是第五种则涵盖所有指针算术能力,如p+n、p-n、p[n]、p1-p2、p1<p2。
在编写代码的时候最好能够在编译期就能决定使用哪个版本,如果在运行期使用 if else 来判断,会影响效率,因此推荐使用重载函数来解决(不同的迭代器类型会有不同的计算法方式,以达到效率的最大化)。
STL算法命名规则: 以算法所能接受之最低阶迭代器类型,来为其迭代器型别参数命名(即最低层次,最泛化的那一个)。
3.5 std::iterator 的保证
STL提供了一个超类iterator,如果每个设计的迭代器类都继承自它,就可以保证符合STL的规范,iterators class不含任何成员函数,纯粹只是型别定义(因为如果设计的迭代器不含五个内嵌相应型别,traits就无法萃取它,它也会独立于整个STL之外)。iterator类如下:
template<class Category, // 没有默认值,需传参
class T,// 没有默认值,需传参
// 以下三个参数都有默认值
class Distance = ptrdiff_t,
class Pointer = T*,
class Reference = T&>
struct iterator {
typedef Category iterator_category;
typedef T value_type;
typedef Distance difference_type;
typedef Pointer pointer;
typedef Reference reference;
}
因此,声明一个迭代器类只需要继承它,然后指定 Category 和 T 的值即可:
template<class Item>
struct ListIter : public std::iterator<std::forward_iterator_tag,Item>
总结:
迭代器的责任:设计相应的型别(包含traits(泛化版、针对原生指针的偏特化版、针对const的偏特化版))
容器的责任:设计适当的迭代器,只有容器本身才知道如何设计一个迭代器来遍历自己,并执行迭代器该有的各种行为(如前进、后退、取值、取用成员等等)。
算法:则完全独立于容器和迭代器之外自行发展,只要设计时以迭代器为对外接口即可。
3.6 iterator源代码完整重列
3.7 SGI STL 的私房菜:__type_traits
- type_traits: 负责萃取迭代器的特性
- __type_traits: 负责萃取型别的特性,即判断这个型别是否具有 non-trivial 默认的构造函数、是否具备 non-trivial 拷贝构造函数、 non-trivial 赋值操作符、 non-trivial dtor(析构),如果不含有这些函数,那么在对这个类型进行构造、析构、拷贝、赋值等操作时,就可以采用最有效率的、直接针对内存的操作,如malloc()、memcpy()等等,从而获得最高的效率。
根据 iterator_traits 的实现方法,我们可以类比实现出 __type_traits (用来返回类型的特性):
typedef __type_traits::has_trivial_default_constructor; // 构造函数
typedef __type_traits::has_trivial_copy_constructor; // 拷贝构造函数
typedef __type_traits::has_trivial_assignment_operator; // 赋值运算符
typedef __type_traits::has_trivial_destructor; // 析构
typedef __type_traits::is_POD_type; // Plain Old Data
我们希望上面能够返回带true或者false的对象,因为我们希望根据该对象进行参数推导,因此我们应该传回(即一个类的对象):
struct __true_type {
}; // 表示可以用最快的方法(即针对内存的方式)来进行拷贝或辅助操作
struct __false_type {
};
__type_traits具体的一个实现:
template<class type>
struct __type_traits{
typedef __true_type this_dummy_member_must_be_first; // 不要删除该行,避免冲突
typedef __false_type has_trivial_default_constructor; // 构造函数
typedef __false_type has_trivial_copy_constructor; // 拷贝构造函数
typedef __false_type has_trivial_assignment_operator; // 赋值运算符
typedef __false_type has_trivial_destructor; // 析构
typedef __false_type is_POD_type; // Plain Old Data
}
保守起见,默认的所有对象都是 __false_type 的,即不能直接使用内存进行操作,然后通过定义特化版本的 __type_traits ,可以解决这个问题,如:
// 针对基本数据类型的偏特化版本
// __STL_TEMPLATE_NULL 是类模板的显示(excplicit)特化(specialization)
__STL_TEMPLATE_NULL struct __type_traits<char/int/double/...>{
typedef __true_type has_trivial_default_constructor; // 构造函数
typedef __true_type has_trivial_copy_constructor; // 拷贝构造函数
typedef __true_type has_trivial_assignment_operator; // 赋值运算符
typedef __true_type has_trivial_destructor; // 析构
typedef __true_type is_POD_type; // Plain Old Data
}
// 针对原生指针的偏特化版本
template<class T>
struct __type_traits<T*>{
typedef __true_type has_trivial_default_constructor; // 构造函数
typedef __true_type has_trivial_copy_constructor; // 拷贝构造函数
typedef __true_type has_trivial_assignment_operator; // 赋值运算符
typedef __true_type has_trivial_destructor; // 析构
typedef __true_type is_POD_type; // Plain Old Data
}
什么时候一个class该有自己的non-trivial-xxx呢:
- 如果class内含指针成员,并且对它进行内存动态配置,那么这个class就需要实现出直接的non-trivial-xxx。
边栏推荐
猜你喜欢
安徽《合肥市装配式建筑施工图审查设计深度要求》印发;河北衡水市调整装配式建筑预售许可标准
ArcGIS Pro + PS 矢量化用地规划图
MATLAB image histogram equalization, namely spatial filtering
数据库什么时候需要使用索引【杭州多测师】【杭州多测师_王sir】
RobotFramework学习笔记:环境安装以及robotframework-browser插件的安装
Use keil5 software to simulate and debug gd32f305 from 0
历史上的今天:微软收购 PowerPoint 开发商;SGI 和 MIPS 合并
scratch绘制正方形 电子学会图形化编程scratch等级考试二级真题和答案解析2022年6月
ArcGIS Pro scripting tool (5) - delete duplicates after sorting
Q-Learning笔记
随机推荐
Viewing technological changes through Huawei Corps (V): smart Park
Migrate full RT thread to gd32f4xx (detailed)
Auto SEG loss: automatic loss function design
Remember the experience of an internship. It is necessary to go to the pit (I)
经典面试题:负责的模块,针对这些功能点你是怎么设计测试用例的?【杭州多测师】【杭州多测师_王sir】...
LVGL 8.2 Image styling and offset
[rust daily] the first rust monthly magazine on January 22, 2021 invites everyone to participate
最新SCI影响因子公布:国产期刊最高破46分!网友:算是把IF玩明白了
[deep learning] common methods for deep learning to detect small targets
The intelligent DNA molecular nano robot model is coming
Skill sorting [email protected]+adxl345+ Motor vibration + serial port output
Unity Shader - 踩坑 - BRP 管线中的 depth texture 的精度问题(暂无解决方案,推荐换 URP)
Memory escape analysis
Input a decimal data, convert to 8, using the sequence stack
The AOV function of R language was used for repeated measures ANOVA (one intra group factor and one inter group factor) and interaction Plot function and boxplot to visualize the interaction
Anhui "requirements for design depth of Hefei fabricated building construction drawing review" was printed and distributed; Hebei Hengshui city adjusts the pre-sale license standard for prefabricated
Qt之实现动效导航栏
SGD has many improved forms. Why do most papers still use SGD?
MATLAB image histogram equalization, namely spatial filtering
超长干货 | Kubernetes命名空间详解