现在的位置: 首页 > 操作系统 > 正文

C++头文件系列(iterator)

2020年02月10日 操作系统 ⁄ 共 2817字 ⁄ 字号 评论关闭

简介

该头文件围绕迭代器展开,定义了一系列与迭代器有关的概念,但最最最重要的一点就是----它和其它容器一起实现了C++容器的Iterator设计模式

Iterators are a generalization of pointers that allow a C++ program to work with different data structures(containers) in a uniform manner.

上述文字摘自C++14标准草案,简而言之,迭代器就是对指针的一层封装,提供了统一的接口

使用迭代器有很多好处:

访问数据内容,同时不暴露其内部结构,降低耦合性支持multiple traversal(即同时有多个遍历发生)。提供统一的访问接口和多态遍历(该多态为静态多态,发生在编译期)。

详细请见设计模式。

迭代器类别

迭代器主要有5类([iterator-class]代指该类迭代器支持的操作集):

这里有两点需要特别说明:

multi-pass:它的意思是支持同时多次个遍历这个概念有待验证)。解引用:该操作是有限制的,只能出现在赋值语句的左边

不难看出,这几类迭代器有如下关系:

迭代器 与 指针

因为迭代器实际上是指针的抽象,很多功能概念都是从指针身上“扒”下来的,所以它的语义跟指针是一致的

这意味着什么呢? 这意味着可以传入指针作为迭代器, 因为指针上的操作集(递增、递减、算数运算等)是迭代器的超集,模版定义对迭代器所做出的操作要求放在指针上完全适用。

这在操纵内置数组的时候,可以省去不少麻烦(不用再去敲多余的代码来生成iterators):

int numbers[] = { 1,2,3,4 };std::find(numbers, numbers + 4, 2);

迭代器基础设施

标准库提供了以下4个方面的设施来帮助用户使用iterator。

iterator_traits类

“traits”是特性的意思,所以“iterator_traits”是迭代器特性的意思。 从代码角度看,这里的traits就是types,因为这个类只包含了五个类型定义:

difference_typevalue_typereference

pointer

iterator_category

因为algorithm在C++是单独的一块,是iterator将容器与算法沟通在一起。 也就是说,标准库的算法只是通过迭代器来进行数据操作。 必然而然的,一些操作需要有对应的类型: 1) 例如,应用distance库函数计算迭代器的距离,应该返回“距离”类型的值。 2) 例如,获取迭代器指向的对象,应该返回“对象值”类型的对象。 等等...

所以,标准库的算法需要我们定义这些类型,好让它在应用算法的时候使用正确的类型。

需要注意的是,当迭代器为output iterators时,上面的4个类型可能被定义为void(可能对于output iterator来说,这四个类型都没有多大意义,它支持的操作非常有限)。

iterator类

上面这个iterator_traits类取自某个库的iterator实现,可以看到,默认的iterator_traits模版内的类型定义都取自迭代器中相应的类型,即_Iter迭代器类。 所以我们在定义自己的迭代器的时候,如果定义了这些类,就不用再显示实例化iterator_traits模版了,它能自动提取出这些类型。

这时候就轮到我们的iterator类来大显身手啦! 用户只要继承这个base class并指定两个参数,就可以获得剩余的三个类型定义,因为它的定义是这样的:

iterator category tags

对应迭代器类别,这里也有5类标签(tag),名称为XXX_tag,XXX对应迭代器名称。

这个标签的作用主要是实现标签派发功能,提供迭代器类型信息,从而让C++库算法可以选择合适的、高效的操作来完成算法(可参见下一小节)。

iterator functions

头文件还提供了一些方便的操纵迭代器的函数供用户使用:

advance(步进)distance(距离)next(下一个)prev(上一个):只支持双向迭代器以上(因为单向迭代器不支持“--”操作符)。

对于不同类型的迭代器,上述四个函数采用不同的方法进行计算,例如:

随机访问迭代器支持算数运算,故使用“+”和“-”操作符进行运算(若两个迭代器分别为first和last,则计算他们之间的距离只需要last - first)。单向迭代器只支持递增运算,故使用++运算符进行运算(若两个迭代器分别为first和last,计算他们之间的距离需要重复对first进行递增,知道first == last)

迭代器适配器

标准库包含了三种迭代器适配器:

    Reverse iterator:这种迭代器对元素进行反向迭代。 注意,当从某个迭代器构造出reverse iterator时,新的迭代器不再指向先前的元素,而是指向前一个元素(按旧迭代器的顺序),因为end iterator逆转过来才是begin iterator。

    Insert iterator:通过迭代器进行元素的插入时,操作略有不同。 指针通常是指向已有的内存,因此迭代器一般也只是对指向地址的元素进行赋值;而插入元素是需要先分配内存,再赋值。 为了能让使用者像使用一般迭代器那样进行元素的插入,标准库提供了3种插入迭代器

    back_insert_iteratorfront_insert_iteratorinsert_iterator

    Move iterator:移动迭代器会将内部的迭代器的操作返回值全部转换成右值(rvalue)。

生成函数(Generators)

back_inserterfront_inserterinsertermake_move_inserter

这些都是全局模版函数,利用类型推导帮助用户构造上述的三种迭代器适配器。

流迭代器

输入输出一直是语言非常重要的部分,对于C++迭代器来说,操纵流(stream)中数据的输入输出的重要性毋庸置疑。 Stream Iterator则是针对stream的一套迭代器,包括istream,ostream,istreambuf 和 ostreambuf。

以下两种是input iterator:

istream_iteratoristreambuf_iterator

以下两种是output iterator:

ostream_iteratorostreambuf_iterator

本文永久更新链接地址:http://www.xuebuyuan.com/Linux/2017-02/140200.htm

以上就上有关C++头文件系列(iterator)的相关介绍,要了解更多C++ 头文件,iterator,C++ 头文件系列(iterator),编程,Linux编程,Linux Shell,Android,Android教程,JAVA,C语言,Python,HTML5内容请登录学步园。

抱歉!评论已关闭.