精选文章 C++STL 体系结构与内核分析(侯捷)——课程笔记(十一)

C++STL 体系结构与内核分析(侯捷)——课程笔记(十一)

作者:Niu Yutao 时间: 2020-08-05 08:27:24
Niu Yutao 2020-08-05 08:27:24

现在开始了算法的讲解。本部分包括迭代器的类型以及其对算法的影响,还包括一点traits的内容。

STL中的Algorithms对Containers一无所知,所以它需要的一切信息都必须从Iterators取得,而Iterators必须能够回答Algorithms的所有提问,才能搭配Algorithms的所有操作。

一、iterators的各种iterator_category

一共有五种iterator_category,每种category都是一个class,并且它们之间还存在一些继承关系,如下图所示:

C++STL 体系结构与内核分析(侯捷)——课程笔记(十一)1

(注意图里面forward写错了)

forward_iterator_tag、bidirectional_iterator_tag、random_access_iterator_tag不用说了,比较特殊的是input_iterator_tag和output_iterator_tag,istream_iterator的iterator_category是input_iterator_tag,ostream_iterator的iterator_category是output_iterator_tag,这两个并不属于容器的迭代器,特别是output_iterator_tag还有“只写”的特殊行为。

二、iterator_category对算法的影响

1. 根据iterator_category的不同,调用不同版本的处理函数,下面举两个例子:

(1) distance()函数用来求解两个迭代器之间的距离。所以当迭代器是随机访问迭代器时,距离可以直接相减得到,其他情况需要依次遍历。

template 
inline iterator_traits::difference_type
distance(InputIterator first, InputIterator last){
    typedef typename
        iterator_traits::iterator_category category;
    return __distance(first, last, category());
}

template 
inline iterator_traits::difference_type
__distance(RandomAccessIterator first, RandomAccessIterator last,
           random_access_iterator_tag){
    return last - first;
}

template 
inline iterator_traits::difference_type
__distance(InputIterator first, InputIterator last,
           input_iterator_tag){
    iterator_traits::difference_type n = 0;
    while(first != last){
        ++first; ++n;
    }
}

(2) advance()函数将一个迭代器向前移动n步,如果是随机访问迭代器可以直接得到,如果是双向迭代器还要注意n的正负代表了移动的方向。

template 
inline void advance(InputIterator& i, Distance n){
    __advance(i, n, iterator_category(i));
}

template 
inline typename iterator_traits::iterator_category
iterator_category(const Iterator&){
    typedef typename iterator_traits::iterator_category category;
    return category();
}

template 
inline void __advance(RandomAccessIterator& i, Distance n,
                      random_access_iterator_tag){
    i += n;
}

template 
inline void __advance(BidirectionalIterator& i, Distance n,
                      bidirectional_iterator_tag){
    if (n >= 0)
        while(n--) ++i;
    else
        while(n++) --i;
}

template 
inline void __advance(InputIterator& i, Distance n,
                      input_iterator_tag){
    while(n--) ++i;
}

三、iterator_category和type traits对算法的影响

1. copy(first, last, destination_start)函数

C++STL 体系结构与内核分析(侯捷)——课程笔记(十一)2

(1) 先对copy()函数定义重载版本,如果传入的类型为某些特定类型(如图所示),就调用较快的C的库函数。

(2) 对传入的迭代器也要进行一些判断,通过iterator traits分辨出作为class的迭代器和普通指针,如果是作为class的迭代器,通过iterator_category判断是否为随机访问迭代器,如果是的话就可以优化copy动作(用n决定循环次数),如果不是,就要使用迭代器作为循环变量进行拷贝。

(3) 在(2)中如果iterator_traits分辨出的是普通指针,那么就要通过type traits判断指针指向的对象有没有non-trival的拷贝赋值运算符,如果没有说明对象是基本类型或者是由基本类型组成的简单class,就会调用C的库函数;如果有的话,就需要迭代进行拷贝赋值操作,当然可以用n作为循环变量,因为迭代器是普通指针。

2. destroy()函数

C++STL 体系结构与内核分析(侯捷)——课程笔记(十一)3

分析过程与1类似,不再详述

3. __unique_copy()对于output_iterator_tag的特殊处理

C++STL 体系结构与内核分析(侯捷)——课程笔记(十一)4

因为output_iterator_tag是只能写的,不能读取,所以要针对这个版本做特殊处理

最后还有一个小tips,叫做算法源码中对iterator_category的暗示,这是指可能有某些函数只能接受某些类型的迭代器,就比如说sort()只接受随机访问迭代器,但是在语法上(函数模板的语法)不禁止传入其他类型的迭代器,但是在源码中会把模板参数的名字命名为相应的迭代器类型,起到提醒使用者的目的。

