【C++】第十二节——详解list（上）—（list的介绍和使用、模拟实现）
Hi，我是云边有个稻草人，一个偶尔中二的C++方向在学博主^(*￣(oo)￣)^，与你分享所学知识
C++—本节课所属专栏—持续更新中—欢迎订阅！
目录
一、list的介绍和使用
1.1 list的介绍—带头双向循环链表
1.2 list的使用
（1）list的构造
（2）list iterator的使用
（3）list capacity
（4）list element access
（5）list modifiers
【补充1】——push_back类和emplace_back类的区别
【补充2】vector和list使用sort的区别
【vector下和list下sort性能的区别—Release】
1.3 关于上面list的使用所写的全部代码
二、list模拟实现
2.1 模拟实现list
list.h
list.cpp
正文开始——
一、list的介绍和使用
1.1 list的介绍—带头双向循环链表
list - C++ Reference—list文档介绍
1.2 list的使用
list中的接口比较多，此处类似，只需要掌握如何正确的使用，然后再去深入研究背后的原理，已达到可扩展的能力。以下为list中一些常见的重要接口。
（1）list的构造
| 构造函数 | 接口说明 |
|---|---|
| list (size_type n, const value_type& val = value_type()) | 构造的list中包含n个值为val的元素 |
| list() | 构造空的list |
| list (const list& x) | 拷贝构造函数 |
| list (InputIterator first, InputIterator last) | 用[first, last)区间中的元素构造 list |
（2）list iterator的使用
此处，大家可暂时将迭代器理解成一个指针，该指针指向list中的某个节点。
| 函数声明 | 接口说明 |
|---|---|
| begin()+end() | 返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器 |
| rbegin()+rend() | 返回第一个元素的reverse_iterator,即end位置，返回最后一个元素下一个位 置的reverse_iterator,即begin位置 |
【注意】
- begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
- rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动
（3）list capacity
| 函数说明 | 接口说明 |
|---|---|
| empty | 检测list是否为空，是返回true，否则返回false |
| size | 返回list中有效节点的个数 |
（4）list element access
| 函数说明 | 接口说明 |
|---|---|
| front | 返回list的第一个节点中值的引用 |
| back | 返回list的最后一个节点中值的引用 |
（5）list 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中的有效元素 |
【补充1】——push_back类和emplace_back类的区别
（这里涉及到前面几节所讲的拷贝构造，隐式类型转换，直接构造啥的，要是忘记了就，反正我是痛苦。复习回来啦，我爱C++）
int main()
{list<Pos> lt;Pos p1(1, 1);//构造+拷贝构造lt.push_back(p1);//有名对象，先创建一个对象，再将对象进行push_backlt.push_back(Pos(2, 2));//匿名对象lt.push_back({ 2,2 });//隐式类型转换lt.emplace_back(p1);//那是一个模版，传一个Pos类型的对象，模版参数推出形参的类型为Poslt.emplace_back(Pos(2,2));//对于匿名对象，emplace_back的模版参数也可以推导出为Pos类型//lt.emplace_back({ 2,2 });//直接构造lt.emplace_back(3, 3);//但是可以支持这样玩，直接将初始化pos的值给它传过去return 0;
}- 下面的拷贝构造，是将形参的pos拷贝构造到链表中的节点里面
- lt.push_back({1,1});//本质是隐式类型转换—>这里也是构造+拷贝构造（隐式类型转换，实参传给形参，先用(1,1)构造一个临时对象，形参引用的是临时对象，这种场景下就解释了为什么形参的部分要加上const，因为它引用的临时对象具有常性！）
- lt.emplace_back(1, 1);//不仅仅可以传pos类型的对象，也可以传构造链表里面pos的参数直接最后去构造pos，所以形参也叫可变模版参数
所以相比于push_back，emplace_back的高效之处仅在于直接构造的那种情况！
【补充2】vector和list使用sort的区别
int main()
{list<int> lt1 = { -1,90,100,-8,34 };for (auto e : lt1){cout << e << " ";}cout << endl;//排序sort，默认是升序，lesslt1.sort();for (auto e : lt1){cout << e << " ";}cout << endl;//排降序 >greater<int> gt;//有名对象做实参，干脆直接用匿名对象:lt1.sort(greater<int>());lt1.sort(gt);for (auto e : lt1){cout << e << " ";}cout << endl;//对于vector，算法库里面有现成的sort，现在试用一下vector<int> v1 = { 1,3,-2,90,9 };for (auto e : v1){cout << e << " ";}cout << endl;//默认是升序//sort(v1.begin(), v1.end());sort(v1.begin(), v1.end(), greater<int>());//现在加入仿函数，> 是降序for (auto e : v1){cout << e << " ";}cout << endl;//但是list就不可以使用算法库里面的sort，只能用STL里面的sort//sort(lt1.begin(), lt2.end(), greater<int>());return 0;
}运行结果见下：
（vector的sort底层是递归，算法库里面的sort底层是归并）
【vector下和list下sort性能的区别—Release】
下面是在Release下，对vector使用算法库里面的sort和list使用自己实现的sort各自效率的测试
void test_op1()
{srand((unsigned int)time(0));const int N = 1000000;list<int> lt1;list<int> lt2;vector<int> v;for (int i = 0; i < N; i++){auto e = rand() + i;lt1.push_back(e);v.push_back(e);}int begin1 = clock();//排序,用算法库里面的sort给vector排序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;}void test_op2()
{srand((unsigned int)time(0));const int N = 1000000;list<int> lt1;list<int> lt2;for (size_t i = 0; i < N; i++){auto e = rand();lt1.push_back(e);lt2.push_back(e);}int begin1 = clock();//拷贝vectorvector<int> v(lt2.begin(), lt2.end());//用迭代器区间进行构造sort(v.begin(), v.end());//拷贝回lt2lt2.assign(v.begin(), v.end());int end1 = clock();int begin2 = clock();lt1.sort();int end2 = clock();cout << "vector sort(copy):" << end1 - begin1 << endl;cout << "list sort:" << end2 - begin2 << endl;
}int main()
{test_op1();test_op2();return 0;
}运行结果如下：显而易，要排序的话最好使用vector，vector排序的效率更高！
list中还有一些操作，需要用到时大家可参阅list的文档说明。
1.3 关于上面list的使用所写的全部代码
#include<iostream>
#include<list>
#include<vector>
#include<algorithm>using namespace std;int main()
{list<int> lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);lt1.push_back(5);list<int>::iterator it1 = lt1.begin();while (it1 != lt1.end()){cout << *it1 << " ";it1++;}cout << endl;list<int> lt2 = { 1,2,3,4,5,6 };for (auto e : lt2){cout << e << " ";}cout << endl;return 0;
}class Pos
{int _row;int _col;public:Pos(int row, int col):_row(row), _col(col){ }
};int main()
{list<Pos> lt;Pos p1(1, 1);//构造+拷贝构造lt.push_back(p1);//有名对象，先创建一个对象，再将对象进行push_backlt.push_back(Pos(2, 2));//匿名对象lt.push_back({ 2,2 });//隐式类型转换lt.emplace_back(p1);//那是一个模版，传一个Pos类型的对象，模版参数推出形参的类型为Poslt.emplace_back(Pos(2,2));//对于匿名对象，emplace_back的模版参数也可以推导出为Pos类型//lt.emplace_back({ 2,2 });//直接构造lt.emplace_back(3, 3);return 0;
}int main()
{list<int> lt1 = { 1,2,3,4,5 };for (auto e : lt1){cout << e << " ";}cout << endl;int x;cin >> x;auto it = find(lt1.begin(), lt1.end(), x);if (it != lt1.end()){lt1.erase(it);}for (auto e : lt1){cout << e << " ";}cout << endl;//逆置lt1.reverse();for (auto e : lt1){cout << e << " ";}cout << endl;return 0;
}int main()
{list<int> lt1 = { 1,2,3,4,5,6 };//LRU最近最少用,将最近最少使用的调到前面去int x;while (cin >> x){auto pos = find(lt1.begin(), lt1.end(), x);//直接调用算法库里面的findlt1.splice(lt1.begin(), lt1, pos);//学会查看文档学习这些接口的用法for (auto e : lt1){cout << e << " ";}cout << endl;}return 0;
}int main()
{list<int> lt1 = { -1,90,100,-8,34 };for (auto e : lt1){cout << e << " ";}cout << endl;//排序sort，默认是升序，lesslt1.sort();for (auto e : lt1){cout << e << " ";}cout << endl;//排降序 >greater<int> gt;//有名对象做实参，干脆直接用匿名对象:lt1.sort(greater<int>());lt1.sort(gt);for (auto e : lt1){cout << e << " ";}cout << endl;//对于vector，算法库里面有现成的sort，现在试用一下vector<int> v1 = { 1,3,-2,90,9 };for (auto e : v1){cout << e << " ";}cout << endl;//默认是升序//sort(v1.begin(), v1.end());sort(v1.begin(), v1.end(), greater<int>());//现在加入仿函数，> 是降序for (auto e : v1){cout << e << " ";}cout << endl;//但是list就不可以使用算法库里面的sort，只能用STL里面的sort//sort(lt1.begin(), lt2.end(), greater<int>());return 0;
}void test_op1()
{srand((unsigned int)time(0));const int N = 1000000;list<int> lt1;list<int> lt2;vector<int> v;for (int i = 0; i < N; i++){auto e = rand() + i;lt1.push_back(e);v.push_back(e);}int begin1 = clock();//排序,用算法库里面的sort给vector排序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;}void test_op2()
{srand((unsigned int)time(0));const int N = 1000000;list<int> lt1;list<int> lt2;for (size_t i = 0; i < N; i++){auto e = rand();lt1.push_back(e);lt2.push_back(e);}int begin1 = clock();//拷贝vectorvector<int> v(lt2.begin(), lt2.end());//用迭代器区间进行构造sort(v.begin(), v.end());//拷贝回lt2lt2.assign(v.begin(), v.end());int end1 = clock();int begin2 = clock();lt1.sort();int end2 = clock();cout << "vector sort(copy):" << end1 - begin1 << endl;cout << "list sort:" << end2 - begin2 << endl;
}int main()
{test_op1();test_op2();return 0;
}二、list模拟实现
2.1 模拟实现list
要模拟实现list，必须要熟悉list的底层结构以及其接口的含义，通过上面的学习，这些内容已基本掌握，现在我们来模拟实现list。
list.h
#pragma oncenamespace lrq
{//模版//定义list里面结点的结构//虽然struct是全公开的，但是我们在使用list这个容器的接口的时候感受不到这些底层，//也不知道这些变量的命名，这其实也算一种隐形的封装template<class T>struct list_node{T _data;list_node<T>* _next;list_node<T>* _prev;//初始化list_node(const T& x = T())//构造函数写成全缺省的，无参的和有参的都可以用:_data(x), _next(nullptr), _prev(nullptr){ }};template<class T>struct list_iterator{typedef list_node Node;typedef list_iterator<T> Self;Node* _node;//类封装结点指针，重载运算符，模拟指针的行为list_iterator<T>(Node* node):_node(node){ }T& operator* (){return _node->data;}T* operator->(){//返回的是这个数据的地址return &_node->_data;}Self& operator++(){_node = _node->_next;return *this;}Self& operator--(){_node = _node->_prev;return *this;}Self operator++(int){Self tmp(*this);_node = _node->_next;return _tmp;}Self operator--(int){Self tmp(*this);_node = _node->_prev;return _tmp;}bool operator!=(const Self& s){return _node!= !=s._node();}};//class和struct的区别是什么？没有用访问限定符修饰的，struct是共有的，class是私有的//惯例：如果一个类既有公有也有私有就用class，全部是公有默认用structtemplate<class T>class list{typedef list_node<T> Node;//定义成类里面的typedef，和全局的typedef的区别是，//类里面的typedef中Node受访问限定符的限制，外部不能随意访问Nodepublic:typedef list_iterator<T> iterator;void empty_init(){_head = new Node();_head->_next = _head;_head->_prev = _head;}iterator begin(){return iterator(_head->_next);}iterator end(){return iterator(_head);}//无参的构造函数list(){empty_init();}void push_back(const T& x){Node* new_node = new Node(x);Node* tail = _head->_prev;tail->_next = new_node;new_node->_prev = tail;new_node->_next = _head;_head->_prev = new_node;}private:Node* _head;//哨兵位头结点};}运算符重载-> ,第一个->的结果是Pos*，第二个是找Pos这个结构体里面的_row。
list.cpp
#include<iostream>
#include"list.h"using namespace std;//class Pos
//{
// int _row;
// int _col;
//
//public:
// Pos(int row, int col)
// {
// _row = row;
// _col = col;
// }
//};//int main()
//{
// list<int> lt1;
//
// lt1.push_back(1);
// lt1.push_back(2);
// lt1.push_back(3);
// lt1.push_back(4);
//
// list<int>::iterator it1 = lt1.begin();
// //迭代器
// while (it1 != lt1.end())
// {
// cout << *it1 << " ";
// it1++;
// }
//
// //范围for
// for (auto e : lt1)
// {
// cout << e << " ";
// }
//
// cout << endl;
//
// Pos pos(1, 1);//调用有参的构造函数
// list<Pos> lt;
// lt.push_back(pos);//有名对象
// lt.push_back(Pos(1,1));//匿名对象
// lt.push_back({1,1});//本质是隐式类型转换
//
// lt.emplace_back(pos);
// lt.emplace_back(Pos(1, 1));
// lt.emplace_back(1, 1);//用两个形参直接构造节点里面的pos// return 0;
//}//int main()
//{
// list<int> lt1 = { 1,2,3,4,5 };
//
// int x;
//
// while (cin >> x)
// {
//
// auto e = find(lt1.begin(), lt1.end(), x);
// lt1.splice(lt1.begin(), lt1, e);
//
// for (auto e : lt1)
// {
// cout << e << " ";
// }
// cout << endl;
// }
//
//
// return 0;
//}//int main()
//{
// list<int> lt = { 90,199,3,4,78 ,-9};
//
// for (auto e : lt)
// {
// cout << e << " ";
// }
//
// cout << endl;
//
// greater<int> gt;
// //lt.sort(gt);
// lt.sort(greater<int>());//传匿名对象，类型名+（）
//
// lt.sort();//默认排升序 <
//
// for (auto e : lt)
// {
// cout << e << " ";
// }
//
// cout << endl;
//
// return 0;
//}int main()
{lrq::list<int> lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);lt1.push_back(5);lrq::list<int>::literator it1 = lt1.begin();while (it1 != lt1.end()){//*it1 = 2;也可以写数据cout << *it1 << " ";++it1;}cout << endl;for (auto e : lt1){cout << e << " ";}cout << endl;return 0;
}完——
今天就到这里，剩下的list明天继续，我猜我明天还会更新list博客
This Is Who I Am
—— Jackal
至此结束——
我是云边有个稻草人
期待与你的下一次相遇。。。。。。