stl源码剖析list,stl list遍历
Yyds干货库存
写到这里，我们知道了STL的具体框架，你会发现里面的一些函数都是用同样的方法。这篇博客主要讲迭代器的子封装。我们皱眉串和向量的迭代器是原生指针，但是今天的不同。这里你会发现，既然我们的字符串和向量都可以支持下标访问，为什么迭代器还存在？今天的列表你会发现它不支持下标。为了统一，我们的STL支持迭代器。
我们来看看list中的函数，其中最重要的是构造函数。这里先看用法，不要在意原理。这里就不说那些熟悉的功能了，后面实现的时候再说。
构造函数一共有四个构造函数，其中我们可以只把比较常用的拿出来。
构造器
界面描述
list (size_type n，常量值_类型val=值_类型())
由构造的列表包含n个值为val的元素。
列表()
构建一个空列表
列表(常量列表x)
复制构造函数
列表(输入运算符在前，输入运算符在后)
使用[first，last] interval中的元素构建一个列表。
首先，测试构造的列表是否包含n个带有val值的元素。
#包括iostream
#包含列表
使用命名空间std
int main()
{
list int l(10，1)；
返回0；
}
看看另一个没有参数的构造函数。
#包括iostream
#包含列表
使用命名空间std
int main()
{
list int l；
返回0；
}
我们不会在这里演示其余部分。我们以前学习的时候用过，没必要浪费你的时间。
迭代器这里，我们最好先和大家分享一下迭代器。这里有四种迭代器，比如正向迭代器。在用法上没有什么新意。在这里，我们最好演示一个。
int main()
{
list int l(10，1)；
list int:iterator it=l . begin()；
而(它！=l.end())
{
cout * it“”；
它；
}
返回0；
}
Reverse()这是一个反转函数，就像我们之前实现的字符串反转一样。下面我们来看看。
#包括iostream
#包含列表
使用命名空间std
int main()
{
list int l；
for(int I=0；i 10我)
{
l . push _ back(I)；
}
l . reverse()；
for (int val : l)
{
cout val“”；
}
cout endl
返回0；
}
Sort()list他自己内置了一个排序函数，具体用法比较简单。先用一下，里面的比较器是给一个自定义类型的。我们以后再谈这个。
#包括iostream
#包含列表
#包含时间. h
使用命名空间std
int main()
{
srand((无符号int)time(NULL))；
list int l；
for(int I=0；i 20我)
{
int ret=rand()% 100；
l . push _ back(ret)；
}
for (int val : l)
{
cout val“”；
}
cout endl
l . sort()；
for (int val : l)
{
cout val“”；
}
cout endl
返回0；
}
list的排序函数性能有点低，我们一般不用。我会在这个博客上分享这个功能。
merge()merge(()的本质是合并两个有序链表。记住是有序的，也就是我们最好先把两个链表快照，再合并。
int main()
{
srand((无符号int)time(NULL))；
list int l1
list int l2
for(int I=0；i 20我)
{
int ret=rand()% 100；
L1 . push _ back(ret)；
}
for(int I=0；i 20我)
{
int ret=rand()% 100；
L2 . push _ back(ret)；
}
L1 . sort()；
L2 . sort()；
l1 .合并(L2)；
for (int val : l1)
{
cout val“”；
}
cout endl
返回0；
}
注意，当我们使用merge函数时，知道哪个参数最多的列表被清除就足够了。
int main()
{
srand((无符号int)time(NULL))；
list int l1
list int l2
for(int I=0；i 20我)
{
int ret=rand()% 100；
L1 . push _ back(ret)；
}
for(int I=0；i 20我)
{
int ret=rand()% 100；
L2 . push _ back(ret)；
}
L1 . sort()；
L2 . sort()；
l1 .合并(L2)；
cout L2 . size()endl；
返回0；
}
unique()函数是一个重复数据删除函数，但是我们仍然需要对列表进行排序。这里演示了简单的重复数据删除。看看这种无序的情况。这可以理解为我们只是去一个区域复制。
int main()
{
list int l；
l . push _ back(1)；
l . push _ back(1)；
l . push _ back(2)；
l . push _ back(1)；
l . push _ back(3)；
for (int val : l)
{
cout val“”；
}
cout endl
l . unique()；
for (int val : l)
{
cout val“”；
}
cout endl
返回0；
}
排序性能list中排序的本质是归并排序，list中的排序数据是一种浪费。我们在想一件事。STL中我们的算法库中不是有排序算法吗？为什么这里有一个内置列表？我们先来看看算法库。
#包含算法
int main()
{
srand((无符号int)time(NULL))；
list int l；
for(int I=0；i 20我)
{
int ret=rand()% 100；
l . push _ back(ret)；
}
for (int val : l)
{
cout val“”；
}
cout endl
std:sort(l.begin()，l . end())；
for (int val : l)
{
cout val“”；
}
cout endl
返回0；
}
迭代器分类我们发现了上面报道的一堆错误，这里就不要让大家多想了。我们可以在这里观察事物，我们称之为随机迭代器。这里我们有点困惑。迭代器还会分类吗？好像没见过面，主要是之前淡化了这个知识点。
我们来观察一下string和vector的迭代器类型，顺便把迭代器类型拿出来。
迭代器分类
单迭代器，双向迭代器，随机迭代器，单迭代器
先说这个迭代器。单迭代器只能，这个的stl对应下面几个。
双向迭代器
这里就不截图了，双向迭代器或者-，之类的东西还有很多，比如list，map，set。通常，如果底层物理结构不连续，就会出现这种情况。
随机迭代器
随机迭代器支持-、-和-。我们学的vector，string，加上后面要学的adapter deque，都是随机迭代器。
排序性能从这里可以看出，算法中的排序是随机迭代器，而我们的链表只是双向迭代器，不太合适。我们可以将随机迭代器传递给双向迭代器，反之亦然，这就是为什么我们的列表有内置排序。
我们需要测试sort的性能。在某种意义上，列表中的排序是无用的。我们先测试一下vector和list的排序比较。
int main()
{
srand((无符号int)time(NULL))；
const int N=1024 * 1024
list int l；
向量int v；
for(int I=0；I N；我)
{
int val=rand()；
l.push_back(瓦尔)；
v . push _ back(val)；
}
int begin 1=clock()；
l . sort()；
int end 1=clock()；
int begin 2=clock()；
std:sort(v.begin()、v . end())；
int end 2=clock()；
“cout”列表：“(end 1-begin 1)endl；
cout sort:“(end 2-begin 2)endl；
返回0；
}
我们发现，如果数据量小于1w，两个系统的性能相差不大，但是随着数据量的扩大，两个系统的差别越来越大。
我们再测试一次。如果我们按向量排序，然后在指南列表中去看他们的表现如何，你会发现我是按向量排序的，并对其进行了排名。我比你落后，那你是废物吗？
int main()
{
srand((无符号int)time(NULL))；
const int N=1024 * 1024
list int l1
list int l2
向量int v；
for(int I=0；I N；我)
{
int val=rand()；
L1 . push _ back(val)；
l2 .推回(val)；
}
//排序l1
int begin 1=clock()；
L1 . sort()；
int end 1=clock()；
//移动前排序
int begin 2=clock()；
五.储备(N)；
for (int val : l2)
{
v . push _ back(val)；
}
std:sort(v.begin()、v . end())；
//再填回去
L2 . clear()；
for (int val : v)
{
l2 .推回(val)；
}
int end 2=clock()；
“cout”列表：“(end 1-begin 1)endl；
cout vector:“(end 2-begin 2)endl；
返回0；
}
我们可以在这里看看迭代器的封装。之前我们都是用原生指针。本质原因是它们的物理空间是连续的。在这里，list并不是所谓的连续空间，它们可以一个一个地放置节点。那么-，就有问题了，所以这里需要把迭代器单独拿出来。
让我们先写简单的迭代器，然后再完善它。
模板类T
结构列表迭代器
{
typedef _list_node T节点；
typedef _ list _ iterator T self//这是必需的，我们稍后会对此进行修改。如果使用了tepdef，则只能修改这一个。
Node * _ node//我们给的是指针，节点的空间可能会大一些。
_list_iterator(Node* node)
:_node(节点)
{
}
};大家想想，所谓的或者——不就是当前指针的节点指向next或者prev吗？对应的迭代器对象不变，但是里面的内容变了。
int main()
{
list int l；
l . push _ back(1)；
l . push _ back(2)；
l . push _ back(3)；
l . push _ front(10)；
list int:iterator it=l . begin()；
而(它！=l.end())
{
cout it endl
它；
}
cout l . size()endl；
返回0；
}
迭代器实现的一般结构如下。我们将第一个元素视为开始，将标记位视为结束。这其中还是有一些原因的，不过会在后面的博客中分析，其中涉及到反向迭代器。
根据考试成绩分等级排列的投考者的名单
{
公共：
typedef _list_node T节点；
typedef _ list _ iterator T iterator；
公共：
列表()
{
//首先，新建一个头节点
_head=新节点；
_ head-_ next=_ head；
_ head-_ prev=_ head；
}
私人：
Node * _ head//哨兵位置
}
Begin() end()先实现常用的，后面const修改的危害需要单独讨论。
迭代器begin()
{
返回迭代器(_ head-_ next)；
}
迭代器结束()
{
返回迭代器(_ head)；
}
接线员！=operator==这里我们知道只是改变了迭代器中的指针，就不说细节了。我们来加==和！=超载吧。这个只需要比较里面的指针。
布尔运算符！=(const self t)常量
{
返回_节点！=t. _ node
}
布尔运算符==(常数self t)常数
{
回归！(*这个！=t)；
}
operator的意思是把里面的指针指向下一个地址，本质上没什么可看的。
//前面
self运算符()
{
_ node=_ node-_ next；
返回* this
}
//后部
自身运算符(整数)
{
self cur=* this//调用复制构造。
_ node=_ node-_ next；
返回cur
}
算子——既然都实现了，也相对容易。
//前面
自运算符-()
{
_ node=_ node-_ prev；
返回* this
}
//后部
自运算符-(整数)
{
self cur(* this)；
_ node=_ node-_ prev；
返回cur
}
操作员*在这里开始出现问题。这个操作符是解引用的，即获取节点中的数据。我们这里用T作为返回值，或者突破类域。这种突破类域的方法我们后面会讲。这是标准图书馆的惯例。
测试运算符*()
{
return _ node-_ data；
}
运算符——既然提出了解决方案，那就先把所有运算符都写在这里，然后我们再修改。运算符——是编译器优化，本来应该是(迭代器。_node- \_date)。
T*运算符-()
{
返回(_ node-_ data)；
}
测试迭代器现在我们可以看到迭代器是如何工作的。在这里，我们将测试这种情况。这里最大的问题是后两个。
先测试一下常用迭代器，但是后面的const迭代器有些问题。
int main()
{
bit:list int l；
l . push _ back(1)；
l . push _ back(2)；
l . push _ back(3)；
l . push _ back(4)；
l . push _ back(5)；
l . push _ back(6)；
l . push _ back(7)；
l . push _ front(10)；
bit:list int:iterator it=l . begin()；
而(它！=l.end())
{
cout * it endl
它；
}
返回0；
}
结构A
{
A(int a=0，int b=0)
{
a1=a；
a2=b；
}
int a1
int a2
};
int main()
{
bit:列出一个l；
l.push_back(A(1，2))；
l.push_back(A(1，2))；
l.push_back(A(1，2))；
bit:list A:iterator it=l . begin()；
而(它！=l.end())
{
cout it-a1 it-a2 endl；
它；
}
返回0；
}
现在我们已经确认了普通迭代器在正常使用，我们需要看看const修改的迭代器。这里我们有两种方法。第一种方法是我们重写一个类，但是这种方法反复做轮子。我们不推荐。先把另外两个暂时放在一边，先看看我们遇到的问题。
#include assert.h
命名空间位
{
////这是列表节点
模板类T
结构列表节点
{
_ list _ node T * _ next
_ list _ node T * _ prev
T _ data
//先看看构造函数要不要写
_list_node(const T t=T())
:_next(nullptr)
，_prev(nullptr)
,_数据(吨)
{
}
};
模板类T
结构列表迭代器
{
类型定义_列表_节点T节点；
typedef _ list _ iterator测试自身
Node * _ node
_list_iterator(Node* node)
:_node(节点)
{
}
//析构拷贝都不需要
布尔运算符==(常数自我测试)常数
{
回归！(*这个！=t)；
}
T*运算符-()
{
return _ node-_ data；
}
测试运算符*()
{
return _ node-_ data；
}
布尔运算符！=(const self t)常量
{
返回_节点！=t. _节点
}
//前置
自己运算符()
{
_ node=_ node-_ next；
返回*这个
}
自运算符-()
{
_ node=_ node-_ prev；
返回*这个
}
//后置
自身运算符（整数)
{
自我约束=*这
_ node=_ node-_ next；
返回坏蛋
}
自运算符-(整数)
{
self cur(* this)；
_ node=_ node-_ prev；
返回坏蛋
}
};
模板类T //这个就是一个模板
根据考试成绩分等级排列的投考者的名单
{
公共：
类型定义_列表_节点T节点；
typedef _ list _ iterator T iterator；
typedef _ list _ iterator const T const _ iterator；
//要有构造函数作为一个标记位
列表()
{
//首先新的一个头节点
_head=新节点；
_ head-_ next=_ head；
_ head-_ prev=_ head；
}
//插入不做说明的话我们插入节点的前面
迭代器插入（迭代器位置，常量值)
{
//记录迭代器对应的节点指针
Node* ppos=pos ._ node
节点*当前=新节点(val)；
//记录前一个节点
node * prev=ppos-_ prev；
cur-_ next=ppos；
ppos-_ prev=cur；
cur-_ prev=prev；
prev-_ next=cur；
返回迭代器(cur)；
}
无效推回(常量值)
{
insert(end()，val)；
}
//迭代器
迭代器开始()
{
返回迭代器(_ head-_ next)；
}
const_iterator begin() const
{
返回const _ iterator(_ head-_ next)；
}
const_iterator end() const
{
返回const _ iterator(_ head)；
}
迭代器结束()
{
返回迭代器(_ head)；
}
私人：
节点* _头
};
}
void func(const bit:list int l)
{
bit:list int:const _ iterator it=l . begin()；
而（它！=l.end())
{
cout * it结束
它；
}
}
int main()
{
bit:list int l；
我。push _ back(1)；
我。push _ back(2)；
我。push _ back(3)；
我。push _ back(4)；
我。push _ back(5)；
我。push _ back(6)；
我。push _ back(7)；
func(l)；
返回0;
}
我们学到了模板，这里的编译器报的错误就会变多了，这里我们看看高手是怎么控制的。高手给他们重新添加了一个模板，主要就是返回值作用。
模板类t，类裁判，类光电带读数机(photoelectric tape reader)
结构列表迭代器
{
类型定义_列表_节点T节点；
typedef _list_iterator T，Ref，Ptr self
Node * _ node
_list_iterator(Node* node)
:_node(节点)
{
}
布尔运算符==(常数自我测试)常数
{
回归！(*这个！=t)；
}
光电带读数机(photoelectric tape reader)操作员-()
{
return _ node-_ data；
}
引用运算符*()
{
return _ node-_ data；
}
};
根据考试成绩分等级排列的投考者的名单
{
公共：
类型定义_列表_节点T节点；
typedef _list_iterator T，T，T * iterator
typedef _list_iterator T，const T，const T * const _ iterator
}
这样就可以了。关于目录的迭代器我们到这里就放一段落，后面等我们谈过栈，在和大家谈反向迭代器
目录实现我们在C语言过程中学过部分数据结构，学了顺序表，也就是我们的向量，那么今天我们分享的本质就是链表，而且是带哨兵位的双向循环链表。我们先把这个节点给定义出来，一般这种节点我们都是用结构。
//这个是目录节点
模板类T
结构列表节点
{
_ list _ node T * _ next
_ list _ node T * _ prev
T _ data
//先看看构造函数要不要写
_list_node(const T t=T())
:_next(nullptr)
，_prev(nullptr)
,_数据(吨)
{
}
};
这里我们先把框架搭出来，我们最好把节点数据类型说明一下。
模板类T
根据考试成绩分等级排列的投考者的名单
{
公共：
类型定义_列表_节点T节点；
公共：
列表()
{
//首先新的一个头节点
_head=新节点；
_ head-_ next=_ head；
_ head-_ prev=_ head；
}
私人：
Node * _ head//哨兵位
};
Insert()让我们先实现insert。后面的尾插页和头插页可以重用这个代码，就不重复轮了。这里你不必关心迭代器。我们稍后将讨论这个迭代器包。你只需要记住迭代器里有一个节点指针，就是当前节点地址。这里的返回值是插入到元素中的第一个节点的迭代器。我是按照标准库来的。
迭代器插入(迭代器位置，常量值)
{
//记录迭代器对应的节点指针
Node* ppos=pos。_ node
Node* cur=新节点(val)；
//记录上一个节点
node * prev=ppos-_ prev；
cur-_ next=ppos；
ppos-_ prev=cur；
cur-_ prev=prev；
prev-_ next=cur；
返回迭代器(cur)；
}
重用push_back() push_front()代码即可。
void push_back(常量值)
{
insert(end()，val)；
}
void push_front(常量值)
{
insert(begin()，val)；
}
这个需要测试，这样才能证明之前的insrt是正确的。
int main()
{
bit:list int l；
l . push _ back(1)；
l . push _ back(2)；
l . push _ back(3)；
l . push _ back(4)；
l . push _ back(5)；
l . push _ back(6)；
l . push _ back(7)；
l . push _ front(10)；
bit:list int:iterator it=l . begin()；
而(它！=l.end())
{
cout * it“”；
它；
}
cout endl
返回0；
}
Erase()最后，我们将实现delete函数，其他函数将被忽略。主要是太简单，没有挑战性。如果你想看的话，我们后面会附上仓库的链接，里面实现的功能更多。
迭代器擦除(迭代器位置)
{
Node* ppos=pos。_ node
//无法删除标记位置。
断言(位置！=_ head)；
node * prev=ppos-_ prev；
node * next=ppos-_ next；
prev-_ next=next；
next-_ prev=prev；
删除ppos
返回迭代器(下一个)；
}
Pop_back() pop_front这里再用一下吧。
void pop_back()
{
erase(-end())；
}
void pop_front()
{
erase(begin())；
}
注意删除元素会导致迭代器失败。在这里，我们首先使用擦除测试。会有头删尾之类的问题，标准库中也有。
int main()
{
bit:list int l；
l . push _ back(1)；
l . push _ back(2)；
l . push _ back(3)；
l . push _ back(4)；
l . push _ back(5)；
l . push _ back(6)；
l . push _ back(7)；
l . push _ front(10)；
bit:list int:iterator it=l . begin()；
而(它！=l.end())
{
it=l . erase(it)；
}
cout l . size()endl；
返回0；
}
迭代器失败我们来测试一下list中迭代器失败的问题。这里很简单。我们先来看看insert。这个没有问题。
int main()
{
*国际清单；
l . push _ back(1)；
l . push _ back(2)；
l . push _ back(2)；
l . push _ back(4)；
l . push _ back(4)；
l . push _ back(6)；
l . push _ back(7)；
auto it=l . begin()；
而(它！=l.end())
{
if (*it % 2==0)
{
l.insert(it，* it * 10)；
}
它；
}
for (int val : l)
{
cout val“”；
}
返回0；
}
但是erase会变成迭代器失效的问题。我们很容易理解擦除。一般我们删除数据的时候，这个会变成一个野指针。
int main()
{
*国际清单；
l . push _ back(1)；
l . push _ back(2)；
l . push _ back(2)；
l . push _ back(4)；
l . push _ back(4)；
l . push _ back(6)；
l . push _ back(7)；
auto it=l . begin()；
l.erase(它)；
* it
返回0；
}
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。