【C++】简单学——list类

模拟实现之前需要了解的

概念

带头双向链表（double-linked），允许在任何位置进行插入

区别

相比vector和string，多了这个

已经没有下标+[ ]了，因为迭代器其实才是主流

（要包头文件<list>）

方法

构造

和vector的构造差不多，无参、n个、迭代器、拷贝构造

迭代器失效

因为底层结构不一样

在list中的迭代器不会因为insert的挪动和扩容而失效，erase删除到自己就会失效

clear会把所有节点清楚，但是不清楚哨兵位

特殊的方法Operations

逆置reverse

排序sort

（默认升序，如果要改就要传仿函数）

list的排序意义不大，因为这个排序的效率太低

甚至vector还进行了两次拷贝构造，都比list高了差不多四倍的效率

list底层用的是归并排序，访问效率太低导致的，并不是算法本身效率低

合并merge

本质上就是取小的尾插

去重unique

但是要求先排序

remove

给一个值，然后进行删除（和erase不同，相当于是find加erase，find到了就删，没find到就不删）

remove_if

条件删除，和仿函数有关

splice

名字没取好，应该叫转移

作用：把某些值转移到某个位置去

pos就是位置之前，一个链表、某个链表的一个位置、某个链表的一部分

也可以自己转移自己

用法2

不删除节点，只会改变指向，把1转移到哨兵位之前，也就是4后面

用法1

把前面的那个链表整个转移到另个一链表的某个位置

另一个链表因为被转移了，所以list1就没节点了

转移的前提是类型必须匹配

链表的内部实现

1.先看源码

节点

链表的成员变量

link_type其实就是list_node*；成员就是一个节点指针

2.看构造函数

总结：调用了一个空初始化，然后这个空初始化建了一个哨兵位头结点（get_node()），然后next和prev都指向自己

以下内容看看就好

空间配置器调用一个allocate的接口来获取空间（单纯的获取节点）

创建一个节点，顺带初始化

3.看push_back

在哨兵位（end）的头结点那里插入，在哨兵位的prev插入，就是尾插

insert和我们自己搞的差不多，就不用多看了

主要是迭代器比较麻烦
 

正式开始模拟实现

非常需要画图

先搭个架子出来

list需要节点，所以需要再建一个节点类出来，节点用的是struct（库里面也用的是struct，只要是是需要大量公开的内容都可以用struct）

 链表的成员：

节点

成员变量

1. 下个节点位置的指针
2. 上个节点位置的指针
3. 存值的地方

成员方法

• 构造函数（在链表的构造函数地方，逻辑是先搞一个哨兵位头结点，然后指针全都指向自己，而在搞一个哨兵位头结点的时候会用到new Node，此时new Node就会去调用节点类的构造函数，所以我们需要提前把构造函数准备好）

链表

成员变量

1. 一个哨兵位的头结点

构造函数

就先搞一个哨兵位头结点

pushback

暂且不考虑insert复用，因为要用到迭代器

尾插逻辑：

新建一个节点，然后让节点之间连接上：尾插就是在head的prev

步骤

1. 先新建一个节点
2. 记录没插之前的tail
3. 然后修改tail和newnode和head之间的指向

因为有哨兵位，所以就算没有节点，当他们进行尾插的时候也不用考虑自己是第一个节点要怎么操作，这个是这个设计的优势（主要工作就是找到tail和head，因为有哨兵位，所以哪怕没有节点，tail也是head->prev=自己；剩下的就是改变指向了）

现在先实现一下遍历数据（前提就是有迭代器）

我们的目的是实现以下的遍历功能

1. list<int>::iterator it = lt.begin();
2. lt.end()
3. *it
4. ++it

这四个功能对于list迭代器来说：

list的迭代器不能用原生指针

因为节点空间不连续（没办法直接typedef T* iterator,因为list的T是节点，只用节点指针没办法搞定

1. list<int>::iterator it = lt.begin();（这个倒是可以用这个访问方式）
2. lt.end()（这个也可以解决）
3. *it(对节点指针解引用得到的是节点，而不是节点的值，不满足)
4. ++it（++it实际达到的效果是it指针在地址上往前移动一个节点size单位的空间，并不会到下一个节点处，不满足）

原因：List是一个节点一个节点开辟空间的，所以空间一定是不连续的

）

vector可以的原因

1. 每个节点之间都是连续的，而且T就是数据的类型，每次++的时候都是往前走T类型size的空间，刚好就可以走到下一个节点处
2. 解引用之后就可以得到T的值，即自己想要的数据

需要解决的问题：

1. *it(对节点指针解引用得到的是节点，而不是节点的值，不满足)
2. ++it（++it实际达到的效果是it指针在地址上往前移动一个节点size单位的空间，并不会到下一个节点处，不满足）

类比：

Node*原生指针不能满足我们的需求

我们的那个日期类，如果想要做到++或者日期减日期，这种操作原本都是不能直接用的，但是我们内部可以自己去控制（凭借运算符重载）

因此，如果我们没办法用原生指针去实现*it和++it，那我们就自己去封装一个迭代器的类（即内置类型不能解决我们的问题，那我们就实现成自定义类型），然后就写（typedef 迭代器的类 iterator；），这样就可以照常使用了

