文章目录
一、list的介绍
列表是一种顺序容器，它允许在序列中的任何位置执行常量时间插入和删除操作，并允许在两个方向上进行迭代。
它的底层是一个带头双向循环链表，我们直接来看一看整体框架：
// List的节点类template<classT>structListNode{ListNode(const T& val =T()):_val(val),_pPre(nullptr),_pNext(nullptr){}
ListNode<T>* _pPre;
ListNode<T>* _pNext;
T _val;};template<classT>classlist{typedef list_node<T> node;public://迭代器typedef __list_iterator<T> iterator;typedef __list_const_iterator<T> const_iterator;//构造list(){
_head =newnode(T());
_head->_next = _head;
_head->_prev = _head;}private:
node* _head;
size_t _size;};
二、迭代器
1、list的迭代器失效问题
insert，迭代器不失效。
earse失效。
2、迭代器的功能分类
1、单向迭代器：只能++，不能–。例如单链表，哈希表；
2、双向迭代器：既能++也能–。例如双向链表；
3、随机访问迭代器：能+±-，也能+和-。例如vector和string。
迭代器是内嵌类型（内部类或定义在类里）
3、list迭代器的模拟实现
1、list迭代器的引入
对于vector和string类而言，物理空间是连续的，原生的指针就是迭代器了（不一定哦，只是可能，版本可能不同），解引用就是数据了。但是对于这里的list而言，空间是不连续的，我们知道，迭代器有两个特征：1.解引用 2.++ /–
此时如果解引用是拿不到数据的（空间不连续），更不用说++指向下一个结点了。所以，对于list的迭代器，原生指针已经不符合我们的需求了，我们需要去进行特殊处理：进行类的封装。 我们可以通过类的封装以及运算符重载支持，这样就可以实现像内置类型一样的运算符。
2.普通迭代器
//用类封装迭代器template<classT>struct__list_iterator{typedef list_node<T> node;//用节点的指针进行构造__list_iterator(node* p):_pnode(p){}//迭代器运算符的重载
T&operator*(){return _pnode->_data;}
__list_iterator<T>&operator++()//返回值不要写成node* operator++()，因为迭代器++返回迭代器{//return _pnode->_next;
_pnode=_pnode->_next;return*this;//返回的是迭代器}booloperator!=(const __list_iterator<T>& it){return _pnode != it._pnode;}public:
node* _pnode;//封装一个节点的指针};
注意：对于迭代器的拷贝构造和赋值重载我们并不需要自己去手动实现，编译器默认生成的就是浅拷贝，而我们需要的就是浅拷贝，这也说明了，并不是说如果有指针就需要我们去实现深拷贝。另外，迭代器通过结构体指针访问修改链表，所以，对于迭代器我们并不需要构造函数，结点的释放由链表管理。
3.const迭代器
const迭代器的错误写法：
typedef __list_iterator<T> iterator;const list<T>::iterator it=lt.begin();
因为typedef后，const修饰的是迭代器it，只能调用operator*(),调不了operator++()。
正确写法：想实现const迭代器，，需要再写一个const版本迭代器的类。
//用类封装const迭代器template<classT>struct__list_const_iterator{typedef list_node<T> node;//用节点的指针进行构造__list_const_iterator(node* p):_pnode(p){}//迭代器运算符的重载const T&operator*()const{return _pnode->_data;}
__list_const_iterator<T>&operator++()//返回值不要写成node*，因为迭代器++肯定返回迭代器{//return _pnode->_next;//返回类型错误的
_pnode = _pnode->_next;return*this;//返回的是迭代器}
__list_const_iterator<T>&operator--(){
_pnode = _pnode->_prev;return*this;}booloperator!=(const __list_const_iterator<T>& it)const{return _pnode != it._pnode;}public:
node* _pnode;//封装一个节点的指针};typedef __list_const_iterator<T> const_iterator;
如果是这样子去实现的话，我们就会发现，这两个迭代器的实现并没有多大的区别，唯一的区别就在于operator*的不同。const迭代器和普通迭代器的唯一区别就是普通迭代器返回T&，可读可写，const迭代器返回const T&,可读不可写，上面的代码存在很大的问题：代码冗余，所以我们应该去解决这个问题：我们可以参考源码的实现：类模板参数解决这个问题，这也是迭代器的强大之处
//用类封装普通/const迭代器template<classT,classRef>struct__list_iterator{typedef list_node<T> node;typedef __list_iterator<T,Ref> Self;//用节点的指针进行构造__list_iterator(node* p):_pnode(p){}//迭代器运算符的重载
Ref operator*(){return _pnode->_data;}
Self&operator++()//返回值不要写成node*，因为迭代器++肯定返回迭代器啊，你返回节点指针类型不对{//return _pnode->_next;//返回类型错误的
_pnode=_pnode->_next;return*this;//返回的是迭代器}
Self&operator--(){
_pnode = _pnode->_prev;return*this;}booloperator!=(const Self& it){return _pnode != it._pnode;}public:
node* _pnode;//封装一个节点的指针};typedef __list_iterator<T, T&> iterator;typedef __list_iterator<T,const T&> const_iterator;
4、迭代器operator->的重载
迭代器的用法就是模拟指针的行为，如果现在有一个指向结构的指针，那么就需要用到->来解引用。
//*的重载：返回节点的数据
Ref operator*(){return _pnode->_data;}//->的重载：返回数据的指针
T*operator->(){return&_pnode->_data;}
但是operator->使用T*做返回值类型，这样无论是普通迭代器和const迭代器都能修改，所以operator->的返回值类型应该改为泛型：
template<classT,classRef,classPtr>
Ptr operator->(){return&_pnode->_data;}typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T,const T&,const T*> const_iterator;
5、迭代器价值
1、封装底层实现，不暴露底层实现的细节；
2、多种容器提供统一的访问方式，降低使用成本；
C语言没有运算符重载和引用等语法，是实现不了迭代器的。
三、增删查改
1、insert和erase
insert：在pos位置上一个插入，返回插入位置的迭代器，对于list的insert迭代器不会失效，vector失效是因为扩容导致pos位置造成野指针问题。
iterator insert(iterator pos,const T& x){
node* newnode =newnode(x);
node* cur = pos._pnode;
node* prev = cur->_prev;
newnode->_prev = prev;
prev->_next = newnode;
newnode->_next = cur;
cur->_prev = newnode;++_size;returniterator(newnode);}
erase:这里的带头（哨兵位）头结点不可删除，返回值是删除位置的下一个，对于list的erase迭代器是失效的
iterator erase(iterator pos){assert(pos !=end());
node* prev = pos._pnode->_prev;
node* next = pos._pnode->_next;
prev->_next = next;
next->_prev = prev;delete pos._pnode;--_size;returniterator(next);}
2、push_back和push_front
voidpush_back(const T& x){/*node* newnode = new node(x);
node* tail = _head->_prev;
newnode->_prev = tail;
tial->_next = newnode;
newnode->_next = _head;
_head->_prev = newnode;*/insert(end(), x);}voidpush_front(const T& x){insert(begin(), x);}
3、pop_back和pop_front
尾删和头删，复用erase即可
voidpop_front(){erase(begin());}voidpop_back(){erase(--end());}
四、list的构造函数
1、构造
默认构造：
list(){
_head =newnode(T());
_head->_next = _head;
_head->_prev = _head;
_size =0;}
我们可以用empty_initialize()来封装初始化，方便复用，不用每次都写：
voidempty_initialize(){
_head =newnode(T());
_head->_next = _head;
_head->_prev = _head;
_size =0;}
迭代器区间构造：
//迭代器区间构造template<classInputIterator>list(InputIterator first, InputIterator last){empty_initialize();while(first != last){push_back(*first);++first;}}
拷贝构造：
传统写法
list(const list<T>& lt){empty_initialize();for(constauto& e : lt){push_back(e);}}
用范围for进行尾插，但是要注意要加上&，范围for是*it赋值给给e，又是一个拷贝，e是T类型对象，依次取得容器中的数据，T如果是string类型，不断拷贝，push_back之后又销毁。
现代写法
voidswap(list<T>& lt){
std::swap(_head, lt._head);
std::swap(_size, lt._size);}list(const list<T>& lt){empty_initialize();
list<T>tmp(lt.begin(), lt.end());swap(tmp);}
2、赋值重载
传统写法
list<T>&operator=(list<T>& lt){if(this!=<){clear();for(constauto& e : lt){push_back(e);}}return*this;}
现代写法
list<T>&operator=(list<T> lt){swap(lt);return*this;}
3、析构
对于list，有单独的clear()接口，list的析构可以直接复用clear()，同时还需要我们去释放掉头结点：
~list(){clear();delete _head;
_head =nullptr;}voidclear(){
iterator it =begin();while(it !=end()){
it =erase(it);}}
类名和类型的区别
普通类：类名等于类型
类模板：类名不等价于类型，例如list类模板类名是list,类型list等。
所以我们平常写函数形参和返回值时，总会带上形参和返回值的类型：
// 赋值运算符重载
list<T>&operator=(list<T> lt){swap(lt);return*this;}
五、list和vector的对比
1.vector
vector的优点（结构牛逼）：
1、支持下标的随机访问；
2、尾插尾删效率高（当然扩容的那一次尾插会较慢）；
3、CPU高速缓存命中高（数据从缓存加载至CPU中，会加载连续的一段数据，vector因为结构连续，高速缓存命中高）。
vector的缺点：
1、非尾插尾删效率低；
2、扩容有消耗，并存在一定的空间浪费。
vector迭代器失效问题：
insert/erase均失效。（如果string的insert和erase形参是迭代器，那么也会失效，但是大部分接口是下标传参，不考虑失效问题，只有几个接口是迭代器传参，需要注意迭代器失效问题）
2、list
list的优点：
1、按需申请释放，无需扩容；
2、任意位置插入删除时间O(1)；（这里说的是插入删除，不要加上查找的时间）
list的缺点：
1、不支持下标的随机访问；
2、CPU高速缓存命中率低；
3、每一个节点除了存储数据外，还需要额外存储两个指针。
vectorlist底 层 结 构动态顺序表，一段连续空间带头结点的双向循环链表随 机 访 问支持随机访问，访问某个元素效率O(1)不支持随机访问，访问某个元素效率O(N)插 入 和 删 除任意位置插入和删除效率低，需要搬移元素，时间复杂度为O(N)，插入时有可能需要增容，增容：开辟新空间，拷贝元素，释放旧空间，导致效率更低任意位置插入和删除效率高，不需要搬移元素，时间复杂度为O(1)空 间 利 用 率底层为连续空间，不容易造成内存碎片，空间利用率高，缓存利用率高底层节点动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低迭 代 器原生态指针对原生态指针(节点指针)进行封装迭 代 器 失 效在插入元素时，要给所有的迭代器重新赋值，因为插入元素有可能会导致重新扩容，致使原来迭代器失效，删除时，当前迭代器需要重新赋值否则会失效插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响使 用 场 景需要高效存储，支持随机访问，不关心插入删除效率大量插入和删除操作，不关心随机访问
六、模拟实现list整体代码
namespace fx
{// List的节点类template<classT>structListNode{ListNode(const T& val =T()):_val(val),_pPre(nullptr),_pNext(nullptr){}
ListNode<T>* _pPre;
ListNode<T>* _pNext;
T _val;};//List的迭代器类template<classT,classRef,classPtr>classListIterator{typedef ListNode<T>* PNode;typedef ListIterator<T, Ref, Ptr> Self;public:ListIterator(PNode pNode =nullptr):_pNode(pNode){}ListIterator(const Self& l){
_pNode = l._pNode;}
Ref operator*(){return _pNode->_val
}
Ptr operator->(){}
Self&operator++(){return _pNode->_pNext;}
Self operator++(int){
Self tmp(*this);
_pNode = _pNode->_pNext;return tmp;}
Self&operator--(){return _pNode->_pPre;}
Self&operator--(int){
Self tmp(*this);
_pNode = _pNode->_pPre;return tmp;}booloperator!=(const Self& l){return _pNode != l._pNode;}booloperator==(const Self& l){return _pNode == l._pNode;}private:
PNode _pNode;};//list类template<classT>classlist{typedef ListNode<T> Node;typedef Node* PNode;public:typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T,const T&,const T*> const_iterator;public:///// List的构造voidCreateHead(){
Node* _pHead =new Node;
_pHead->_pNext = _pHead;
_pHead->_pPre = _pHead;
_size =0;}list(){CreateHead();}list(int n,const T& value =T()){CreateHead();for(int i =0; i < n;++i){push_back(value);}}template<classIterator>list(Iterator first, Iterator last){CreateHead();wihle(first != last){push_back(*first);++first;}}list(const list<T>& l){CreateHead();for(auto& e : lt){push_back(e);}}
list<T>&operator=(const list<T> l){swap(l);return*this;}~list(){clear();delete _head;
_head =nullptr;}///// List Iterator
iterator begin(){return _pHead->_pNext;}
iterator end(){return _pHead;}
const_iterator begin(){return _head->_next;}
const_iterator end(){return _pHead;}///// List Capacity
size_t size()const{return _size;}boolempty()const{return _size ==0;}// List Access
T&front(){return*begin();}const T&front()const{return*begin();}
T&back(){return _head->_prev->_val;}const T&back()const{return _head->_prev->_val;}// List Modifyvoidpush_back(const T& val){insert(end(), val);}voidpop_back(){erase(--end());}voidpush_front(const T& val){insert(begin(), val);}voidpop_front(){erase(begin());}// 在pos位置前插入值为val的节点
iterator insert(iterator pos,const T& val){
Node* newnode =new Node;
Node* cur = pos._node;
Node* prev = cur->_prev;
newnode->_next = cur;
cur->_prev = newnode;
newnode->_prev = prev;
prev->_next = newnode;++_size;}// 删除pos位置的节点，返回该节点的下一个位置
iterator erase(iterator pos){assert(pos !=end());
Node* prev = pos._node->_prev;
Node* next = pos._node->_next;
prev->_next = next;
next->_prev = prev;delete pos._node;--_size;}voidclear(){auto it =begin();while(it !=end()){
it =erase(it);}}voidswap(list<T>& l){
std::swap(_head, lt._head);
std::swap(_size, lt._size);}private:
PNode _pHead;
size_t _size;};};
版权归原作者 Filex; 所有， 如有侵权，请联系我们删除。