勿删,copyright占位
分享文章到微博
分享文章到朋友圈

上一篇:2020B证(安全员)考试及B证(安全员)模拟考试题库

下一篇:pcl点云:降采样&VoxelGrid

您可能感兴趣

  • python前端学习之js

    01-Javascript简介 Web前端有三层: HTML:从语义的角度,描述页面结构 CSS:从审美的角度,描述样式(美化页面) JavaScript:从交互的角度,描述行为(提升用户体验) JavaScript历史背景介绍 布兰登 • 艾奇(Brendan Eich,1961年~),1995年在网景公司,发明的JavaScript。 一开始JavaScript叫做LiveScript,...

  • Linux命令总结

    命令总结: mkdir -p (递归创建目录)创建目录的命令 make directorys。 ls -l(long)d(directory)a(all)显示目录或者文件 全称list。 vi/vim 类win记事本/emeditor编辑器,命令模式(:wq :q :q! :wq!)<==>插入模式(esc切换命令模式) :set nu显示行号,dd删除当前行,yy拷贝当前行,p粘帖。行号g...

  • 微信小程序开发教程、小程序资讯、小程序demo合揖(10月16日更新)

    2019独角兽企业重金招聘Python工程师标准>>> 本帖最后由 小程序社区管理员 于 2017-10-16 10:36 编辑**(50+个DEMO和80+篇教程)** 1:微信小程序官方工具:https://mp.weixin.qq.com/debug/w ...

  • 计算机软件方面的面试题?

    作为刚刚毕业参加工作的本科生,初出茅庐的这点儿经验和建议自然无法和业界大佬的相提并论,就姑且算作是我的小总结吧;对你有用就更好啦! 一.我的第一份工作经历了两轮面试,第一次是项目经理到学校进行的校招,第二次是与项目技术人员进行的视频面试。 P公司是3月份大三下学期开学后第一个来我学校进行校招的公司,因为我一开始就没打算考研,所以对打好招呼要来校招的公司都给与了足够的重视, 放寒假前就知道P公...

  • 左耳朵耗子给出的学习指南

    转载 http://www.cnblogs.com/wangtongxue/p/3273480.html 你是否觉得自己从学校毕业的时候只做过小玩具一样的程序?走入职场后哪怕没有什么经验也可以把以下这些课外练习走一遍(朋友的抱怨:学校课程总是从理论出发,作业项目都看不出有什么实际作用,不如从工作中的需求出发) 建议: · 不要乱买书,不要乱追新技术新名词,基础的东西经过很长时间积累而且还会在...

  • 程序员的十层楼及读后感

    自西方文艺复兴以来,中国在自然科学方面落后西方很多,软件领域也不例外。当然现在中国的许多程序员们对此可能有许多不同的意见,有些人认为中国的程序员水平远落后于西方,有些则认为中国的程序员个人能力并不比西方的程序员差,只是整个软件产业落后而已。 那么,到底中国的程序员水平比西方程序员水平差,还是中国有许多优秀的程序员达到或超过了西方程序员同等水平呢?要解决这个问题,必须先知道程序员有多少种技术层...

  • 嗯嗯------摘抄

    2019独角兽企业重金招聘Python工程师标准>>> 我大学本科毕业以后就从事信息与计算科学专业建设和教学,和同事一起带领我的学生们一起探索。。。。都七个年头了,取得了一定的成绩、也得到了不少的感悟!感觉教学不仅仅是学习知识的问题,学生的思想引导、管理和领导同事之间的微妙关系,都会影响到专业的方向和发展!很多时候并不是你付出了,学生就能理解你,同事就能支持你!很多时候不做事更轻松,一做事,...

  • 老兵不死,只是凋零:前九枝兰架构师王晓辉

    他曾是以一位人民教师,他是程序开发界的一名老兵,你可能没有听过他,他有着十多年的开发经验,先后在做过计算机老师,并且在私企、外企、互联网公司、创业公司里做程序开发和技术管理工作。“惟正己可以化人,惟尽己可以服人。”他就是本期程序员客栈专访前九枝兰架构师,王晓辉:https://www.proginn.com/community/topics/356 1,程序员客栈王鑫:我还是叫你老师吧,您先...

华为云40多款云服务产品0元试用活动

免费套餐,马上领取!
CSDN

CSDN

中国开发者社区CSDN (Chinese Software Developer Network) 创立于1999年,致力为中国开发者提供知识传播、在线学习、职业发展等全生命周期服务。