模板类+迭代器模拟实现STL::List双向循环链表

2017-04-12 14:19 阅读 799 次 评论 0 条

理解迭代器是理解STL的关键所在。模板使得算法独立于存储的数据类型,而迭代器使算法独立于使用的容器类型,因此,它们都是STL通用方法的重要组成部分。作为STL的六大组件之一,无疑起到了举足轻重的作用。

迭代器的简介?

迭代器(iterator)是一种对象,它能够用来遍历标准模板库容器中的部分或全部元素,每个迭代器对象代表容器中的确定的地址。迭代器修改了常规指针的接口,所谓迭代器是一种概念上的抽象:那些行为上像迭代器的东西都可以叫做迭代器。然而迭代器有很多不同的能力,它可以把抽象容器和通用算法有机的统一起来。

为什么要引入迭代器?

首先我们看一个例子:下面是两个不同的数据结构,即数据和单链表,我们所要采取的是查找值为key元素,并返回它的地址。

①数组:在数组array中查找值为key的元素

②单链表:在链表List中查找值为key的结点

从某种程度上来讲,两个查找算法所示不同的:一个使用数组索引来遍历元素,另一个通过链表的next域查找。但从另一方法,两者的算法却是相同的,都是将某个值域容器中的每个值进行逐次比较,直到匹配为止。

泛型编程旨在使用同一个查看函数来处理数组、链表或任何其他容器类型。即函数不仅独立于容器中存储的数据类型,而且独立于容器本身的数据结构。模板提供了存储在容器中的数据类型的通用,因此还需要遍历容器中值的通用表示,所以就有了迭代器的出现。

③迭代器类型:查找值为key的元素

通过定义迭代器的首尾指针对链表也可以进行++操作,当然这只是迭代器的九牛一毛。

迭代器提供一些基本操作符:*、++、==、!=、=。这些操作和C/C++“操作array元素”时的指针接口一致。不同之处在于,迭代器是个所谓的复杂的指针,具有遍历复杂数据结构的能力。其下层运行机制取决于其所遍历的数据结构。因此,每一种容器型都必须提供自己的迭代器。事实上每一种容器都将其迭代器以嵌套的方式定义于内部。因此各种迭代器的接口相同,型号却不同。这直接导出了泛型程序设计的概念:所有操作行为都使用相同接口,虽然它们的型别不同。

迭代器的5大类型

上面就是5种迭代器的说明,今天要实现的双向循环链表使用的正是双向迭代器,下面我会简单说一下双向链表的特性。

STL::List库中的基本操作

当然,我不可能把库里面每一个操作都实现一遍,有些实现也是没有意义的,我只会实现常用的库函数,当然,实现List库函数是为了方便理解迭代器,双向链表仅仅是一个陪衬。

STL库中List的特性

在STL库中List是一个双向循环且带头结点的链表,它的原型是:

源代码及注释

模板提供了存储在容器中的数据类型的通用,迭代器使得容器中的值的通用,在某种程度上,迭代器就好比一个智能指针,它对原始指针进行了封装,并且提供一些等价于原始指针的操作,做到既方便又安全。

版权声明:本文著作权归原作者所有,欢迎分享本文,谢谢支持!
转载请注明:模板类+迭代器模拟实现STL::List双向循环链表 | 术与道的分享
分类:编程素养 标签:,
1024do.com导航_术与道导航平台

发表评论


表情