C++ --- list

前言

C++容器中的list是双向带头循环链表，其整体结构请翻看我之前的数据结构专题中的list篇章，本篇文章着重list的使用。

一、构造

1.默认构造

	// 默认构造list<int> lt1;

调试观察：

2.n个val构造

	// n个val构造list<int> lt2(10, 2);

调试观察：

对于list链表，VS编译器对于监视窗口对象内容的显示做出了一些调整，让其看起来和vector的表现形式相似，易于我们观察，而链表实际的底层结构是由一个一个的链表“串”起来的。

3.初始化列表构造

	// 初始化列表构造list<int> lt3 = { 1,2,3,4,5,6,7,8,9,10 };

调试窗口：

4.迭代器区间构造

	// 迭代器区间构造 --- 底层是模板，所以可以传不同类型的迭代器区间vector<int> v = { 10,9,8,7,6,5,4,3,2,1 };list<int> lt4(v.begin(), v.end());list<int> lt5(lt3.begin(), lt3.end());// 数组也是可以作为迭代器区间构造int a[] = { 10,20,30,40,50,60,70,80,90,100 };list<int> lt6(a, a + 10);   // 数组名就是数组首元素的地址

这里就不再贴出监视窗口了，构造情况后上述对象差不多。

5.拷贝构造

	// 拷贝构造list<int> lt7(lt6);

二、迭代器

迭代器功能本身就是模拟指向数组的指针，所以在上文迭代器构造处出现了使用数组构造list对象。

这里要引出迭代器的类型，学习了string，vector ，其实它们的迭代器都有自己的类型的，一共有5种类型：输入，输出，单向，双向，随机迭代器，就目前自身学习进度而言，所学容器中string，vector是随机迭代器，list是双向迭代器，forward_list（单链表）是单向迭代器。

以上5种迭代器类型的关系是：
Input iterator < - - forward iterator < - - bidirectional iterator < - - random access iterator。越靠后迭代器所实现的功能就越多。
output iterator是单独的一种。
比如Input迭代器能够实现读取，前置/后置++，比较，一次读写；forward迭代器在前项迭代器的基础上多出多次读写；bidirectional迭代器又多了前置/后置- -；random access迭代器多了算术运算+/-，下标访问，关系比较。
output迭代器只实现写入，前置/后置++。

迭代器的类型决定了某些容器能否使用某些算法。
例如：
算法库中sort算法所传的参数类型是一个随机迭代器，所以此算法list容器是不能使用的，

所以以后在使用算法库中的算法时，要知道算法其参数类型，正确使用迭代器。

list的迭代器实现就不实现了，使用方式和之前string，vector文章一模一样，这里就不再赘述。

三、常用方法

1.尾插

即push_back方法，在链表最后一个节点后插入一个节点。

	list<int> lt1 = { 1,2,3,4,5,6,7,8,9,10 };// (1)尾插lt1.push_back(999);

运行：

2.头插

即push_front方法，在链表第一个有效节点之前插入节点。

	// (2)头插lt1.push_front(999);

运行：

3.尾删

即pop_back方法，删除链表最后一个节点。

	// (3)尾删lt1.pop_back();

运行：

4.头删

即pop_frontf方法，删除链表中第一个有效节点。

	// (4)头删lt1.pop_front();

运行：

5.赋值

即assign方法，可以给空对象进行赋值，也可以给有值对象进行赋值。本身有三个重载，可以传迭代器区间，n个val，initializer_list。

	// (5)赋值,assignlist<int> lt2;    // 空对象lt2.assign(lt1.begin(), lt1.end());        // 迭代器区间lt2.assign(10,0);                          // n个vallt2.assign({ 9,8,7,6,5,4,3,2,1 });         // initializer_list// 有值对象lt1.assign(lt2.begin(), lt2.end());

监视观察：

lt1通过assign方法，由原来的1，2，3，4，5，6，7，8，9变成了9，8，7，6，5，4，3，2，1；lt2通过assign方法，也变成了9，8，7，6，5，4，3，2，1。

6.pos位置插入

即insert方法，需配合find方法找到目标位置，再在此位置上插入值。

	list<int> lt2;    // 空对象lt2.assign({ 9,8,7,6,5,4,3,2,1 });      // (6)pos位置插入，insert// 此方法需要配合着find方法使用auto pos = find(lt2.begin(), lt2.end(), 9);lt2.insert(pos, 100);for (auto e : lt2){cout << e << " ";}cout << endl;

运行：

7.pos位置删除

即erase方法，需配合find方法找到目标位置，再删除在此位置上的值。

	// (7)pos位置删除，erase// 此方法需要配合着find方法使用auto pos = find(lt2.begin(), lt2.end(), 9);lt2.erase(pos);for (auto e : lt2){cout << e << " ";}cout << endl;

运行：

8.交换

即swap方法，交换两个链表。

	// (8)交换，swaplist<int> lt3(10, 0);list<int> lt4(10, 9);lt3.swap(lt4);

监视观察：

9.扩容或缩容

