网站界面设计案例莱芜都市网官网

网站界面设计案例,莱芜都市网官网,免费视频剪辑软件,网络营销顾问list 深入讲解 1. 简述与适用场景 list 是双向链表的标准实现#xff0c;适用于#xff1a; 频繁在容器中间进行插入/删除的场景#xff08;已知位置的情况下这些操作为 O(1)#xff09;。需要稳定的指针/迭代器#xff08;对于不被删除的元素#xff0c;list 的迭代器在…list深入讲解1. 简述与适用场景list是双向链表的标准实现适用于频繁在容器中间进行插入/删除的场景已知位置的情况下这些操作为 O(1)。需要稳定的指针/迭代器对于不被删除的元素list的迭代器在大多数操作后仍然有效。不适合场景需要频繁随机访问operator[]不可用跳转到第 n 个元素需 O(n)。大量排序且希望用sortsort需要随机访问迭代器。cpp listintlt;lt.push_back(1);lt.push_back(3);lt.push_back(2);lt.push_back(6);for(autoe:lt)coute ;2. 迭代器分类复盘按功能iterator、const_iterator、reverse_iterator等。按性质底层决定单向forward_list仅支持双向list支持和--随机访问vector/deque支持/-关键点算法要求特定迭代器类别例如sort要求随机访问迭代器因此不能直接对list使用sort。3. 增删改查基础push_back/push_front在尾/头插入元素。emplace_back/emplace_front直接在容器内部构造对象避免额外拷贝/移动。emplace_back可以代替push_back使用且在默写场景下效率更高。cppstructA{A(inta11,inta22):_a1(a1),_a2(a2){}int_a1;int_a2;};listAlt1;Aaa1(1,1);lt1.push_back(aa1);lt1.emplace_back(3,3);// 直接构造insert(it, value)在迭代器it之前插入O(1)。erase(it)删除it指向的节点返回下一个迭代器。remove(value)查找并删除所有等于value的元素按值删除不需要迭代器。splice(...)在常数时间内把一个链表或一段节点从一个list移动到另一个list不拷贝节点仅变指针。lt1.splice(it, lt2)把lt2全部插入到lt1的it前lt2变空。lt.splice(lt.begin(), lt, it)把单个节点移动到头部。lt.splice(lt.begin(), lt, it, lt.end())把[it, end)段移动到头部。reverse()链表自身提供反转lt.reverse()。注意std::reverse(lt.begin(), lt.end())对双向迭代器同样可用但list有专门的reverse()。4. 排序与合并std::sort不能直接用于list需随机访问迭代器。std::list提供list::sort()内部是归并排序稳定适合链表。可以传入仿函数或函数对象如lt.sort(greaterint())进行降序。如果希望利用std::sort的速度随机访问算法常常更快可以先把list内容拷贝到vector排序后再assign回listcpp vectorintv(lt.begin(),lt.end());sort(v.begin(),v.end());lt.assign(v.begin(),v.end());merge合并两个已排序的list将元素从参数表list中移动到目标list操作后被合并的list变空。cpp x.sort();y.sort();x.merge(y);// y 变空x 成为合并后的有序列表5. 性能与复杂度总结常见操作push_back,push_front: O(1)insert在已知位置: O(1)erase给定迭代器: O(1)find基于值: O(n)spliceO(1)只是改变指针不拷贝sort()list::sort: O(n log n)归并排序remove(value): O(n)注意虽然对单个已知位置的插入/删除为 O(1)但查找位置仍然可能需要 O(n)。6. 常见“坑”与建议不能对list使用std::sort会编译错误应使用list::sort或先复制到vector。splice非常高效但要注意源list中被移动节点的迭代器/引用在语义上仍然有效并且指向原节点但被移走后会在新容器中可用。对list执行大量随机访问步进迭代器若干次以到达位置会很慢应考虑vector或deque。emplace_back在构造复杂对象时通常比push_back更高效因为能避免不必要的拷贝/移动。在并发环境下list不提供线程安全操作前需加锁或采用其他并发容器。7. 小结std::list在需要频繁、局部化的插入和删除时是优秀的选择并通过splice、merge等操作能以常数时间移动节点。若需随机访问或使用需要随机访问迭代器的算法如std::sort应使用vector/deque或将list的数据转换到vector再处理。选择容器时优先考虑操作模式插入/删除 vs 随机访问 vs 内存紧凑性与缓存友好性vector通常更缓存友好。list模拟实现namespacelist{templateclassTclasslist_node{public:T _data;list_nodeT*_next;list_nodeT*_prev;list_node(constTdataT()):_data(data),_next(nullptr),_prev(nullptr){}};//重点迭代器的实现templateclassTstructlist_iterator//默认{typedeflist_nodeTNode;typedeflist_iteratorTSelf;//const iterator - 迭代器本身不能修改//const_iterator - 指向内容不能修改Node*_node;Toperator*(){return_node-_data;}Selfoperator()//前置{_node_node-next;return*this;}Selfoperator(int)//后置{Selftmp(*this);_node_node-next;returntmp;}Selfoperator--(){_node_node-_prev;return*this;}Selfoperator--(int){Selftmp(*this);_node_node-prev;returntmp;}Toperator-(){return_node-_data;}booloperator!(constSelfs)const{return_node!s._node;}list_iterator(Node*node):_node(node){}};//const迭代器的实现templateclassTstructlist_const_iterator//默认{typedeflist_nodeTNode;typedeflist_const_iteratorTSelf;Node*_node;list_const_iterator(Node*node):_node(node){}constToperator*(){return_node-_data;}Selfoperator()//前置{_node_node-next;return*this;}Selfoperator(int)//后置{Selftmp(*this);_node_node-next;returntmp;}Selfoperator--(){_node_node-_prev;return*this;}Selfoperator--(int){Selftmp(*this);_node_node-prev;returntmp;}constT*operator-(){return_node-_data;}booloperator!(constSelfs)const{return_node!s._node;}};templateclassTclasslist{typedeflist_nodeTNode;public:typedeflist_iteratorT,T,T*iterator;typedeflist_iteratorT,constT,constT*const_iterator;list():_head(newNode()),_size(0){_head-_next_head;_head-_prev_head;}~list(){clear();delete_head;}list(constlistTlt):list(){for(autoconste:lt)push_back(e);}listToperator(listTlt){swap(lt);return*this;}voidswap(listTlt){std::swap(_head,lt._head);std::swap(_size,lt._size);}iteratorbegin(){returniterator(_head-_next);}iteratorend(){returniterator(_head);}const_iteratorbegin()const{returnconst_iterator(_head-_next);}const_iteratorend()const{returnconst_iterator(_head);}voidpush_back(constTx){Node*newnodenewNode(x);Node*tail_head-_prev;tail-_nextnewnode;newnode-_prevtail;newnode-_next_head;_head-_prevnewnode;_size;}iteratorinsert(iterator pos,constTx){Node*curpos._node;Node*prevcur-_prev;Node*newnodenewNode(x);newnode-_nextcur;cur-_prevnewnode;newnode-_prevprev;prev-_nextnewnode;_size;returniterator(newnode);}iteratorerase(iterator pos){assert(pos!end());Node*curpos._node;Node*prevcur-_prev;Node*nextcur-_next;prev-_nextnext;next-_prevprev;deletecur;--_size;returniterator(next);}voidpop_back(){assert(!empty());erase(iterator(_head-_prev));}voidpop_front(){assert(!empty());erase(begin());}voidclear(){Node*cur_head-_next;while(cur!_head){Node*nextcur-_next;deletecur;curnext;}_head-_next_head;_head-_prev_head;_size0;}size_tsize()const{return_size;}boolempty()const{return_size0;}private:Node*_head;size_t _size;};}其中迭代器的实现部分我们可以使用高度相似的模板复用实例化来优化代码templateclassT,classRef,classPtrstructlist_iterator//默认{typedeflist_nodeTNode;typedeflist_iteratorT,Ref,PtrSelf;Node*_node;list_const_iterator(Node*node):_node(node){}Refoperator*(){return_node-_data;}Selfoperator()//前置{_node_node-next;return*this;}Selfoperator(int)//后置{Selftmp(*this);_node_node-next;returntmp;}Selfoperator--(){_node_node-_prev;return*this;}Selfoperator--(int){Selftmp(*this);_node_node-prev;returntmp;}Ptroperator-(){return_node-_data;}booloperator!(constSelfs)const{return_node!s._node;}};