前言

老样子我们还是通过list - C++ Reference (cplusplus.com)这个文档来介绍我们的list.

我们先来简单的介绍一下我们的list,我们的list是一个带头循环双向链表,这样的链表结构十分优秀.

如下图:

而forward_list是单链表,他们相似但是list能向前向后遍历而forward_list只能向后遍历

list文档介绍

1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代
2. ist的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素
3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效
4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好
5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)

可以看到我们的list是通过模板实现的,参数模板T是我们list存储的类型元素,Alloc是内存池用于分配的工具.

list的名称定义

对list中出现的参数名称的解释

list的构造

list的构造函数我还是直接演示使用.

代码如下：

void test1()
{
	list<int> l1;//第一个
	list<int> l2(5,10);//第二个
	list<int> l3(20);//第二个
	list<int> l4(l2.begin(), l2.end());//第三个
	list<int> l5(l3);//拷贝构造
	for (auto e : l1)
	{
		cout << e << " ";
	}
	cout << endl;
	for (auto e : l2)
	{
		cout << e << " ";
	}
	cout << endl;
	for (auto e : l3)
	{
		cout << e << " ";
	}
	cout << endl;
	for (auto e : l4)
	{
		cout << e << " ";
	}
	cout << endl;
	for (auto e : l5)
	{
		cout << e << " ";
	}
	cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

经历的vector和string的学习之后我们对于list的学习应该是轻车熟路了,所以博主就加快一些进度.

list的迭代器

同样我们可以吧list的迭代器当作指针来使用,但是因为list是链表的原因,我们其实并不能真的使用指针来当作list的迭代器,所以list的迭代器也应该是一个新的类来模拟指针的实现.

可以看到我们的list的迭代器其实一共就重载了前置后置++ -- * -> == !=而我们从stl的源码库中其实也是可以看到只有上述几种的操作符重载;

stl库如下图:

这里也可以看到我们的list其实是由迭代器类节点类和list类一起组成.

常用接口

容量接口

几乎类似

• empty是判空
• size是返回容器元素的个数.
• max_size是能存储的最大值.

元素接口

• front返回第一个元素的引用
• back返回最后一个元素的引用

修改接口

• assign 分配一个新空间给之前的list

• push_front 向第一个位置前插入一个新元素

• pop_front 删除第一个位置的元素

• push_back 尾插

• pop_back 尾删

• insert 向某位置插入数据

  

  insert的使用他会在pos前的位置插入数据,然后返回插入数据位置(第一个).

  第二个insert也是在pos前插入,但是是插入的n个val值

  第三个insert类似也是在pos前的位置插入值,插入first到last的区间元素.

• earse 删除位置数据

  

  第一个: 删除pos位置的数据并返回下一元素的指针位置.(一定要接收不然会导致迭代器失效)

  第二个: 删除first到last区间的元素(左闭右开式删除).返回删除区间后的第一个元素.

• swap交换元素及把所有元素交换

  

• resize void resize (size_type n, value_type val = value_type());和vector等相同

• clear 清空所有元素(头节点不删除).

操作接口

• sort 其实也不算常用接口,因为sort是直接对链表进行的排序操作所有效率很低甚至不如把list的元素拿出来排序然后再塞回去
• reverse 开辟空间