目录一、 list的使用1.1 list的构造1.2 list iterator的使用1.3 list capacity1.4 list element access1.5 list modifiers1.6 list的迭代器失效二、list的模拟实现三、反向迭代器的实现四、list与vector的对比一、 list的使用1.1 list的构造构造函数 (constructor)接口说明list (size_type n, const value_type val value_type())构造的list中包含n个值为val的元素list()构造空的listlist (const list x)拷贝构造函数list (InputIterator first, InputIterator last)用[first, last)区间中的元素构造list1.2 list iterator的使用此处大家可暂时将迭代器理解成一个指针该指针指向list中的某个节点。【注意】begin与end为正向迭代器对迭代器执行操作迭代器向后移动rbegin(end)与rend(begin)为反向迭代器对迭代器执行操作迭代器向前移动1.3 list capacity1.4 list element access1.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.6 list的迭代器失效前面说过此处大家可将迭代器暂时理解成类似于指针迭代器失效即迭代器所指向的节点的无效即该节点被删除了。因为list的底层结构为带头结点的双向循环链表因此在list中进行插入时是不会导致list的迭代器失效的只有在删除时才会失效并且失效的只是指向被删除节点的迭代器其他迭代器不会受到影响。举例代码voidTestListIterator1(){intarray[]{1,2,3,4,5,6,7,8,9,0};listintl(array,arraysizeof(array)/sizeof(array[0]));autoitl.begin();while(it!l.end()){// erase()函数执行后it所指向的节点已被删除因此it无效在下一次使用it时必须先给其赋值 l.erase(it);it;}}// 改正voidTestListIterator(){intarray[]{1,2,3,4,5,6,7,8,9,0};listintl(array,arraysizeof(array)/sizeof(array[0]));autoitl.begin();while(it!l.end()){l.erase(it);// it l.erase(it);}}二、list的模拟实现#define_CRT_SECURE_NO_WARNINGS1#pragmaonce#includeiostream#includeassert.h#includereverse_iterator.husing namespace std;namespace sk{//构造链表templateclass TstructListNode{ListNode(constTvalT()):_prev(nullptr),_next(nullptr),_val(val){}ListNodeT*_prev;ListNodeT*_next;T _val;};//list迭代器封装templateclass T,class Ref,class Ptrclass __list_iterator{typedefListNodeTNode;typedef__list_iteratorT,Ref,PtrSelf;public:Node*_node;__list_iterator(Node*x):_node(x){}Ref operator*(){return_node-_val;}Ptr operator-(){return(_node-_val);}Selfoperator(){_node_node-_next;return*this;}Self operator(int){Selftmp(*this);_node_node-_next;returntmp;}Self operator--(){_node_node-_prev;return*this;}Self operator--(int){Selftmp(*this);_node_node-_prev;returntmp;}bool operator!(constSelfit)const{return_node!it._node;}bool operator(constSelfit)const{return_nodeit._node;}};//list功能实现templateclass Tclass list{typedefListNodeTNode;public:typedef__list_iteratorT,T,T*iterator;typedef__list_iteratorT,constT,constT*const_iterator;typedefreverse_iteratorconst_iterator,constT,constT*const_reverse_iterator;typedefreverse_iteratoriterator,T,T*reverse_iterator;reverse_iteratorrbegin(){returnreverse_iterator(end());}reverse_iteratorrend(){returnreverse_iterator(begin());}const_reverse_iteratorrbegin()const{returnconst_reverse_iterator(end());}const_reverse_iteratorrend()const{returnconst_reverse_iterator(begin());}iteratorbegin(){returniterator(_head-_next);}iteratorend(){returniterator(_head);}const_iteratorbegin()const{returnconst_iterator(_head-_next);}const_iteratorend()const{returnconst_iterator(_head);}list():_head(nullptr){empty_initiablize();}//深拷贝list(intn,constTvalT()){empty_initiablize();for(size_ti0;in;i){push_back(val);}}templateclass Inputiteratorlist(Inputiterator first,Inputiterator last){empty_initiablize();while(first!last){push_back(*first);first;}}list(constlistTl){empty_initiablize();listTtmp(l.begin(),l.end());swap(_head,tmp._head);}listToperator(listTl){swap(_head,l._head);return*this;}//析构~list(){clear();delete _head;_headnullptr;}voidclear(){iterator itbegin();while(it!end()){iterase(it);}}voidempty_initiablize(){_headnewNode(T());_head-_next_head;_head-_prev_head;}size_tsize()const{size_tcount0;const_iterator itbegin();while(it!end()){count;it;}returncount;}boolempty()const{return_head-_next_head;}Tfront(){return_head-_next-_val;}constTfront()const{return_head-_next-_val;}Tback(){return_head-_prev-_val;}constTback()const{return_head-_prev-_val;}voidpush_front(constTval){insert(begin(),val);}voidpush_back(constTval){//Node* newnode new Node(val);//Node* tail _head-_prev;//newnode-_prev tail;//newnode-_next tail-_next;//tail-_next-_prev newnode;//tail-_next newnode;insert(end(),val);}voidpop_front(){erase(begin());}voidpop_back(){erase(--end());}//寻找iteratorfind(constTval){iterator itbegin();while(it!end()){if(*itval){returnit;}it;}returnnullptr;}//指定位置插入iteratorinsert(iterator pos,constTval){Node*curpos._node;Node*prevcur-_prev;Node*newnodenewNode(val);newnode-_prevprev;newnode-_nextcur;cur-_prevnewnode;prev-_nextnewnode;returniterator(newnode);}//指定位置删除iteratorerase(iterator pos){assert(pos!end());Node*curpos._node;Node*nextcur-_next;next-_prevcur-_prev;cur-_prev-_nextnext;delete cur;pos._nodenext;returniterator(next);}private:Node*_head;};class Date{public:Date(size_tyear1,size_tmonth1,size_tday1):_year(year),_month(month),_day(day){}//private:size_t_year;size_t_month;size_t_day;};voidprint_list(constlistintl){listint::const_iterator itl.begin();while(it!l.end()){cout*it ;it;}coutendl;}voidtest_list1(){listintl;l.push_back(1);l.push_back(2);l.push_back(3);l.push_back(4);print_list(l);}voidtest_list2(){listDatel;l.push_back(Date(2012,2,3));l.push_back(Date(2012,2,4));l.push_back(Date(2012,2,5));l.push_back(Date(2012,2,6));listDate::iterator itl.begin();while(it!l.end()){coutit-_year-it-_month-it-_dayendl;it;}}voidtest_list3(){listintl;l.push_back(1);l.push_back(2);l.push_back(3);l.push_back(4);listint::iterator posl.find(3);print_list(l);l.push_front(10);posl.begin();l.insert(l.end(),9);print_list(l);}voidtest_list4(){listintl;l.push_back(1);l.push_back(2);l.push_back(3);l.push_back(4);print_list(l);l.pop_front();print_list(l);l.pop_back();print_list(l);}voidtest_list5(){listintl1;l1.push_back(1);l1.push_back(2);l1.push_back(3);l1.push_back(4);listintl2(l1);print_list(l2);listintl3l2;print_list(l3);listDatel4(5,Date(2011,1,1));listDate::iterator itl4.begin();for(autod:l4){coutd._year-d._month-d._dayendl;}listintl5(5,1);print_list(l5);}voidtest_list6(){listintl1;l1.push_back(1);l1.push_back(2);l1.push_back(3);l1.push_back(4);coutl1.size()endl;coutl1.empty()endl;coutl1.front()endl;coutl1.back()endl;}voidtest_list7(){listintl1;l1.push_back(1);l1.push_back(2);l1.push_back(3);l1.push_back(4);listDatel4;l4.push_back(Date(2012,1,1));l4.push_back(Date(2012,2,2));l4.push_back(Date(2012,3,3));l4.push_back(Date(2012,4,4));listDate::reverse_iterator ritl4.rbegin();while(rit!l4.rend()){coutrit-_year-rit-_month-rit-_dayendl;rit;}}}三、反向迭代器的实现#define_CRT_SECURE_NO_WARNINGS1#pragmaoncenamespace sk{templateclass iterator,class Ref,class Ptrclass reverse_iterator{typedefreverse_iteratoriterator,Ref,PtrSelf;public:reverse_iterator(iterator x):_it(x){}Ref operator*(){iterator prev_it;return*(--prev);}Ptr operator-(){return(operator*());}Selfoperator(){--_it;return*this;}Selfoperator(int){_it--;return*this;}Selfoperator--(){_it;return*this;}Selfoperator--(int){_it;return*this;}bool operator!(constSelfrit)const{returnrit._it!_it;}private:iterator _it;};}四、list与vector的对比vector与list都是STL中非常重要的序列式容器由于两个容器的底层结构不同导致其特性以及应用场景不同其主要不同如下vectorlist底 层 结 构动态顺序表一段连续空间带头结点的双向循环链表随 机 访 问支持随机访问访问某个元素效率O(1)不支持随机访问访问某个元素效率O(N)插 入 和 删 除任意位置插入和删除效率低需要搬移元素时间复杂度为O(N)插入时有可能需要增容增容开辟新空间拷贝元素释放旧空间导致效率更低任意位置插入和删除效率高不需要搬移元素时间复杂度为O(1)空 间 利 用 率底层为连续空间不容易造成内存碎片空间利用率高缓存利用率高底层节点动态开辟小节点容易造成内存碎片空间利用率低缓存利用率低迭 代 器原生态指针对原生态指针(节点指针)进行封装迭 代 器 失 效在插入元素时要给所有的迭代器重新赋值因为插入元素有可能会导致重新扩容致使原来迭代器失效删除时当前迭代器需要重新赋值否则会失效插入元素不会导致迭代器失效删除元素时只会导致当前迭代器失效其他迭代器不受影响使 用 场 景需要高效存储支持随机访问不关心插入删除效率大量插入和删除操作不关心随机访问