list是什么? list本质上就是双向链表
相对与上一篇所讲的vector,我们知道双向链表有它自己的优点,首先空间利用比较灵活,所以省空间.
而且插入删除元素都是常数时间
下面将参照list的源码,将其分为下面几部分去讲
既然list是链表,那就必须得定义它自己的结点类
在源码中它的结点是这样子的
不像vector是连续的内存空间,所以可以直接用指针作为迭代器
在 list中由于是链式存储的,所以得定义一个属于自己的迭代器
直接看一些它的源码
可以看到在迭代器类中 有一个成员变量 node,用来存放该迭代器指向的结点,
可以通过构造函数给node指定指向的结点,
也可以给通过复制构造函数给node指定好另一个迭代器的node指向的结点.
由于list只支持双向迭代器(因为双向链表要支持前移 后移),所以对运算符 ,-- ,* ,->进行了重载.
注意 在list中插入结点和删除某个结点并不会使其他结点的迭代器失效,
而vector就并非如此,因为插入元素可能导致原有内存重新分配 导致原有迭代器失效
list是一个双向循环链表,既然是循环,也就是说尾结点的下一个就是头结点,头结点的上一个就是尾结点.
同时只要用一个结点指针指向了其中一个结点,就可以遍历到其他任意结点
在list中定义了一个空白的尾结点指针 用node表示 如下图表示
通过这个node,就可以表示出其他任意一个节点了,这样就可以实现我们的一些list的基本操作,
比如返回头结点(即返回node->next就可以了),返回尾结点(返回node本身就行了),返回头结点值,返回尾结点值,以及判空,返回长度
我们看一下在源码中是怎么实现的
4.1内存分配与释放
-
空间配置器list_node_allocator
list默认使用alloc作为空间配置器, 但是为了更方便的以结点大小为配置单位,
依据alloc定义了list_node_allocator作为专属空间配置器,每次配置一个节点大小
list_node_allocator(n)就表示配置n个结点空间大小
以该空间配置器为基础,主要通过下面四个函数来实现内存的分配与释放
-
开辟一个节点空间get_node()
-
释放一个结点空间put_node()
-
开辟一个结点空间并构造create_node()
-
释放一个结点空间并析构destory_node()
4.2内存使用
-
构造函数list()
-
push_back()
-
push_front()
-
erase()
-
pop_front()
-
pop_back()
-
clear
-
remove
-
unique
-
splice
-
merge
-
reverse
-
sort
list和queue与vector之间的区别
list不再能够像vector一样以普通指针作为迭代器，因为其节点不保证在存储空间中连续存在；
list插入操作和结合才做都不会造成原有的list迭代器失效;
list不仅是一个双向链表，而且还是一个环状双向链表，所以它只需要一个指针；
list不像vector那样有可能在空间不足时做重新配置、数据移动的操作，所以插入前的所有迭代器在插入操作之后都仍然有效；deque是一种双向开口的连续线性空间，所谓双向开口，意思是可以在头尾两端分别做元素的插入和删除操作；可以在头尾两端分别做元素的插入和删除操作；
deque和vector最大的差异，一在于deque允许常数时间内对起头端进行元素的插入或移除操作，二在于deque没有所谓容量概念，因为它是动态地以分段连续空间组合而成，随时可以增加一段新的空间并链接起来，deque没有所谓的空间保留功能。