即resize方法，扩容操作时即 n > size ，后续扩容至n，并填充给定val值；缩容操作时即 n < size ，后续缩容至n。

	// (9)扩容或者缩容，resize// 当给定值 n > size 时：扩容至n，并填充给定val值list<int> lt5 = { 1,2,3,4,5,6,7,8,9 };lt5.resize(15, 77);// 当给定值 n < size 时：缩容至nlist<int> lt6 = { 1,2,3,4,5,6,7,8,9 };lt6.resize(5);

监视观察：

9.清空

即clear方法，清空链表数据。

	// (10)清空，clearlt6.clear();

监视观察：

9.获取首 / 尾元素

即front / back方法，获取链表中的首 / 尾元素。

	// (11)front,back// 获取首尾元素cout << lt5.front() << " ";cout << lt5.back() << " ";

运行：

9.计算容器大小

即size方法，计算容器的大小。

	// (12)计算容器大小，sizelt5.size();

10.判空

即empty方法，判断容器是否为空，若为空则返回true(1)，反之返回false(0)。

	// (13)判空，empty// 容器为空，返回true即1，反之返回false即0lt6.empty();

四、算法

1.逆置

list所带的reverse方法仅供list使用，但是在算法库中的reverse方法的参数迭代器类型是双向迭代器，表明list容器是可以使用此算法的。

即单向迭代器类型的容器使用不了此算法。

	// (1)逆置，reverselist<int> lt1 = { 1,2,3,4,5,6,7,8,9,10 };lt1.reverse();// 算法库// reverse(lt1.begin(),lt1.end());for (auto e : lt1){cout << e << " ";}cout << endl;

运行：

2.排序

算法库里的sort参数迭代器类型是随机迭代器，所以list是不能使用算法库里面的sort。

即list内部实现了一个sort。

	// (2)排序，sortlist<int> lt2 = { 2,3,5,1,7,8,5,10,7,4 };lt2.sort();for (auto e : lt2){cout << e << " ";}cout << endl;

运行：

但是这两个sort还是有一些差别的，算法库的底层是用快速排序实现的，而list中的是用归并排序实现的，尽管两者的时间复杂度都为O(n logn)，在面对不同结构数据的排序时，算法库的sort更好一点。
当排序相同数据量的数据时，拿vector和list举例，对于vector来说，底层数组是物理地址连续的内存空间，在计算机硬件层面访问内存中的数据并不是直接去访问内存，而是会先到一个叫缓存的地方去找数据，缓存里面的数据是内存数据的一小部分拷贝，若在缓存中找到此数据，则表示命中，反之表示不命中，在物理地址连续的内存空间，缓存读取内存中的数据不是只读一个数据，而是读取一串数据，就算是第一个数据未命中，若后续有数据命中，也大大提高了缓存的命中率和读取效率；
反观list，底层是一个一个节点，也就是物理地址不连续的内存空间，而这个不连续就会导致每次缓存去内存读取数据时只能一个节点一个节点般的读取，无法读取一串数据，导致缓存的命中率和读取效率都不如vector来的高，也就会导致排序时间增加，当数据量越大，此差距就会越明显。

总结，数据量小的时候可以使用list自带的sort，当数据量特别大的时候，依旧使用算法库的sort(list可以转化为vector再进行排序)。

3.合并

即merge方法，合并就是将一个链表的节点全部连接到目标链表中，即会改变链表的size大小，并且前提是两个链表都要有序。

	// (3)合并，merge// 使用前提两个链表要有序,并且效果是被合并链表中的节点依次拿给将要合并的链表list<int> lt3 = { 1,5,9,7,3 };list<int> lt4 = { 10,8,4,2,6 };lt3.sort();lt4.sort();lt3.merge(lt4);          // lt3就有10个元素，lt4一个元素也没有了

监视观察：

4.去重

即unique方法，会将链表中的所有重复元素只保留到一个。

	// (4)去重，uniquelist<int> lt5 = { 1,2,2,2,2,2,3,4,5 };lt5.unique();

监视观察：

5.删除指定元素

即remove方法，删除指定元素。

	// (5)删除指定元素，remove// 还有一个remove_if，也就是满足条件再删除list<int> lt6 = { 1,2,3,4,5,6,7,100 };lt6.remove(100);

监视观察：

6.粘结，拼接

即splice方法，在两个对象间使用，就是将一个链表的节点拼接到另一个链表的pos位置处，此使用方法会改变size大小；对自身使用可以移动链表指定pos元素的位置，此使用方法不会改变size大小。

	// (6)粘结/拼接，splice// 可以在两个对象间使用，也可以在自身对象使用list<int> lt7 = { 10,20,30 };list<int> lt8(3,0);lt7.splice(lt7.begin(), lt8);        // 此时lt7有六个元素，lt8为空list<int> lt9 = { 1,2,3,4,5,6,7,8,9,10 };auto pos = find(lt9.begin(), lt9.end(), 5);lt9.splice(lt9.begin(), lt9, pos);   // 此时就是pos节点变动到链表首

监视观察：

对两个对象使用：

对自身使用：