一、list是什么
list的底层结构是带头双向循环链表。
相较于 vector 的连续线性空间，list 就显得复杂很多，它是由一个个结点构成，每个结点申请的空间并不是连续的，它的好处是每次插入或删除一个数据，就配置或释放一个元素空间，我们不用在意扩容问题了，也不用单独写扩容函数了，list对于任何位置的元素进行插入或者元素移除，时间复杂度都是O(1)，它的缺点是不支持随机访问，即通过下标直接访问对应元素，这是由于它的底层是链表，链表中的结点在空间上分配是不连续的。
二、list容器的基本使用
1、构造函数
这里的allocator是空间配置器，我们这里先不用管它(认为它不存在)，等到后面的篇章会具体讲解它的作用。 其中，(1)是默认构造 (2)是n个val构造 (3)是迭代器区间构造 (4)是拷贝构造。
2、析构函数
释放每个结点申请的空间资源。
3、赋值重载
它的操作数是两个已有的list对象。
4、迭代器
(1)使用
list的迭代器和vector的迭代器在用法上一模一样。
使用迭代器可以进行遍历：
#include <iostream>
#include <list>
using 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_back(5);list<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;
}int main()
{test_list1();return 0;
}运行结果：
支持迭代器，就支持范围for，因为范围for的底层就是迭代器。
void test_list1()
{list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);for (auto e : lt){cout << e << " ";}cout << endl;
}int main()
{test_list1();return 0;
}运行结果：
(2)分类
迭代器从功能上进行分类，分为iterator、const_iterator、reverse_iterator、const_reverse_iterator这四类，它还可以从性质上进行分类，分为单向迭代器、双向迭代器、随机迭代器。
单向迭代器包括(forward)：forward_list / unordered_map... 它只支持++
双向迭代器(bidirectional)包括：list / map / set... 它只支持++ / --
随机迭代器(random access)包括：vector / string / deque... 它支持++ / -- / + / -
它们的底层结构决定它们的性质，它们的底层结构也决定它们可以使用哪些算法。
比如：
C++标准库中sort的模板参数是RandomAccessIterator，从它的名字中可以看出它只接收随机迭代器，如果传一个单向迭代器，它也可以接收，但运行时会发生错误即程序不能正常运行。
C++标准库中reverse的模板参数是BidirectionalIterator，从它的名字中可以看出它只接收双向迭代器，如果传一个单向迭代器，它也可以接收，但运行时会发生错误即程序不能正常运行。如果传一个随机迭代器，也可以正常使用，因为随机迭代器的范围更广，凡是支持单向迭代器或者双向迭代器的都支持随即迭代器。
出现InputIterator，说明单向/双向/随机迭代器都可以使用这个函数。
5、成员函数
(1)empty()
判断容器内节点个数是否为空，若为空返回true，否则返回false。
(2)size()
返回容器内节点个数。
(3)front()
reference 就是list<T>中的T，T是模板参数。front就是用来返回第一个结点的值。
(4)back()
返回最后一个结点的值。
(5)assign()
用于赋值。(1)是用一段迭代区间赋值 (2)是用n个val赋值
(6)push_front()
头插，头部插入一个新结点。
(7)pop_front()
头删，删除头部的结点。
(8)push_back()
尾插，尾部插入一个新结点。
(9)pop_back()
尾删，删除尾部的结点。
(10)emplace_back()
它的功能和push_back()差不多，但有不同之处，现阶段我们就把它当作push_back()使用。
struct AA
{AA(int a1, int a2):_a1(a1), _a2(a2){}
private:int _a1;int _a2;
};void test_list2()
{list<AA> lt;AA aa1(1, 1);lt.push_back(aa1);lt.push_back(AA(2,2));//lt.push_back(3,3); //err，这里会报错lt.emplace_back(aa1);lt.emplace_back(AA(2,2));lt.emplace_back(3,3); //ok,与push_back()的不同之处，它支持直接传构造A对象的参数
}int main()
{test_list2();return 0;
}(10)insert()
(1)是在pos位置前插入val (2)是在pos位置前插入n个val (3)是在pos位置前插入一段迭代区间。
void test_list3()
{list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);for (auto e : lt)cout << e << " ";cout << endl;//在第3个位置前(整体位置是从0开始编号的)插入30//lt.insert(lt.begin() + 3, 30); //list容器不支持+,所以这行代码会报错list<int>::iterator it = lt.begin();int k = 3;while (k--){++it;//list容器支持++,所以这行代码会报错}lt.insert(it, 30); //(1)for (auto e : lt)cout << e << " ";cout << endl;
}int main()
{test_list3();return 0;
}运行结果：
(11)erase()
(1)删除pos位置上的值 (2)删除一段迭代区间
void test_list4()
{list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);for (auto e : lt)cout << e << " ";cout << endl;int x;cin >> x;list<int>::iterator it = find(lt.begin(),lt.end(),x);if (it != lt.end()) //找到了lt.erase(it); //(1)elsecout << "不存在:" << x << endl;for (auto e : lt)cout << e << " ";cout << endl;}int main()
{test_list4();return 0;
}输入4，运行结果：
(12)clear()
清空所有结点数据。
(13)resize()
将结点个数更新到n，假设原先节点个数为k。
1、k > n
释放k - n个结点
2、k < n
增加n - k个节点，结点中的内容自己可以传，也可以不传，用默认的缺省值。
因为list的底层是链表，所以没有扩容这一说法。
(14)reverse()
逆置结点的顺序。
void test_list5()
{list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);for (auto e : lt)cout << e << " ";cout << endl;lt.reverse();for (auto e : lt)cout << e << " ";cout << endl;//reverse(lt.begin(),lt.end()); //这里的算法库中的reverse也支持list容器的逆置
}int main()
{test_list5();return 0;
}运行结果：
(15)sort()
由于算法库中的sort不支持list容器的迭代器，所以这里它自己实现了一个。
void test_list6()
{list<int> lt;lt.push_back(20);lt.push_back(40);lt.push_back(50);lt.push_back(30);lt.push_back(10);for (auto e : lt)cout << e << " ";cout << endl;//默认排升序lt.sort(); //(1)for (auto e : lt)cout << e << " ";cout << endl;}int main()
{test_list6();return 0;
}运行结果：
如果想要排降序，就要借助仿函数：
void test_list6()
{list<int> lt;lt.push_back(20);lt.push_back(40);lt.push_back(50);lt.push_back(30);lt.push_back(10);for (auto e : lt)cout << e << " ";cout << endl;//排降序greater<int> gt;lt.sort(gt);for (auto e : lt)cout << e << " ";cout << endl;}int main()
{test_list6();return 0;
}运行结果：
(16)merge()
合并两个链表，前提是这两个链表需要有序。
void test_list7()
{list<int> first, second;first.push_back(3);first.push_back(6);first.push_back(1);second.push_back(2);second.push_back(5);second.push_back(4);first.sort();second.sort();first.merge(second); //合并后，second这个链表就空了，相当于将它移到first上了for (auto e : first)cout << e << " ";cout << endl;cout << "----------" << endl;for (auto e : second) //second中已经没有数据了cout << e << " ";cout << endl;cout << "----------" << endl;
}int main()
{test_list7();return 0;
}运行结果：
(17)unique()
去重，删除容器中与val值一样的结点，只保留第一个。删除时要保证重复的数据紧挨着，否则会删不干净，建议删除前先排序。
void test_list8()
{list<int> lt;lt.push_back(5);lt.push_back(1);lt.push_back(4);lt.push_back(2);lt.push_back(4);lt.push_back(3);lt.push_back(3);lt.push_back(5);for (auto e : lt)cout << e << " ";cout << endl;lt.sort();lt.unique();for (auto e : lt)cout << e << " ";cout << endl;
}int main()
{test_list8();return 0;
}运行结果：
(18)remove()
对val进行查找，如果找到就删除，否则什么也不做。
(19)remove_if()
给定一个条件，如果满足就删除，否则什么也不做。
(20)splice()
(1)是将x中全部结点转移到当前容器中的pos位置之前的位置处 (2)是将x中i位置的结点转移到当前容器中的pos位置之前的位置处 (3)是将x中的一段迭代区间上的结点转移到当前容器中的pos位置之前的位置处
//将一个链表的结点转移给另一个链表
void test_list9()
{list<int> mylist1, mylist2;list<int>::iterator it;//先插入一些值for (int i = 1; i <= 4; ++i)mylist1.push_back(i); // mylist1: 1 2 3 4for (int i = 1; i <= 3; ++i)mylist2.push_back(i * 10); // mylist2: 10 20 30cout << "初始值：" << endl;for (auto e : mylist1)cout << e << " ";cout << endl;for (auto e : mylist2)cout << e << " ";cout << endl;cout << "---------------" << endl;it = mylist1.begin();++it; mylist1.splice(it, mylist2); //(1)// mylist1: 1 10 20 30 2 3 4// mylist2中的数据已经没有了// "it" 仍然指向2 cout << "第一次调用splice后：" << endl;for (auto e : mylist1)cout << e << " ";cout << endl;for (auto e : mylist2)cout << e << " ";cout << endl;cout << "---------------" << endl;mylist2.splice(mylist2.begin(), mylist1, it); //(2)// mylist1: 1 10 20 30 3 4// mylist2: 2// "it"现在是无效的cout << "第二次调用splice后：" << endl;for (auto e : mylist1)cout << e << " ";cout << endl;for (auto e : mylist2)cout << e << " ";cout << endl;cout << "---------------" << endl;
}int main()
{test_list9();return 0;
}运行结果：
根据它的功能，我们还可以调整当前链表的结点顺序：
//调整当前链表结点的顺序
void test_list10()
{list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);lt.push_back(6);cout << "转移前:" << endl;for (auto e : lt)cout << e << " ";cout << endl;//现要求将6这个结点转移到1这个结点的前面去lt.splice(lt.begin(), lt, --lt.end());cout << "转移后:" << endl;for (auto e : lt)cout << e << " ";cout << endl;
}int main()
{test_list10();return 0;
}三、排序效率
这里我们将list容器中的sort与算法库中的sort进行效率对比，看看哪个更优。
(1)对比一
#include <vector>
#include <iostream>
#include <algorithm>
#include <list>
using namespace std;void test_op1()
{srand((unsigned int)time(0));const int N = 1000000;list<int> lt1;vector<int> v;for (int i = 0;i < N;++i) //随机生成100万个数据{auto e = rand() + i;lt1.push_back(e);v.push_back(e);}int begin1 = clock();sort(v.begin(), v.end());int end1 = clock();int begin2 = clock();lt1.sort();int end2 = clock();cout << "vector sort:" << end1 - begin1 << endl;cout << "list sort:" << end2 - begin2 << endl;
}int main()
{test_op1();return 0;
}在Debug环境下的运行结果：
可以看到list排序优势更大，那是因为在Debug环境下，优化不是很大，运行结果不具有参考价值，在release环境下，双方优化都是最大的，这才公平。
在Realse环境下运行结果：
实际上，算法库中的sort效率是更好的。
(2)对比二
#include <vector>
#include <iostream>
#include <algorithm>
#include <list>
using namespace std;void test_op2()
{srand((unsigned int)time(0));const int N = 1000000;list<int> lt1;list<int> lt2;for (int i = 0;i < N;++i){auto e = rand() + i;lt1.push_back(e);lt2.push_back(e);}int begin1 = clock();vector<int> v(lt2.begin(), lt2.end()); //迭代器区间构造sort(v.begin(), v.end()); //用算法库中的sort进行排序lt2.assign(v.begin(), v.end()); //再拷贝回lt2int end1 = clock();int begin2 = clock();lt1.sort(); //直接调用list中的sort进行排序int end2 = clock();cout << "list copy vector sort copy list sort:" << end1 - begin1 << endl;cout << "list sort:" << end2 - begin2 << endl;
}int main()
{test_op2();return 0;
}在Release环境下运行结果：
这差距就出来了， 在begin1~end1这段时间内做的事情比begin2~end2这段时间内做的还要多，结果花费的时间还少，说明了当数据量比较大时，list中的sort排序效率很低。不如先把它的值拷贝给vector容器，然后排序，排完再拷贝回来。
四、结语
本篇内容到这里就结束了，主要讲了list容器的基本使用，希望对大家有些许收获，祝大家天天开心！