【C++】第十二节—详解list（list的介绍和使用、模拟实现）_listc++
Hi，我是云边有个稻草人^(*￣(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的构造
（2）list iterator的使用
此处，大家可暂时将迭代器理解成一个指针，该指针指向list中的某个节点。
函数声明
【注意】
- begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
- rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动
（3）list capacity
（4）list element access
（5）list modifiers
【补充1】——push_back类和emplace_back类的区别
（这里涉及到前面几节所讲的拷贝构造，隐式类型转换，直接构造啥的，要是忘记了就，反正我是痛苦。复习回来啦，我爱C++）
int main(){list 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 lt1 = { -1,90,100,-8,34 };for (auto e : lt1){cout << e << \" \";}cout << endl;//排序sort，默认是升序，lesslt1.sort();for (auto e : lt1){cout << e << \" \";}cout <greater gt;//有名对象做实参，干脆直接用匿名对象:lt1.sort(greater());lt1.sort(gt);for (auto e : lt1){cout << e << \" \";}cout << endl;//对于vector，算法库里面有现成的sort，现在试用一下vector 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());//现在加入仿函数，> 是降序for (auto e : v1){cout << e << \" \";}cout << endl;//但是list就不可以使用算法库里面的sort，只能用STL里面的sort//sort(lt1.begin(), lt2.end(), greater());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 lt1;list lt2;vector 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 lt1;list lt2;for (size_t i = 0; i < N; i++){auto e = rand();lt1.push_back(e);lt2.push_back(e);}int begin1 = clock();//拷贝vectorvector 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#include#include#includeusing namespace std;int main(){list lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);lt1.push_back(5);list::iterator it1 = lt1.begin();while (it1 != lt1.end()){cout << *it1 << \" \";it1++;}cout << endl;list 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 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 lt1 = { 1,2,3,4,5 };for (auto e : lt1){cout << e << \" \";}cout <> 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 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 lt1 = { -1,90,100,-8,34 };for (auto e : lt1){cout << e << \" \";}cout << endl;//排序sort，默认是升序，lesslt1.sort();for (auto e : lt1){cout << e << \" \";}cout <greater gt;//有名对象做实参，干脆直接用匿名对象:lt1.sort(greater());lt1.sort(gt);for (auto e : lt1){cout << e << \" \";}cout << endl;//对于vector，算法库里面有现成的sort，现在试用一下vector 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());//现在加入仿函数，> 是降序for (auto e : v1){cout << e << \" \";}cout << endl;//但是list就不可以使用算法库里面的sort，只能用STL里面的sort//sort(lt1.begin(), lt2.end(), greater());return 0;}void test_op1(){srand((unsigned int)time(0));const int N = 1000000;list lt1;list lt2;vector 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 lt1;list lt2;for (size_t i = 0; i < N; i++){auto e = rand();lt1.push_back(e);lt2.push_back(e);}int begin1 = clock();//拷贝vectorvector 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模拟实现
- const 容器必须使用 const 迭代器进行遍历，const 迭代器不是迭代器本身不能修改而是迭代器指向的内容不能修改
2.1 模拟实现list
要模拟实现list，必须要熟悉list的底层结构以及其接口的含义，通过上面的学习，这些内容已基本掌握，现在我们来模拟实现list。
list.h
#pragma once#includenamespace bit{// 惯例// 全部都是公有，一般用structtemplatestruct list_node{T _data;list_node* _next;list_node* _prev;list_node(const T& x = T()):_data(x), _next(nullptr), _prev(nullptr){}};// typedef list_iterator iterator;// typedef list_iterator const_iterator;templatestruct list_iterator{typedef list_node Node;typedef list_iterator Self;Node* _node;list_iterator(Node* node):_node(node){}Ref operator*(){return _node->_data;}Ptr 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;}bool operator==(const Self& s){return _node == s._node;}};/*templatestruct list_const_iterator{typedef list_node Node;typedef list_const_iterator Self;Node* _node;list_const_iterator(Node* node):_node(node){}const T& operator*(){return _node->_data;}const 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;}};*/templateclass list{typedef list_node Node;public:/*typedef list_iterator iterator;typedef list_const_iterator const_iterator;*/typedef list_iterator iterator;typedef list_iterator const_iterator;iterator begin(){return iterator(_head->_next);}iterator end(){return iterator(_head);}const_iterator begin() const{return const_iterator(_head->_next);}const_iterator end() const{return const_iterator(_head);}void empty_init(){_head = new Node();_head->_next = _head;_head->_prev = _head;_size = 0;}list(){empty_init();}// lt2(lt1)list(const list& lt){empty_init();//引用，减少拷贝for (auto& e : lt){push_back(e);}}//对于类模版而言，类名不能代表类型要加上模版参数，在类里面的时候可以去掉模版参数// lt2 = lt3//list& operator=(list lt)list& operator=(list lt){swap(lt);return *this;}//清掉头结点+clear~list(){clear();delete _head;_head = nullptr;}void swap(list& tmp){std::swap(_head, tmp._head);std::swap(_size, tmp._size);}//清掉所有除头结点之外的节点void clear(){auto it = begin();while (it != end()){it = erase(it);}}list(size_t n, const T& val = T()){empty_init();for (size_t i = 0; i _prev;tail->_next = new_node;new_node->_prev = tail;new_node->_next = _head;_head->_prev = new_node;*/insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_front(){erase(begin());}void pop_back(){erase(--end());}//不会导致迭代器失效iterator insert(iterator pos, const T& val){Node* cur = pos._node;Node* newnode = new Node(val);Node* prev = cur->_prev;// prev newnode curprev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;++_size;return iterator(newnode);}//erase会导致迭代器失效iterator erase(iterator pos){assert(pos != end());Node* del = pos._node;Node* prev = del->_prev;Node* next = del->_next;prev->_next = next;next->_prev = prev;delete del;--_size;return iterator(next);}private:Node* _head;size_t _size;};template void swap(T& a, T& b){T c(a); a = b; b = c;}//bit::swap(i, j);//bit::swap(lt1, lt2);此时编译器会调用swap(list)更适配，但是内部调用的是list内部的swap//这里是全局提供专给list的swap，但是调用的是list容器内部的swap，就是为了防止误用template void swap(list& a, list& b){a.swap(b);}}运算符重载-> ,第一个->的结果是Pos*，第二个是找Pos这个结构体里面的_row。
list.cpp
#define _CRT_SECURE_NO_WARNINGS 1#include#include#include#includeusing namespace std;//int main()//{//list lt1;//lt1.push_back(1);//lt1.push_back(1);//lt1.push_back(1);//lt1.push_back(1);//lt1.emplace_back(10);////list lt2 = {1,2,3,4,5};////list::iterator it1 = lt1.begin();//while (it1 != lt1.end())//{//cout << *it1 << \" \";//++it1;//}//cout << endl;////for (auto e : lt2)//{//cout << e << \" \";//}//cout << endl;////return 0;//}class Pos{public:int _row;int _col;Pos(int row = 0, int col = 0):_row(row), _col(col){cout << \"Pos(int row, int col)\" << endl;}Pos(const Pos& p):_row(p._row), _col(p._col){cout << \"Pos(const Pos& p)\" << endl;}};//int main()//{//list lt;////// 构造+拷贝构造//Pos p1(1, 1);//lt.push_back(p1);//lt.push_back(Pos(2, 2));//lt.push_back({3,3});////lt.emplace_back(p1);//lt.emplace_back(Pos(2, 2));////lt.emplace_back({ 3,3 });////// 直接构造//lt.emplace_back(3, 3);////return 0;//}//int main()//{//list lt1 = { 1,2,3,4,5 };////for (auto e : lt1)//{//cout << e << \" \";//}//cout <> x;//auto it = find(lt1.begin(), lt1.end(), x);//if (it != lt1.end())//{//lt1.erase(it);//}////for (auto e : lt1)//{//cout << e << \" \";//}//cout << endl;////return 0;//}//int main()//{//list lt1 = { 1,2,3,4,5 };//// LRU//int x;////while (cin >> x)//{//auto pos = find(lt1.begin(), lt1.end(), x);//if (pos != lt1.end())//{//lt1.splice(lt1.begin(), lt1, pos);//}////for (auto e : lt1)//{//cout << e << \" \";//}//cout << endl;//}////cout << \"xxxxxxxxxxxxxxxxxxxxxx\" << endl;////return 0;//}//int main()//{//list lt1 = { 1,20,3,-4,5 };//for (auto e : lt1)//{//cout << e << \" \";//}//cout << endl;////// ///*greater gt;//lt1.sort(gt);*///lt1.sort(greater());////// 不能用////sort(lt1.begin(), lt1.end(), greater());//for (auto e : lt1)//{//cout << e << \" \";//}//cout << endl;////vector v1 = { 1,20,3,-4,5 };//for (auto e : v1)//{//cout << e << \" \";//}//cout << endl;//////sort(v1.begin(), v1.end());//sort(v1.begin(), v1.end(), greater());//for (auto e : v1)//{//cout << e << \" \";//}//cout << endl;//////return 0;//}void test_op1(){srand(time(0));const int N = 1000000;list lt1;list lt2;vector v;for (int i = 0; i < N; ++i){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();printf(\"vector sort:%d\\n\", end1 - begin1);printf(\"list sort:%d\\n\", end2 - begin2);}void test_op2(){srand(time(0));const int N = 1000000;list lt1;list lt2;for (int i = 0; i < N; ++i){auto e = rand();lt1.push_back(e);lt2.push_back(e);}int begin1 = clock();// 拷贝vectorvector 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();printf(\"list copy vector sort copy list sort:%d\\n\", end1 - begin1);printf(\"list sort:%d\\n\", end2 - begin2);}////int main()//{//test_op1();//test_op2();////return 0;//}#include\"List.h\"//int main()//{//bit::list lt1;//lt1.push_back(1);//lt1.push_back(1);//lt1.push_back(1);//lt1.push_back(1);////bit::list::iterator it1 = lt1.begin();//while (it1 != lt1.end())//{//*it1 = 2;////cout << *it1 << \" \";//++it1;//}//cout << endl;////for (auto e : lt1)//{//cout << e << \" \";//}//cout << endl;////bit::list lt2;//Pos p1(1, 1);//lt2.push_back(p1);//lt2.push_back(Pos(2, 2));//lt2.push_back({3,3});////bit::list::iterator it2 = lt2.begin();//while (it2 != lt2.end())//{////cout << (*it2)._row << \":\" << (*it2)._col <//cout <_row << \":\" <_col << endl;//cout <()->_row << \":\" <()->_col << endl;////++it2;//}//cout << endl;//}//int main()//{//const bit::list lt1(10, 1);////// const int* p1 //// int* const p2//bit::list::const_iterator it1 = lt1.begin();//while (it1 != lt1.end())//{////*it1 = 2;//cout << *it1 << \" \";//++it1;//}//cout << endl;////for (auto e : lt1)//{//cout << e << \" \";//}//cout << endl;////return 0;//}//int main()//{//bit::list lt1;//lt1.push_back(1);//lt1.push_back(2);//lt1.push_back(3);//lt1.push_back(4);//lt1.push_front(0);//lt1.push_front(-1);////bit::list::iterator it1 = lt1.begin();//while (it1 != lt1.end())//{//cout << *it1 << \" \";//++it1;//}//cout << endl;////lt1.pop_front();//lt1.pop_back();////for (auto e : lt1)//{//cout << e << \" \";//}//cout << endl;////bit::list lt2(lt1);//for (auto e : lt2)//{//cout << e << \" \";//}//cout << endl;////bit::list lt3(10, 1);//lt2 = lt3;//for (auto e : lt2)//{//cout << e << \" \";//}//cout << endl;//}int main(){bit::list lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);lt1.push_front(0);lt1.push_front(-1);bit::list lt2(10, 1);//lt1.swap(lt2);int i = 1, j = 2;bit::swap(i, j);bit::swap(lt1, lt2);for (auto e : lt1){cout << e << \" \";}cout << endl;for (auto e : lt2){cout << e << \" \";}cout << endl;return 0;}
list 结束！
完——
This Is Who I Am
—— Jackal
至此结束——
我是云边有个稻草人
期待与你的下一次相遇。。。。。。
