list的介绍及使用

【写在前面】

在学完 list，大家对 STL 中的迭代器的认知会进一步提高。list 用的虽然不多，但是它的底层有很多经典的东西，尤其是它的迭代器。list 的结构对我们来说应该问题不大，因为在《数据结构》时我们就已经了解过链表了，它的结构是一个带头双向循环链表，之前我们也实现过。

对于 list 没有 reserve 和 resize，因为它的底层不是连续的空间，它是用一个申请一个，不用一个就释放一个。也没有 operator[]，因为它不支持随机访问。同时它有头插、头删、尾插、尾删、任意位置的插入、删除。因为 list 是带头双向循环链表。

有了前面 string 和 vector 的铺垫，我们这里对于 list 的使用就大概过一下即可，因为它们比较类似，重点主要放在 list 的深度剖析及模拟实现。

其实来严格来说 C++ 的 list 有两个：

1. <list> 是带头双向循环链表，是我们本章需要学习的知识
2. <forward_list> 是单链表，它是 C++11 所增加的，它的使用场景一点也不多，查看文档，可以看到它不支持尾插、尾删，因为对于单链表效率很低。并且它的任意位置插入、删除是在当前位置之后，因为当前位置之前得找前一个，也是一个 O(N) 的实现。单链表对比双向链表的唯一优势就是每个节点少存一个指针。
   

一、list的介绍及使用

list的介绍

list的文档介绍

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

list的使用

1、list的构造

constructor	接口说明
list()	构造空的 list
list(size_type n, const value_type& val = value_type())	构造 list 中包含 n 个值为 val 的元素
list(const list& x)	拷贝构造函数
list(InputIterator first, InputIterator last)	用 (first, last) 区间中的元素构造 list

#include<iostream>#include<vector>#include<list>using namespace std;namespace std{	void test_list1()	{		list<int> lt1;		list<int> lt2(10, 5);		list<int> lt3(lt2.begin(), lt2.end());		//同样支持用其它容器的迭代器区间去构造,因为它是模板,并且它可以支持如下写法		vector<int> v = { 1, 2, 3, 4, 5 };		list<int> lt4(v.begin(), v.end());			list<int> lt5(lt4);	}}int main(){	std::test_list1();	return 0;	}

2、list iterator的使用

iterator	接口说明
begin + end	返回第一个元素的迭代器 + 返回最后一个元素下一个位置的迭代器
rbegin + rend	返回第一个元素的 reserve_iterator，即 end 位置，返回最后一个元素下一个位置的 reverse_iterator，即 begin 位置

#include<iostream>#include<vector>#include<list>using namespace std;namespace std{	void test_list1()	{		vector<int> v = { 1, 2, 3, 4, 5 };		list<int> lt(v.begin(), v.end());				list<int>::iterator it1 = lt.begin();		//注意对于string和vector我们可以用小于或不等于做为判断条件,但是list只能用不等于做为判断条件,这时因为不同的容器中空间连续与否的原因		while(it1 != lt.end())		{			cout << *it1 << " ";			++it1;			}		cout << endl;				list<int>::reverse_iterator it2 = lt.rbegin();		while(it2 != lt.rend())		{			cout << *it2 << " ";			++it2;			}		cout << endl;			//list里已经不再支持operator[]		for(auto e : lt)		{			cout << e << " ";		}		cout << endl;	}}int main(){	std::test_list1();	return 0;	}

3、list capacity

capacity	接口说明
empty	检测 list 是否为空，是返回 true，否则返回 false
size	返回 list 中有效节点的个数

4、list element access

element access	接口说明
front	返回 list 的第一个节点的中值的引用
back	返回 list 的最后一个节点中值的引用

5、list modifiers

modifiers	接口说明
push_front	在 list 首元素前插入值为 val 的元素
pop_front	删除 list 中第一个元素
push_back	在 list 尾部插入值为 val 的元素
pop_back	删除 list 中最后一个元素
insert	在 list position 位置中插入值为 val 的元素
erase	删除 list position 位置的元素
swap	交换两个 list 中的元素
clear	清空 list 中的有效元素