这个迭代器的类名字不重要，毕竟之后都是要用来typedef的

库里面也是这样实现的

可以看到，库里面的那个迭代器类的成员变量用的也是原生节点指针（link_type就是list_node*），在list里的迭代器也是原生节点指针，只不过因为原生节点指针的功能不符合我们的预期，所以我们就改造一下，用一个类去封装，然后去把这个原生节点指针的运算符给重载成我们需要的功能，就可以去掌控迭代器的功能了

也就是可以做到以下功能

1. *it(返回节点的值，调用operator*)
2. ++it（跳转到下一个节点，调用operator++）
3. (还有一个没有说的，因为迭代器类的成员变量就是一个节点指针，所以当sizeof这个迭代器的时候，得到的迭代器大小就是4，而这个4恰好就是自己那个节点指针的大小)

（类型决定了我们的行为是什么，如果是单单的原生指针，那++就是到下一个节点大小的位置处；如果说我们封装了这个原生指针，修改了这个类型的具体行为，那++我们就可以修改为到下一个节点）

实现迭代器类

迭代器的行为是统一的，目的是不关注底层实现，而是要关注用指针类型的来访问和修改元素

我们的迭代器类是实现成struct的，因为我们要让外面的人能直接用

成员变量：节点指针

成员方法：构造函数、operator++()、后置++：operator++(int)、

构造函数

使用场景：List<int>::iterator it = lt.begin();

这个it就是在用 lt.begin()的返回值Node* 来进行初始化

前置++和后置++（--也类似）

前置++返回的是++后的自己，后置++返回的是++前的自己

这个地方另外再typedef ListIterator<T> Self是因为后置++要返回的是原本的自己，也就是ListIterator<T> it或者说是*this

（这个地方会有点绕，因为this就是自己的指针，而中的自己则是ListIterator<T> it，所以需要解引用之后再返回）

 为了写的方便，所以我们把ListIterator<T>给typedef成了Self

所以：就是ListIterator<T> tmp(*this)

我们通过重载++修改了++的规则，让++可以正确地指向下一个节点

拷贝构造

在这个地方我们可以不用写拷贝构造，可以直接让编译器给我们自己生成那个浅拷贝的拷贝构造，因为我们的成员变量是一个节点的指针，浅拷贝这个节点的指针目的就是让那个拷贝构造出来的迭代器也指向那个节点，要的就是浅拷贝（并非成员变量中有指针就要深拷贝，要看具体情况）

用it拷贝构造出it2，it2也同样指向节点值为1的那个节点

析构函数

不需要写析构，析构的目的是为了释放资源，而迭代器指向的那块空间并不是属于迭代器的，而是属于list的，迭代器的作用仅仅是访问或者修改值，不需要析构

解引用

解引用要实现读和写的功能

运算符

operator!=和==

问：需不需要重载比较大小

要看有没有意义

答：不需要，因为没有意义，如果说是比较节点所在的位置的大小的话还好，但是这个是比较迭代器的大小，每个节点在new的时候地址都是无规则的，根本就不能保证后面的节点一定就比前面的节点的地址要大

正式开始链表类

目前已经搞好了迭代器类

现在我们要做的就是把这个迭代器和我的list连接起来

总结一下前面的部分：

 我们做的链表类是一个带头双向链表

我们的节点是一个个数据单元，我们的链表就是要把他们链接起来

链表的迭代器因为原生节点指针无法满足我们的功能，所以我们用一个类去封装了一下节点指针，再用运算符重载来掌控他的行为

还是要重申一下结构：这个链表类需要和迭代器类和节点类结合起来使用，他们之前的关系是并列的，其中，节点类和迭代器类使用的是struct，设置成struct就是为了让list可以访问，是专门为list类服务

如果说我们要访问我们的链表，那我们就要从第一个节点(_head->next)开始

begin()和end()

因为只有list类才知道链表的开头是在哪里，所以我们的begin要写在链表类里

上面的写法和下面的写法一样，没什么区别，只不过上面用了匿名对象

甚至可以这样写：走隐式类型转换，

有了这个我们就可以实现前面没有实现的遍历了

insert

问：为什么还要用cur记录pos，而不是直接用pos，不都是指向同一块空间吗？迭代器不就是指针吗？为什么还要取_node出来

答：迭代器是一个封装了节点指针的类，类里面放了节点指针，也就是_node，现在把他拿出来才可以进行找prev和next的操作，因为只有ListNode才有prev和next，迭代器只是ListNode*的一个盒子

erase

别忘了改变指向后还要delete

delete的是cur，而不是pos，我们不是delete外面的那个盒子，而是那个节点

pos已经被erase了

这个地方要小心迭代器失效的问题

所以我们要返回next（利用next构造一个next迭代器回去）

push_front和push_back

pop_back和pop_front

这个地方用--不要用-1，因为我们只提供了operator--没有提供operator-

然后我们就可以用范围for了

（因为底层被替换成迭代器了）

size

两种方案

