list 手动实现 1

在之前list的使用中发现list接口的使用和string及vector是类似的 这也体现出stl封装这些数据结构的意义 熟悉一个数据结构的使用方法后 其他的也很容易就能上手使用

本文来详细实现一下c++里面list的底层结构 这里实现遇到的主要问题其实就是迭代器的问题 string和vector因为天生物理结构是连续的 所以在实现他们迭代器的时候就就可以直接用做指针  

但是list物理空间上不是连续的 那list的迭代器为什么能和string及vevtor一样使用呢

------------------

在实现之前先说一下按需实例化 模版里面检查不严格只会检查简单的  比如少了；() 这种问题  很多的越界或者调用不存在的函数 很多问题都不会检查 只有在调用对应的函数时候实例化那个函数之后 才会报错 所以我们在写的时候可能有很多的问题了已经 但是没有给我们报出来 等我们使用的时候会一下子报很多错出来 要注意一下

首先在写list真正结构之前 需要先写一个list_node类型的类 来存一个节点的信息(数据 及前后位置的指针)  然后写一个含缺省值的构造函数 (这里缺省值的方式之前解释过  这样子主要是为了支持自定义类型的缺省值)  把前后指针都初始化为空指针 

list的类 成员变量就是刚刚写的节点类型的指针 head(哨兵位) 这里为了方便额外写的size  这里因为要频繁使用到刚刚的节点类 将其重命名为Node方便使用 

这里实现的无参默认构造函数 为头结点申请了一个节点的空间 然后让头结点的前后指针都指向自己 

然后实现尾插 

尾插要先给先新节点newNode申请一个空间   插入之前要先保存一下插入之前的最后一个元素的地址到prev  然后断开之前最后一个元素和头结点的连接  然后让prev的_next指向newNode  newNode的_prev指向prev head的_prev指向newNode newNode的_next指向head

迭代器的实现

在list里面实现迭代器和之前的string及vector的实现有很大的区别 

因为string vector是顺序表的结构 物理空间上是连续的 之前实现的迭代器就可以直接是类型的指针  解引用之后就是当前位置的元素 ++之后就是下一个元素的位置

但是对于lsit 因为还单独封装一个节点类 解引用之后是当前的节点 要访问值还需要 用 ._data的方式访问元素  还有物理空间上不连续 ++之后不知道到哪一个位置了 不是我们所想的下一个位置的地址

 如下图 想使用list迭代器的效果  发现不能使用

所以list迭代器的实现需要想办法来支持我们想要实现的效果

解决的方式是给迭代器封装一个类 里面的成员变量只有一个节点类型的指针  然后在里面用运算符重载的方式让它对外实现我们想要实现的效果

迭代器在对外使用上我们其实就可以把它当做节点类型的指针 (里面的唯一成员变量就是节点类型的指针 在类里面对这个成员变量的操作 类型对外的表现上像指针一样 且实现的功能由里面的重载决定)

例如接下来对解引用操作符* 及++  == ->进行重载

这里的解引用操作我们对外是想表现为 解引用之后是该节点位置的值date  _node此时是节点的指针 解引用之后就是当前节点 然后._date 就是当前位置的值了 

这样对外我们将迭代器使用的时候 用解引用操作就可以直接访问到了里面的值date

而++对外我们是想到达下一个位置的地址   当前位置的节点里面存着下一个位置的地址在_next中 所以 对于++重载 我们直接让_node指向下一个位置的地址

这里的==  !=重载 我们不是要对里面的值_data进行比较 重载是根据我们的需求来重载的

在之前的使用中我们知道 迭代器方式打印结束的条件就是等于end也就是最后一个位置的迭代器 那么他们判断的方式就是比较节点的指针 所以这里就用比较指针的方式实现      

在重载这些运算符之后  并在list中写了这样的迭代器

begin返回的是第一个元素的位置 也就是头结点的后一个位置 end返回的是最后一个元素的后一个位置 那么也就是头结点

iterator只是对外使用我们可以当做类型指针来直接使用 但是在实现功能的时候要注意 迭代器iterator是一个自定义的类 返回值是iteraotr 所以可以创建一个iterator类型对象 用对应的指针类型初始化传回去就可以 当然匿名对象的方式或者 隐式类型转化都可以

 就可以发现可以用迭代器的方式打印了  而底层就是迭代器的范围for打印方式也可以了 

->的重载很奇怪 返回值是T*类型 为什么这样呢

结合解引用重载来理解一下  _node是Node类型的指针 在解引用之后期望的是T(模版) 类型的date 所以返回的是(*node)._data  

那如果T是自定义类型的AA  用->的操作我们期望访问的就是AA类型的_a1或者_a2   但是在重载->中我们不知道这个自定义类型的成员变量是什么名字 所以不能直接返回自定义类型的成员变量 

这里采用的就是如下返回T指针的方式  

但是 这样不是离我们所期望的更远了吗  却可以按我们预期的方式来实现 如下图  

其实这是因为还隐含了一个->  真正情况其实下面这样 it调用operator-> 返回了T* 这里就是AA* 然后对于AA*又调用了一个原生的-> 然后访问到了_a1和_a2    那么为什么这样设计呢 没有别的 就是为了可读性

虽然只写一个-> 真正的情况就是两个-> 第一个是重载的-> 第二个是原生的

然后顺便把后置的++及  --都给重置了  后置的需要先存处理前的_node

然后实现insert  insert也很简单  和尾插没什么区别 给新的节点开了空间后 存节点然后改变相应指向就可以了

 再强调一下  迭代器的封装使得在使用的时候可以根据我们想实现的功能像指针一样来实现 但是在功能的实现上我们要以里面的_node来进行 通过_node 才能找到前一个和后一个位置的指针

其实写了insert之后 尾插和头插直接赋用inseet就可以了

erase的实现及头删尾删和insert类似

之前在vector实现过下面的打印函数  任何容器都可以使用  里面用到的是范围for 但是当我们用该函数打印的时候会报错  而之前我们正常使用范围for的时候没有出现过这样的问题 为什么呢

这是因为这里的函数形参是const修饰过的  范围for的打印底层用到的是迭代器

在之前我们使用的时候

const类型的迭代器是用cosnt_iterator(整体是一个类型)的方式 那为什么不直接用const iterator的方式呢

这里和const修饰指针类似

这里的迭代器也是一样的道理

const_iterator 表示指向的内容不能改变

const iterator表示迭代器本身不能改变

所以我们还需要实现const_iterator

const_iterator的实现也可以重写一个类 相较于iterator只需要改变下面这两个 这里主要是返回值用const修饰  this用const修饰是为了和普通的迭代器区分 

const类型对象调用const类型的迭代器 返回的就是const类型

普通对象可以调用普通的可以调用const的 会先匹配适合自己的

如上 *it应该不能改变 但是当没有调用这个函数的时候没有报错  还是按需实例化的问题 函数模版只有使用时候实例化成函数才会会报错 没有实例化之前之后检查简单的错误

在这样写了const类型迭代器之后 刚刚在打印函数中不能使用的范围for打印就可以使用了

iterator和const_iterator里面大部分基本类似 完全重写的话就很浪费空间了 其实很有一种方式可以解决这个问题 stl中的list这块就用的这样的方式

list源代码解决iterator和const_iterator问题