#include<iostream>#include<algorithm>#include<vector>#include<list>#include<functional>#include<time.h>using namespace std;namespace std{	void test_list1()	{		list<int> lt;		lt.push_back(1);		lt.push_back(2);		lt.push_back(3);		lt.push_back(4);			lt.push_front(10);		lt.push_front(20);		lt.push_front(30);		lt.push_front(40);			for(auto e : lt)		{			cout << e << " ";			}		cout << endl;			lt.pop_back();		lt.pop_back();		lt.pop_back();		lt.pop_back();				lt.pop_front();		lt.pop_front();		lt.pop_front();		lt.pop_front();		//lt.pop_front();//err,注意在头删、尾删时要保证list里还有数据,否则这里会报断言错误				for(auto e : lt)		{			cout << e << " ";			}	}	void test_list2()	{		list<int> lt;		lt.push_back(1);		lt.push_back(2);		lt.push_back(3);		lt.push_back(4);				//list里也没有提供find,所以这里使用algorithm里的		list<int>::iterator pos = find(lt.begin(), lt.end(), 2);		if(pos != lt.end())		{			lt.insert(pos, 20);		}		for (auto e : lt)		{			cout << e << " ";		}		cout << endl;				//clear并不会把头节点清除,这里还可以继续push_back		lt.clear();		lt.push_back(1);		lt.push_back(2);		lt.push_back(3);		lt.push_back(4);		for(auto e : lt)		{			cout << e << " ";			}		cout << endl;	}	void test_list3()	{		list<int> lt1;		lt1.push_back(1);		lt1.push_back(2);		list<int> lt2;		lt2.push_back(2);		lt2.push_back(1);					list<int> lt3;		lt3.push_back(5);		lt3.push_back(1);		lt3.push_back(3);		lt3.push_back(3);		//对于swap,在C++98中建议使用容器里的,而不建议使用算法里的。它们效果一样,但是效率不一样,具体见如下说明		lt1.swap(lt2);		//swap(lt1, lt2);		for(auto e : lt1)		{			cout << e << " ";			}		cout << endl;		for(auto e : lt2)		{			cout << e << " ";			}		cout << endl;			//注意所有的排序都满足,>是降序,<是升序,这里默认是升序		//这个也是一个类模板,它是一个仿函数,所在头<functional>后面我们会实现,sort所在头<algorithm>		/*greater<int> g; lt3.sort(g);*/		lt3.sort(greater<int>());//同上,可以直接写成匿名对象		for(auto e : lt3)		{			cout << e << " ";			}		cout << endl;		//unique的功能是去重,所在头<algorithm>,去重的前提是排序,升序降序都行,如果不排序它只去去相邻的数据		lt3.unique();		for(auto e : lt3)		{			cout << e << " ";			}		cout << endl;				//erase需要先find,而remove可以直接删除,有就全删,没有就不删,所在头<algorithm>		lt3.remove(3);		for (auto e : lt3)		{			cout << e << " ";		}		cout << endl;			//reverse的功能是逆置,对于带头双向循环链表的逆置比单链表简单的多,所在头<algorithm>		lt3.reverse();		for (auto e : lt3)		{			cout << e << " ";		}		cout << endl;		//merge的功能是合并		//splice的功能是转移,它转移的是节点不是数据,很特殊的场景下才会使用到,我们以后在了解LRU可能还会再接触到	}	void test_OP()	{		srand(time(0));		const int N = 10000;		list<int> lt;		vector<int> v;				v.resize(N);		for (int i = 0; i < N; i++)		{			v[i] = rand();			lt.push_back(v[i]);		}		int begin1 = clock();		sort(v.begin(), v.end());//vector用算法里的,它底层使用的是快排的三数取中法		int end1 = clock();		int begin2 = clock();		lt.sort();//list用容器里的		//sort(lt.begin(), lt.end());//err,本质sort会用两个迭代器相减,而list的迭代器不支持减		int end2 = clock();					cout << "vector sort：" << end1 - begin1 << endl;		cout << "list sort：" << end2 - begin2 << endl;	}}int main(){	std::test_list1();	std::test_list2();	std::test_list3();	std::test_OP();	return 0;	}