1. 每一次调用size()的时候都遍历一遍（库里是这样实现的）
2. 加一个成员变量size_t size;每次创建节点的时候都size++，减少的时候就--（这个地方不是用静态成员变量，因为每个链表的长度都不一样，静态成员变量倒是可以记录一共创建了多少个链表，但绝对不是这里）（我们实现这个）

• 成员变量加上_size
• size方法直接返回成员变量_size
• 初始化的时候赋值0 
• 每次插入的时候都++
• 每次删除的时候都--

empty

因为我们实现了_size，所以我们就直接看_size就好

也可以用_head来用

resize

这个我们就不写了，因为链表没有容量的概念，所以基本上就是n比size大，就往后尾插一堆，n比size小，就尾删一堆

假如说我们的链表要存储自定义类型

匿名对象

有名对象

多参数构造的隐式类型转换

C++11特有的：{}多参数的构造函数也支持隐式类型转换了，用花括号（这个地方不是initailizer_list类型）

但是这样子没办法遍历

这里是说<<不支持A类型使用

因为我们的A类型里面没有写

但如果对方不想写operator<<怎么解决

如果对方是公有的，我们就自己拿

但是这个地方怎么看怎么别扭，因为我们的迭代器的目标是模拟当前类型的指针，既然是指针，肯定就应该能像下面这样直接用箭头访问

所以我们还可以重载一个operator->

operator->

返回的是那个T类型的值的指针

这个地方会很诡异

如果用替换的方法的话，替换出来应该是A*a1,问题是A*是怎么直接啥都不用就可以访问a1的呢？

答：这个地方隐藏了一个箭头，编译器为了可读性省略了一个箭头

也可以不省略写，都一样

我们要把it当成A*来设计，迭代器就是模拟的T*

外面的箱子iterator里面放了一个小箱子A，从小箱子里面取一个物品_a1

我们用迭代器的时候就是希望直接通过->取_a1,所以operator->和operator*都是要跨两层的

const迭代器

如果直接在原本的begin或者end那个前面加上const，是没办法解决问题的

如果只是读的话那还好，因为非const的成员用const迭代器是权限的缩小，所以也可以用

我是一个const的链表，但是你通过非const的迭代器修改了我的值

罪魁祸首就是那个加了const的begin和end，原本迭代器是没办法去接收const成员的迭代器的，因为const成员不给你begin你就没辙

但是加了const之后，const成员也可以给你begin了，而你却只是一个普通迭代器而不是const迭代器，所以普通迭代器肯定可以修改

（const链表调用之后返回了普通迭代器）

因此我们需要增加一个可以返回const迭代器的重载版本，然后普通的链表就会调用普通迭代器，const的链表就会调用const迭代器

问：为什么不能写成这样？

答：上面写的const iterator是指本身这个iterator不能被修改

而const_iterator是指迭代器指向的内容不能被修改；

况且，iterator是一个类，如果说用const了这个类，就代表这他连++都调用不了了，因为类的那些成员不能被修改

所以我们得自己实现一个const_iterator类，让迭代器本身可以修改，但是指向的内容不能修改

我们需要解决的问题

1. *it += 10不能操作
2. clt.begin()返回的是const_iterator

这个地方可以干脆直接把原本的iterator给拷贝一下，稍微修改一些功能，让前面的两点功能能够实现

const_iterator就是一个普通 iterator的一个cv版本，只是修改一下名字，以及处理一下写方面的东西

就是因为cv版本，所以两个感觉有些冗余了，所以接下来的目的就是解决这个冗余

解决冗余（加模板）

就这两个返回值不同

想办法合并，用模板，用一个模板参数来控制

模板参数传引用、传指针

在这个地方，只要传一个T过去就可以了，另外两个会根据T而改变

本质上我们写了一个类模板

编译器实例化生成了两个类

• 如果说我们搞的是const的链表，那我们在使用迭代器的时候就要用const_iterator,然后const_iterator会根据你的T类型，编译器生成各种const T& 和const T*的迭代器，然后当我们进行*it+=10的时候，会因为*it 返回的是const的T&而报错
• 如果说我们搞的是普通链表，那我们在使用迭代器的时候就要用iterator,然后iterator会根据你的T类型，编译器生成各种T& 和T*的迭代器，然后当我们进行*it+=10的时候，就可以修改了

小小收个尾

还没有销毁链表

~list和clear

原本因为erase搞了之后，会迭代器失效，但是因为我们的erase返回了下一个迭代器，所以就可以这样

其实这个应该叫clear

但是这个it是到end就停下来，也就是说头结点没有被释放

所以说~list应该这样写

拷贝构造

默认的拷贝构造是一个浅拷贝，其中一个析构，另一个就全是野指针了

所以我们要自己实现

我们可以增加一个empty_init(其实就是把无参构造的内容给单独拿出来了)

这样会比较方便拷贝构造（因为在pushback的前提是有个哨兵位头结点）

拷贝逻辑：遍历另一个链表，然后全部插入

T有可能是string，所以auto要加上引用

链表的赋值

顺便也把swap给搞了

swap逻辑：交换成员

技巧：

因为需要析构，就是申请了资源的，有资源的肯定就是指针指向那个资源，然后就需要深拷贝的了