企业官网建设流程全解析

list的使用(常用)

本质:带头双向链表

Member functions

construct

voidtest01(){//默认构造list<int>lt1;//n个val构造list<int>lt2(10,1);//迭代器区间构造vector<int>v1={1,2,3,4,5,6};list<int>lt3(v1.begin(),v1.end());//拷贝构造list<int>lt4(lt3);//initializer_list(C++11语法)list<int>lt5={1,2,3,4,5};}

iterator

一个算法,不是所有的容器都可以使用,算法对迭代器是有一些要求
算法迭代器名字就是要求(暗示)

voidtest02(){//迭代器//1.封装:通用的,相似的遍历容器的方式,并且封装了容器底层,屏蔽容器结构的差异//2,通用/复用,实现算法时用迭代器函数模板方式实现,跟底层容器结构解耦list<int>lt1={1,2,3,4,5};list<int>::iterator it1=lt1.begin();while(it1!=lt1.end()){cout<<*it1<<' ';++it1;}cout<<endl;//范围forfor(autoe:lt1){cout<<e<<" ";}cout<<endl;//sort(迭代器理解)//list自己实现sort//效果没有vector好inta[]={0,-3,90,-8,88,55};sort(a,a+sizeof(a)/sizeof(int));for(autox:a){cout<<x<<" ";}cout<<endl;}

Modifiers

push_back

push_front

resize

Operations

voidtest04(){list<int>lt1={1,2,3,4,5};lt1.push_back(10);lt1.push_front(10);lt1.resize(20,9);list<int>lt2={1,20,13,-4,5};lt1.sort();//尽量少用lt2.reverse();lt2.sort();//merge之前两个容器都要先排好序lt1.merge(lt2);for(autoe:lt1){cout<<e<<" ";}cout<<endl;//去重lt1.unique();for(autoe:lt1){cout<<e<<" ";}cout<<endl;//removelt1.remove(5);for(autoe:lt1){cout<<e<<" ";}cout<<endl;}

以上省略一些使用接口,因为在使用时并不常用.
想要更多了解使用可查看官方文档:
(https://legacy.cplusplus.com/reference/list/list/)
此处的重点为list的模拟实现,实现的过程过结合list的源码可以带给我们更多感悟和启发,进一步加深我们对C++这一编程语言的两大特点(封装和面对对象)的理解.

list模拟实现

list.h

#define_CRT_SECURE_NO_WARNINGS#pragmaonce#include<iostream>usingnamespacestd;namespacemySTL{template<classT>structlist_node{T _data;list_node<T>*_next;list_node<T>*_prev;//全缺省构造list_node(constT&x=T()):_data(x),_next(nullptr),_prev(nullptr){}};////普通迭代器//template<class T>//struct _list_iterator//{// typedef list_node<T> Node;// Node* _node;// _list_iterator(Node* node)// :_node(node)// { }// //// T& operator*() {// return _node->_data;// }// _list_iterator<T> operator++() {// _node = _node->_next;// return *this;// }// _list_iterator<T> operator++(int) {// _list_iterator<T> tmp(*this);// _node = _node->_next;// return tmp;// }// _list_iterator<T> operator--() {// _node = _node->_prev;// return *this;// }// _list_iterator<T> operator--(int) {// _list_iterator<T> tmp(*this);// _node = _node->_prev;// return tmp;// }// bool operator!=(const _list_iterator<T>& it) {// return _node != it._node;// }// bool operator==(const _list_iterator<T>& it) {// return _node == it._node;// }////};////const迭代器//template<class T>//struct const_list_iterator//{// typedef list_node<T> Node;// Node* _node;// const_list_iterator(Node* node)// :_node(node)// {// }// //// const T& operator*() {// return _node->_data;// }// const_list_iterator<T> operator++() {// _node = _node->_next;// return *this;// }// const_list_iterator<T> operator++(int) {// const_list_iterator<T> tmp(*this);// _node = _node->_next;// return tmp;// }// const_list_iterator<T> operator--() {// _node = _node->_prev;// return *this;// }// const_list_iterator<T> operator--(int) {// const_list_iterator<T> tmp(*this);// _node = _node->_prev;// return tmp;// }// bool operator!=(const _list_iterator<T>& it) {// return _node != it._node;// }// bool operator==(const _list_iterator<T>& it){// return _node == it._node;// }//};//最终迭代器实现template<classT,classRef,classPtr>struct_list_iterator{typedeflist_node<T>Node;Node*_node;_list_iterator(Node*node):_node(node){}//Ref&operator*(){return_node->_data;}_list_iterator<T,Ref,Ptr>operator++(){_node=_node->_next;return*this;}_list_iterator<T,Ref,Ptr>operator++(int){_list_iterator<T,Ref,Ptr>tmp(*this);_node=_node->_next;returntmp;}_list_iterator<T,Ref,Ptr>operator--(){_node=_node->_prev;return*this;}_list_iterator<T,Ref,Ptr>operator--(int){_list_iterator<T,Ref,Ptr>tmp(*this);_node=_node->_prev;returntmp;}booloperator!=(const_list_iterator<T,Ref,Ptr>&it){return_node!=it._node;}booloperator==(const_list_iterator<T,Ref,Ptr>&it){return_node==it._node;}Ptroperator->(){return&_node->_data;}};template<classT>classlist{public:typedeflist_node<T>Node;typedef_list_iterator<T,T&,T*>iterator;//不行const修饰迭代器本身,不能实现++//typedef const _list_iterator<T> iterator;typedef_list_iterator<T,constT&,constT*>const_iterator;//同一个类模板实例化的两个类型iteratorbegin(){returniterator(_head->_next);}iteratorend(){returniterator(_head);}const_iteratorbegin()const{returnconst_iterator(_head->_next);}const_iteratorend()const{returnconst_iterator(_head);}list(){_head=newNode;_head->_next=_head;_head->_prev=_head;}//insert(在pos前面插入)iteratorinsert(iterator pos,constT&val){Node*cur=pos._node;Node*pre=cur->_prev;// 先把原来的前驱存下来Node*newnode=newNode(val);newnode->_prev=pre;newnode->_next=cur;pre->_next=newnode;cur->_prev=newnode;returniterator(newnode);}//eraseiteratorerase(iterator pos){Node*cur=pos._node;Node*prev=pos._node->_prev;Node*next=pos._node->_next;prev->_next=next;next->_prev=prev;deletecur;returniterator(next);}//析构~list(){iterator _it=begin();while(_it!=end()){_it=erase(_it);}//等价于cleardelete_head;_head=nullptr;}//push_back/*void push_back(const T& val) { Node* newnode = new Node(val); Node* tail = _head->_prev; newnode->_next = _head; newnode->_prev = tail; tail->_next = newnode; _head->_prev = newnode; }*/voidpush_back(constT&val){insert(end(),val);}voidpush_front(constT&val){insert(begin(),val);}voidpop_back(){erase(--end());}voidpop_front(){erase(begin());}//clearvoidclear(){iterator it=begin();while(it!=end()){it=erase(it);}}//深拷贝list(constlist<T>&lt){_head=newNode;_head->_next=_head;_head->_prev=_head;for(constauto&e:lt){push_back(e);}}//list(initializer_list<T>il){_head=newNode;_head->_next=_head;_head->_prev=_head;for(constauto&e:il){push_back(e);}}//lt1=lt2/*list<T>& operator=(const list<T>& lt) { if (this != &lt) { clear(); for (const auto& e : il) { push_back(e); } } return *this; }*/voidswap(list<T>&lt){std::swap(_head,lt._head);}list<T>&operator=(constlist<T>&lt){swap(lt);return*this;}//sizesize_tsize()const{size_t n=0;for(auto&e:*this){++n;}returnn;}private:Node*_head;};}

test.h

#define_CRT_SECURE_NO_WARNINGS#include"list.h"namespacemySTL{voidtest01(){list<int>lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);list<int>::iterator it=lt1.begin();while(it!=lt1.end()){cout<<*it<<" ";++it;}cout<<endl;}structPos{int_row;int_col;Pos(introw=0,intcol=0):_row(row),_col(col){}};voidtest02(){list<Pos>lt1;//隐式类型转换lt1.push_back({2,2});lt1.push_back({3,3});lt1.push_back({4,4});auto_it=lt1.begin();lt1.insert(_it,{1,1});for(auto&e:lt1){cout<<e._row<<":"<<e._col<<endl;}lt1.push_back({9,9});lt1.push_front({8,8});for(autoit=lt1.begin();it!=lt1.end();++it){cout<<it->_row<<":"<<it->_col<<endl;}lt1.pop_back();for(autoit=lt1.begin();it!=lt1.end();++it){cout<<it->_row<<":"<<it->_col<<endl;}}template<classT>voidprint(constlist<T>&lt){// 类模板未实例化，不能去类模板中找后面的东西// 编译器就分不清const_iterator是嵌套内类，还是静态成员变量// typename告诉编译器，我确认过了这里是类型//typename list<T>::const_iterator it = lt.begin();autoit=lt.begin();while(it!=lt.end()){//*it += 1;cout<<*it<<" ";++it;}cout<<endl;}}intmain(){//mySTL::test01();mySTL::test02();return0;}