说明

1. List item

   为什么 C++98 建议使用各自容器里的 swap，而不建议使用算法里的 swap

   如下可以看到算法里 swap 的 C++98 的实现，无论是 string、vector、list 使用它会涉及深拷贝问题，而且这里的深拷贝代价极大，需要深拷贝 3 次 —— 当 lt1 和 lt2 交换，这里会把 lt1 拷贝构造一份 c，然后把 lt2 赋值于 lt1，c 赋值于 lt2，完成交换。

   而如果是容器里的 swap，需要交换 lt1 和 lt2，只需要头指针交换即可。假设是 vector，只要把 lt1 和 lt2 对应的 _start、_finish、_endofstorage 交换即可。相比算法里的 C++98 里的 swap，这里可以认为没有任何代价。

   所以说，我们为什么在以后工作中多数不会去写数据结构，而还要学《数据结构》这门学科。因为如果你没有自己去实现数据结构，你不了解链表的结构，我跟你说这 2 个 swap 有深拷贝差异，你可能都听不懂，没有学过《数据结构》的人永远不能理解为什么 top-k 问题用了堆好像效率就高很多。所以我们从 C 语言一路走来，各种各样的模拟实现(小的有 strstr、strcmp；大的有二叉树、list)，其实不是为了造更好的轮子，而是能更好的理解并高效的使用。
   

2. List item

   迭代器补充

   容器迭代器的分类：

   a) 使用功能的角度可分为，(正向、反向) + const

   b) 容器底层结构的角度可分为，单向、双向、随机

     比如单链表迭代器、哈希表迭代器就是单向，特征是能 ++，不能 --；双向链表迭代器、map 迭代器就是双向，特征是能 ++、–；string、vector、deque 迭代器就是随机迭代器，特征是能 ++、–、+、-，一般随机迭代器底层都是一个连续的空间。

   可以看到算法里的 sort、reverse 的声明，它的模板参数的命名不是 T，也不是 iterator，对于模板参数的命名可以任意，但是它的命名是有含意的。比如说你要用 sort 这个算法，你要用的是随机迭代器；你要用 reverse 这个算法，你要用的是双向迭代器。随机迭代器也可以使用 reverse，因为随机迭代器是一个双向迭代器，因为它满足双向迭代器的所有功能；同理，双向迭代器也是单向迭代器、随机迭代器也是单向迭代器。也就意味着这里模板参数的命令是单向迭代器，那么你的容器可以是单向、双向、随机；模板参数的命令是双向迭代器，那么你的容器可以是双向、随机；模板参数的命令是随机迭代器，那么你的容器可以是随机。后面学了继承，就可以知道它们满足一个继承关系。
   
   所以这里要明白一个关系
   

6、list迭代器失效

前面说过，此处大家可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点无效，即该节点被删除了。因为 list 的底层结构为带头结点的双向循环链表，因此在 list 中进行插入时是不会导致 list 的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。

#include<iostream>#include<algorithm>#include<list>using namespace std;namespace std{	void test_list1()	{		int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };		list<int> lt(array, array + sizeof(array) / sizeof(array[0]));		list<int>::iterator pos = find(lt.begin(), lt.end(), 5);		if(pos != lt.end())		{			//不会失效			lt.insert(pos, 45);		}		for(auto e : lt)		{			cout << e << " ";			}		cout << endl;	}	void test_list2()	{		int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };		list<int> lt(array, array + sizeof(array) / sizeof(array[0]));		list<int>::iterator pos = find(lt.begin(), lt.end(), 5);		if(pos != lt.end())		{			//会失效,可以重新指定迭代器pos			lt.erase(pos);			//pos = lt.erase(pos);//ok		}		cout << *pos << endl;		cout << endl;	}}int main(){	std::test_list1();	std::test_list2();	return 0;	}

说明