list的实现和使用

list深入讲解

1. 简述与适用场景

list是双向链表的标准实现，适用于：

• 频繁在容器中间进行插入/删除的场景（已知位置的情况下这些操作为 O(1)）。
• 需要稳定的指针/迭代器（对于不被删除的元素，list的迭代器在大多数操作后仍然有效）。

不适合场景：

• 需要频繁随机访问（operator[]不可用，跳转到第 n 个元素需 O(n)）。
• 大量排序且希望用sort（sort需要随机访问迭代器）。

cpp list<int>lt;lt.push_back(1);lt.push_back(3);lt.push_back(2);lt.push_back(6);for(autoe:lt)cout<<e<<" ";

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(inta1=1,inta2=2):_a1(a1),_a2(a2){}int_a1;int_a2;};list<A>lt1;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(greater<int>())进行降序。
• 如果希望利用std::sort的速度（随机访问算法常常更快），可以先把list内容拷贝到vector，排序后再assign回list：

cpp vector<int>v(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)
• splice：O(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{template<classT>classlist_node{public:T _data;list_node<T>*_next;list_node<T>*_prev;list_node(constT&data=T()):_data(data),_next(nullptr),_prev(nullptr){}};//重点：迭代器的实现template<classT>structlist_iterator//默认{typedeflist_node<T>Node;typedeflist_iterator<T>Self;//const iterator -> 迭代器本身不能修改//const_iterator -> 指向内容不能修改Node*_node;T&operator*(){return_node->_data;}Self&operator++()//前置{_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;}T&operator->(){return_node->_data;}booloperator!=(constSelf&s)const{return_node!=s._node;}list_iterator(Node*node):_node(node){}};//const迭代器的实现template<classT>structlist_const_iterator//默认{typedeflist_node<T>Node;typedeflist_const_iterator<T>Self;Node*_node;list_const_iterator(Node*node):_node(node){}constT&operator*(){return_node->_data;}Self&operator++()//前置{_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;}constT*operator->(){return_node->_data;}booloperator!=(constSelf&s)const{return_node!=s._node;}};template<classT>classlist{typedeflist_node<T>Node;public:typedeflist_iterator<T,T&,T*>iterator;typedeflist_iterator<T,constT&,constT*>const_iterator;list():_head(newNode()),_size(0){_head->_next=_head;_head->_prev=_head;}~list(){clear();delete_head;}list(constlist<T>&lt):list(){for(autoconst&e:lt)push_back(e);}list<T>&operator=(list<T>lt){swap(lt);return*this;}voidswap(list<T>&lt){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(constT&x){Node*newnode=newNode(x);Node*tail=_head->_prev;tail->_next=newnode;newnode->_prev=tail;newnode->_next=_head;_head->_prev=newnode;++_size;}iteratorinsert(iterator pos,constT&x){Node*cur=pos._node;Node*prev=cur->_prev;Node*newnode=newNode(x);newnode->_next=cur;cur->_prev=newnode;newnode->_prev=prev;prev->_next=newnode;++_size;returniterator(newnode);}iteratorerase(iterator pos){assert(pos!=end());Node*cur=pos._node;Node*prev=cur->_prev;Node*next=cur->_next;prev->_next=next;next->_prev=prev;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*next=cur->_next;deletecur;cur=next;}_head->_next=_head;_head->_prev=_head;_size=0;}size_tsize()const{return_size;}boolempty()const{return_size==0;}private:Node*_head;size_t _size;};}

其中，迭代器的实现部分我们可以使用高度相似的模板复用实例化来优化代码

template<classT,classRef,classPtr>structlist_iterator//默认{typedeflist_node<T>Node;typedeflist_iterator<T,Ref,Ptr>Self;Node*_node;list_const_iterator(Node*node):_node(node){}Refoperator*(){return_node->_data;}Self&operator++()//前置{_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;}Ptroperator->(){return_node->_data;}booloperator!=(constSelf&s)const{return_node!=s._node;}};