先申明一下本篇总体介绍过程是按照逐步深入去写的，所以可能有些同样类型不在一块！

前言：

  写这篇博客的时候，我是边思考边写它！自己其中感觉自己对于list的理解更加的深入，其中提出的很多问题让我明白了list为什么要这么设计，以及代码为啥要这么写！希望我的这篇博客不仅让我受益匪浅，也能对你有所帮助！若您发现了其中有什么地方有问题，希望评论区您能提出来。如果你有更好的理解思路，也希望您能不吝赐教！最后写博客不易，还望给一个赞！

 💡💡追着光，跟着光，成为光，发散光！

目录

 一、list 介绍

 二、list 基本框架

2.1 结点

2.2 迭代器框架

2.3  链表类框架

三、模拟实现list

3.1 先提前写好的list函数

3.1.1 默认构造函数list() （构建哨兵结点）

 💡💡3.1.2 返回（非const）迭代器的begin() end(）

3.1.3 迭代器价值+类封装价值

3.2 挪动数据的函数

之前先说明如何查找位置？标准库的find(）函数！

3.2.1 insert() 任意位置插入 （往指定位置的前面插入）

3.2.2 erase() 任意位置删除结点 （ 迭代器失效问题）

3.2.3 push_back() 尾插

3.2.4 pop_back() 尾删 

3.2.5 push_front() 头插 

3.2.5 pop_front() 头删

3.3 构造函数

3.3.1 迭代器区间构造

3.3.2 拷贝构造（现代写法）

💡💡引入const 迭代器（非常重要！）

3.3.4 赋值拷贝（现代写法） 

3.4 释放空间函数

3.4.1 clear() 释放list非哨兵结点其余结点

3.4.2 ~list() 析构函数

四、模拟实现的list

---

 一、list 介绍

1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
2. list的底层是带头双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
3. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
4. 与其他序列式容器相比，list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)

💡强调一下head是哨兵结点，本身不存储数据，作用只是指向头和尾！

---

 二、list 基本框架

2.1 结点

//结点
template<class T>
struct list_node
{//结点构造函数list_node(const T& val = T()):prev(nullptr), next(nullptr), data(val){}
public:list_node* prev;//接前list_node* next;//接后T data;//存储数据
};

这里对于T（）说明一下！这里是匿名构造，对于传来的参数类型不确定，可能是内置类型，也可能是类对象！所以不能想当然比如说默认赋值0！

2.2 迭代器框架

template<class T,class ref,class ptr>struct list_iterator{typedef list_node<T> node;typedef list_iterator<T, ref, ptr> Self;node* pnode;list_iterator(node* p):pnode(p){}ref operator*()ptr operator->()//前置Self& operator++()//后置Self operator++(int)//前置Self& operator--()//后置Self operator--(int)bool operator!=(const Self& it)bool operator==(const Self& it)};

2.3  链表类框架

class list{public:typedef list_node<T> node;typedef list_iterator<T,T&,T*> iterator;typedef list_iterator<T, const T&,const T*> const_iterator;iterator begin()const_iterator begin()constconst_iterator end()constiterator end()void clear()~list()void empty_initialize()list()template <class InputIterator>list(InputIterator first, InputIterator end)void swap(list<T>& lt)list(const list<T>& lt)list<T>& operator=(list<T> tmp)void push_back(const T& x)void push_front(const T& x)void pop_front()void pop_back()void insert(iterator pos,const T& x)iterator erase(iterator pos)private:node* head;//底层是一个哨兵结点};

这里问一个问题，等你看完这篇文章理解很多的时候，回来比较这三个类的是否手动析构，手动写拷贝构造！深入自己想想为啥是上面的结果！

三、模拟实现list

3.1 先提前写好的list函数

这些函数是后面写的基础！后面会频繁调用，所以先写出来！

3.1.1 默认构造函数list() （构建哨兵结点）

💡强调一下head是哨兵结点，本身不存储数据，作用只是指向头和尾！

后面要多次用到这个empty_initialize()内代码 ，所以就用函数了！

void empty_initialize()
{head = new node;//用new对象，可以直接调用对象的构造函数head->next = head;head->prev = head;
}
list()
{empty_initialize();
}

 💡💡3.1.2 返回（非const）迭代器的begin() end(）

首先我们需要将封装的迭代器需要实现的功能函数写好！

❓❓首先我们要问自己一个问题，链表的迭代器能不能像vector string 那样直接单纯地用解引用和++？

我们不妨回顾一下vector string 的迭代器，其底层是指针数组的原生指针！而它们容器的存储空间是连续的，解引用可以直接拿到数组数据，++可以直接加上类型的步长！

而list的呢？list是不连续的！它们通过前后指针链接！直接++不能找到后一个结点！解引用不是直接拿到存储数据，而是一个结点结构体！我们需要的是里面的Data!

怎么办？ 系统的* ++ 不能满足我们需要的结果！

💡必须重载运算符！所以我们得将迭代器封装成一个类！

现在再问自己一个问题！ 他的类成员变量是谁？ 联系一下我们的目的和链表容器结构！

我们想到一个指向node 的指针就可以解决了，++不就是next,--不就是prev *不就是data!

！这里单独将->符号拿出来说明一下！ 想用->访问数据，->左边是什么？ 是结构体地址！ 

也就是说如果我们list 存储的数据是结构体或者类！里面有多个变量，那么我们访问数据就不能单纯的解引用！必须使用->来访问数据！

下面上代码~

template<class T>
struct list_iterator
{typedef list_node<T> node;//结点类typedef list_iterator<T> Self;//迭代器类node* pnode;//成员变量//构造函数 list_iterator(node* p):pnode(p){}T& operator*(){return pnode->data;}T* operator->(){return &pnode->data;//返回结构体地址}Self& operator++(){pnode = pnode->next;return *this;}Self& operator--(){pnode = pnode->prev;return *this;}bool operator!=(const Self& it){return pnode != it.pnode;}
};

现在迭代器功能基本完善！我们通过链表函数构建迭代器！

//再强调一下，迭代器被封装成类！！！
typedef list_iterator<T> iterator;iterator begin()
{//匿名对象返回！这里调用了迭代器的构造函数return iterator(head->next);
}iterator end()
{//这里千万记住，返回的是哨兵结点！不是尾结点!return iterator(head);
}

现在看看如何使用迭代器！

3.1.3 迭代器价值+类封装价值

迭代器是一种可以遍历数组的抽象接口！

1.封装底层实现，不暴露底层实现原理

2.有了迭代器，可以不关心底层实现原理，而是注重使用！

我们上面用的*符号，看似简单几个字母，可底层却是返回Data!我们不需要知道它返回的具体是什么，我们只要知道*符号代表着就是获取容器数据的方式！

类封装价值是什么？

1.因为不同容器实现原理不同，vector，list同样是*符号，对于vector，*号是原生指针！解引用可以直接获取数据，但是对于list，解引用实现不了我们直接获取数据的方法！（前面说过）有了类封装，我们就可以重载*号，让它的意义改变！有了封装，让我们使得同样的符号，对于不同实现原理的容器，可以有同样的效果！

2.我们可以注意到，即使是封装了迭代器，它的物理消耗内存仍只有一个指针大小！也就是说即使是类，他没有过多消耗内存！

---

3.2 挪动数据的函数

有了迭代器，它的成员变量是指向结点的指针，所以我们可以用迭代器获取结点位置！

之前先说明如何查找位置？标准库的find(）函数！

参数为迭代器头尾和要查找的数据！

3.2.1 insert() 任意位置插入 （往指定位置的前面插入）

void insert(iterator pos, const T& x)
{node* newnode = new node(x);//构造新结点node* cur = pos.pnode;//记录当前结点node* prev = cur->prev;prev->next = newnode;newnode->prev = prev;cur->prev = newnode;newnode->next = cur;
}

---

3.2.2 erase() 任意位置删除结点 （ 迭代器失效问题）

iterator erase(iterator pos)
{node* cur = pos.pnode;node* prev = cur->prev;node* next = cur->next;prev->next = next;next->prev = prev;delete[]cur;//delete会调用结点类的默认析构函数//！！！返回下一个位置的迭代器return iterator(next);
}

 为什么会有迭代器失效问题？ 因为结点空间被释放了，这样迭代器++也就不能找到下一个位置结点，所以返回需要返回下一个结点迭代器！

3.2.3 push_back() 尾插

void push_back(const T& x)
{insert(end(), x);
}

3.2.4 pop_back() 尾删 

这里提一嘴，注意前后两者区别，前面不--end() 因为插入是插在结点前一个！end()返回哨兵结点，插在它的前一个就是尾结点！

这里尾删，删的是尾结点，所以--迭代器重载返回前一个结点，也就是尾结点！

void pop_back()
{erase(--end());
}

3.2.5 push_front() 头插 

void push_front(const T& x)
{insert(begin(), x);
}

3.2.5 pop_front() 头删

void pop_front()
{erase(begin());
}

---

---

3.3 构造函数

3.3.1 迭代器区间构造

template <class InputIterator>
list(InputIterator first, InputIterator end)
{empty_initialize();//构建哨兵结点while (first != end){push_back(*first);++first;}
}

3.3.2 拷贝构造（现代写法）

1.先构造临时链表tmp（深拷贝！）->> 2. 临时链表与拷贝构造链表交换！

那么如何交换两个链表？ 很简单就是交换两个链表的哨兵结点！

//list<T> lt2(lt1)
void swap(list<T>& lt)
{std::swap(head, lt.head);//交换地址
}
list(const list<T>& lt)
{empty_initialize();//注意我们必须初始化lt2的哨兵结点！这样tmp析构的时候析构的不是野指针！list<T> tmp(lt.begin(), lt.end());swap(tmp);
}

💡💡引入const 迭代器（非常重要！）

首先说明一下，为什么从这里引入const 迭代器，因为注意一下这个拷贝构造的传参，是const list<T> &，我们在用迭代器构造tmp的时候，传的 lt 是const的！

所以我们要实现const 迭代器！

首先我们得明确一下const迭代器const的作用，这个const保护的是Data!也就是说数据只可读，不可写！迭代器解引用不能算数运算！迭代器本身可以++!

如何实现const迭代器？

先思考一下下面这个写法能不能实现我们要的const迭代器

 现在看看这样的 rit 能干什么：

 我们看到它不能++,它可以解引用算数运算！它是const迭代器吗？当然不是！通过结果我们不难可以类比原来的内置类型 这样写法相当于 int const * 而我们需要的是 const int* !

所以我们仍需要自己写一个const迭代器！

我们在明确一下const 迭代器与非const 迭代器的主要区别就在* 后是可读可写，还是只可读！也就是返回值一个是const T，一个是T！

💡💡那这就很简单了，那不就是我们在原来普通迭代器基础上重载一个*号运算符重载函数，如下：

template<class T>
struct list_iterator
{typedef list_node<T> node;//结点类typedef list_iterator<T> Self;//迭代器类..../之前上面写的普通迭代器函数const T& operator*()const{return pnode->data;}
};

可是这样真的行吗？这样解决了当前的问题，可是我const迭代器想要调用普通迭代器其他接口函数怎么办？有人又会说了那每一个都重载一下呗！每一个函数都弄一个const！

比如 之前的++,写成如下：

 那么请问，如果这样写了会有什么后果！我们来看看！

因为const 修饰了this指针，所以我们不能改变this指向的类对象成员函数 ！

可是我们const迭代器只需要对* 做修改！所以这种只在原迭代器补const重载函数，行不通！

那么引入第三种想法（一般人），我们可以重新写一个const迭代器类封装它，类中与原来普通迭代器不同的就是*号 重载函数！

//在list类中定义const迭代器
typedef const_list_iterator<T> const_iterator;//const迭代器类
template<class T>
struct const_list_iterator
{typedef list_node<T> node;//结点类typedef const_list_iterator<T> Self;//迭代器类node* pnode;//成员变量//构造函数 list_iterator(node* p):pnode(p){}//唯一区别地方const T& operator*(){return pnode->data;}T* operator->(){return &pnode->data;//返回结构体地址}Self& operator++(){pnode = pnode->next;return *this;}Self& operator--(){pnode = pnode->prev;return *this;}bool operator!=(const Self& it){return pnode != it.pnode;}
};

现在我们看看C++设计者大佬的写法！它们的写法就是一行代码能解决的事绝不用多行！

之前我们先引入一个问题，模板类 类型的问题！

请问list 是类型吗？它不是！它是类明！

什么是类型？ 诸如list<int>的list<T>它们是类型！ 区别模板类类型的关键在于T！现在再想一想const迭代器不同于普通迭代器什么？不就是重载的*号不同！那么我们是否可以多一个模板参数，区别这两个不同的类！

list_iterator<T,T>  list_iterator<T,const T>这两个不是同一个迭代器！！！   

现在看看大佬写法！

三个模板参数！！ 两者区别在于第二个一个是T，一个是const T!

//这里的T*是->返回时的参数
typedef list_iterator<T,T&,T*> iterator;
typedef list_iterator<T, const T&,const T*> const_iterator;const_iterator begin()const
{return const_iterator(head->next);
}
const_iterator end()const
{return const_iterator(head);
}template<class T, class ref, class ptr>
struct list_iterator
{typedef list_node<T> node;typedef list_iterator<T, ref, ptr> Self;node* pnode;list_iterator(node* p):pnode(p){}ref& operator*(){return pnode->data;}ptr operator->(){return &pnode->data;}Self& operator++(){pnode = pnode->next;return *this;}Self& operator--(){pnode = pnode->prev;return *this;}bool operator!=(const Self& it){return pnode != it.pnode;}
};

---

3.3.4 赋值拷贝（现代写法） 

1.构造tmp--> 2.交换--> 3.出作用域，临时变量调用析构函数，释放this原空间

//连等可能，所以返回链表！
//出作用域,被替换的tmp会调用它的析构函数,析构this的原空间list<T>& operator=(list<T> tmp)
{swap(tmp);return *this;
}

---

3.4 释放空间函数

3.4.1 clear() 释放list非哨兵结点其余结点

void clear()
{iterator first = begin();while (first != end()){first = erase(first);//!!!注意考虑迭代器失效}
}

3.4.2 ~list() 析构函数

~list()
{clear();delete head;head = nullptr;
}

这里再引入一个问题！为什么之前的迭代器类，结点类我们没有写析构函数？现在需要写呢？

因为这两个类的成员变量都是内置类型，默认构造会自动释放成员变量。它们的任务都是单个结点！

如果list我们这里不写，默认析构函数只会将我们的头结点释放，那些剩余结点并没有被释放，也就是说list析构任务不仅仅是单个结点，而是所有结点！所以这里我们必须手动写！ 

四、模拟实现的list

namespace wyz
{template<class T>struct list_node{list_node(const T& val = T()):prev(nullptr), next(nullptr), data(val){}public:list_node* prev;list_node* next;T data;};template<class T, class ref, class ptr>template<class T, class ref, class ptr>
struct list_iterator
{typedef list_node<T> node;typedef list_iterator<T, ref, ptr> Self;node* pnode;list_iterator(node* p):pnode(p){}ref operator*(){return pnode->data;}ptr operator->(){return &pnode->data;}//前置Self& operator++(){pnode = pnode->next;return *this;}//后置Self operator++(int){Self tmp(pnode);pnode = pnode->next;return tmp;}//前置Self& operator--(){pnode = pnode->prev;return *this;}//后置Self operator--(int){Self tmp(pnode);pnode = pnode->prev;return tmp;}bool operator!=(const Self& it){return pnode != it.pnode;}bool operator==(const Self& it){return pnode == it.pnode;}
};template<class T>class list{public:typedef list_node<T> node;typedef list_iterator<T, T&, T*> iterator;typedef list_iterator<T, const T&, const T*> const_iterator;iterator begin(){//匿名对象返回！return iterator(head->next);}const_iterator begin()const{return const_iterator(head->next);}const_iterator end()const{return const_iterator(head);}iterator end(){return iterator(head);}void clear(){iterator first = begin();while (first != end()){first = erase(first);//!!!}}~list(){clear();delete head;head = nullptr;}void empty_initialize(){head = new node;head->next = head;head->prev = head;}list(){empty_initialize();}template <class InputIterator>list(InputIterator first, InputIterator end){empty_initialize();while (first != end){push_back(*first);++first;}}void swap(list<T>& lt){std::swap(head, lt.head);}list(const list<T>& lt){empty_initialize();list<T> tmp(lt.begin(), lt.end());swap(tmp);}list<T>& operator=(list<T> tmp){swap(tmp);return *this;}void push_back(const T& x){insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_front(){erase(begin());}void pop_back(){erase(--end());}void insert(iterator pos, const T& x){node* newnode = new node(x);node* cur = pos.pnode;node* prev = cur->prev;prev->next = newnode;newnode->prev = prev;cur->prev = newnode;newnode->next = cur;}iterator erase(iterator pos){node* cur = pos.pnode;node* prev = cur->prev;node* next = cur->next;prev->next = next;next->prev = prev;delete[]cur;return iterator(next);}private:node* head;//底层是一个哨兵结点};

---