STL中list的模拟实现

1. 前言and框架

首先，我们要明白list的本质是什么，list的本质是带头双向循环链表

• 注意事项

1. 类模板的声明：在类前面加一个模板template<class T>即可
2. 需要创建一个类list，但list的底层是带头双向循环链表。链表则需要结点，那我们就还需要创建要给结点的类。【总结：就是在列表list中有一个头结点的指针。一个结点里面又会有数据，前一个，后一个结点指针】
3. 这是自己模拟实现的，则需要有命名空间，否则编译器会调用库里的list
4. 如果类里面的内容都是公有的，那么则可以使用struct。有公有和私有，那么使用class（这是惯例，但不是规定）。在struct中，如果没有对某个内容用限定符修饰，那么它就是私有。
5. 一共两个类。list_node(结点)和list(列表）

namespace hou
{template<class T>struct list_node{//在list_node中，存放这个结点的数据，前一个和后一个结点指针，T _data;list_node<T>* _next;list_node<T>* _prev;};template<class T>class list{typedef list_node<T> Node;private:Node* _head;};
}

6. typedef list_node<T> Node;这一步是为了防止大家忘记写模板参数< T>。
   在class中，class没有用限定符修饰，是私有的。因此，只有在这个类里面才可以用Node，在这个类里面Node才代表list_node<T>.

7. 为什么list_node的所有成员全部对外开放？
   因为链表list在增删查改的时候需要高频地控制list_node的成员变量。如果list_node的成员都私有的话，则需要友元函数，比较麻烦。
   但是全部对外开放，不害怕别人修改你的数据吗？
   其实是很难修改的。我们在使用list的时候，是感知不到底层的结点，哨兵位之类的东西的。我们只是看到了它的各种接口，可以感知到它是双向的。想修改内容，需要知道变量的名称，命名空间的名字。所以，虽然开放，但是也安全。

8. list中大部分用迭代器。在此之前，有迭代器失效这个概念，这里也会出现。但string中也有迭代器失效，但比较少，因为大部分用下标访问，较少使用迭代器。vector也有迭代器失效。

2. 相对完整的框架

1. 牢记牢记牢记：为了方便，我们已经将list_node<T>在list这个类里面typedef为Node。
2. 给list构造（无参）：

		void empty_init(){_head = new Node();   //_head的类型是Node*(也就是list_node<T>)结点的指针_head->_prev = _head;_head->_next = _head;}list(){empty_init();}

3. list_node的构造

		list_node(const T& x = T()):_data(x),_next(nullptr),_prev(nullptr){}

4. 迭代器
   面向对象的三大特征：封装，继承，多态。
   封装可以用类和迭代器来实现。（它可以用来“屏蔽底层的实现细节，屏蔽个容器的结构差异，本质是封装底层细节和差异，提供同一的访问方式）

只需要提供一个结点即可

namespace hou
{template<class T>struct list_node{T _data;list_node<T>* _next;list_node<T>* _prev;list_node(const T& x = T()):_data(x),_next(nullptr),_prev(nullptr){}};template<class T>struct list_iterator{typedef list_node<T> Node;Node* _node;}; template<class T>class list{typedef list_node<T> Node;public:typedef list_iterator<T> iterator; void empty_init(){_head = new Node();   //_head的类型是Node*(也就是list_node<T>)结点的指针_head->_prev = _head;_head->_next = _head;}list(){empty_init();}private:Node* _head;};
}

3. 模拟实现接口

1. 迭代器的引入

把原生指针直接命名为迭代器？迭代器的价值在于封装底层，不具体暴露底层的实现细节，提供统一的访问方式。（比如：在使用list的时候，我们并不能知道底层的结点，哨兵位之类的，这就是对底层的封装，不暴露底层的细节）

迭代器有两个特征：解引用，++/–

vector和string类，它的物理空间是连续的（那原生指针就可能是迭代器），那解引用得到的就是数据了。但对于空间不连续的list，那解引用是得不到数据的（node*解引用是node，并不是数据）。
既然空间已经是不连续了，更不用说++指向下一个结点了

所以，对于list的迭代器，原生指针已经不符合我们的需求了，我们需要去进行特殊处理：进行类的封装。我们可以通过类的封装以及运算符重载支持，这样就可以实现像内置类型一样的运算符。

2. 迭代器的区分

迭代器也分为普通迭代器和const迭代器。

何时用const的迭代器呢？当const的容器想用迭代器的时候，必须用const的迭代器。【注：const修饰之后，只有在定义的时候才有初始化的机会，可以在定义的时候进行push_back();】

但首先我们要先明白const是在 *左边，还是 *右边呢？

const int* p1;  //左定值
int* const p2;  //右定址

const在int*前面，则是修饰p1所指向的内容（int*这个类型）。const在int*的后边，在p2的前面，则const是在修饰p2这个迭代器（可能是指针）【左定值，右定址】

那么在list的const迭代器中，const修饰谁呢？
在while中，有一个步骤是将迭代器++，这个步骤就决定了const不是用来修饰迭代器/地址/指针，因为迭代器还要++呢，所以const迭代器类似于模拟p1的行为，保护指向的对象不被修改，迭代器本身可以修改。

迭代器的实现我们需要去考虑普通迭代器和const迭代器。这两种迭代器不同，也会带来不同的接口，我们先去分开实现(提供一个结点即可)

list迭代器

迭代器的构造

这里list的迭代器并不是原生指针，而是用一个类封装的。

一个类型的构造函数是用来构造自己类型的对象的，迭代器类型要构造迭代器对象就需要构造函数。

	template<class T>struct list_iterator   //struct代表着：全开放{typedef list_node<T> Node;Node* _node;   //迭代器中的一个成员变量（公有）list_iterator(Node* pnode):_node(pnode){}};

list迭代器的实现

template<class T>
struct list_iterator
{typedef list_node<T> Node;Node* _node;list_iterator(Node* pnode):_node(pnode){}
}; 

模拟指针

解引用

		T& operator*(){return _node->_data;  //返回此结点的值}

前置++和前置–

即想要下一个结点的数据（但之前的地址++是不可取的，list的物理空间不连续），那我们可以让结点变成结点的_next

		Self& operator++(){_node = _node->_next;return *this;}Self& operator--(){_node = _node->_prev;return *this;}

后置++和–

就是要给这个变量++和–，但是此刻用的还是没有经过++和–的值

		Self operator++(int a){Self tmp(*this);//Self是list_iterator<T>_node = _node->_next;return tmp;}Self operator--(int a){Self tmp(*this);//Self是list_iterator<T>_node = _node->_prev;return tmp;}

迭代器！=

判断迭代器是否相等，就需要看这两个迭代器所指向的结点是否相等。

谁是begin()，第一个结点。谁是end()，哨兵位是。

		bool operator!=(const Self& s){return _node != s._node;}

迭代器->

.是直接访问对象的成员（类访问成员就用. 【调用类中的成员函数和成员变量：用. 】）
->是通过对象的指针访问成员。

		T* operator->(){return &_node->_data;}

list的const迭代器

我们需要再实现一个单独的类，叫做list_const_iterator吧。这个与普通迭代器不同的是类名不同，operator*和operator->的返回值类型不同

	template<class T>struct list_const_iterator{typedef list_node<T> Node;typedef list_const_iterator<T> Self;Node* _node;   //迭代器中的一个成员变量（公有）list_const_iterator(Node* pnode):_node(pnode){}const T& operator*(){return _node->_data;  //返回此结点的值}const T* operator->(){return &_node->_data;}Self& operator++(){_node = _node->_next;return *this;}Self& operator--(){_node = _node->_prev;return *this;}Self operator++(int a){Self tmp(*this);//Self是list_iterator<T>_node = _node->_next;return tmp;}Self operator--(int a){Self tmp(*this);//Self是list_iterator<T>_node = _node->_prev;return tmp;}bool operator!=(const Self& s){return _node != s._node;}};

迭代器模板

普通迭代器返回T&，可读可写，const迭代器返回const T&,可读不可写，上面的代码存在很大的问题：代码冗余，所以我们应该去解决这个问题：我们可以参考源码的实现：类模板参数解决这个问题，这也是迭代器的强大之处。

只有几个地方不一样，代表着普通和const迭代器高度相似。那我们可以用同一个类模板实现它们俩个（同一个类模板，只要我们传递不同的参数实例化成不同的迭代器

记得将list中的也修改

	//typedef list_iterator<T,T&,T*> iterator;//typedef list_iterator<T,const T&,const T*> iterator; template<class T,class Ref,class Ptr>struct list_iterator{typedef list_node<T> Node;typedef list_iterator<T, Ref, Ptr> Self;Node* _node;Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}Self& operator++(){_node = _node->_next;return *this;}Self& operator--(){_node = _node->_prev;return *this;}Self operator++(int){Self tmp(*this);_node = _node->_next;return tmp;}Self operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const Self& s){return _node != s._node;}bool operator==(const Self& s){return _node == s._node;}};

迭代器是否需要析构，拷贝构造，赋值重载

1. it访问完该结点，不可能将该结点释放掉，所以list迭代器不需要析构函数（迭代器只是通过这个系欸但访问，修改这个容器，释放结点是链表的事情
2. 不析构------>那么也不需要拷贝构造和赋值重载（迭代器的拷贝构造和赋值重载我们并不需要自己去手动实现，编译器默认生成的就是浅拷贝（迭代器只是一个用来访问元素的工具，拷贝迭代器，也只是复制出了一个一模一样的工具，所以是浅拷贝），而我们需要的就是浅拷贝，这也说明了，并不是说如果有指针就需要我们去实现深拷贝。另外，迭代器通过结构体指针访问修改链表，所以，对于迭代器我们并不需要构造函数，结点的释放由链表管理。

3. 迭代器begin()，end()

谁是begin()，第一个结点。谁是end()，哨兵位是。

		iterator begin(){return iterator(_head->_next);//调用迭代器构造list_iterator(Node* pnode)}iterator end(){return iterator(_head);//调用迭代器构造list_iterator(Node* pnode)}

2. push_back

第一种实现方式：
在链表中新插一个结点。

原来的最后一个tail(_head->prev)指向新结点。
新结点的_prev指向之前的最后一个（即tail）
新结点的_next指向第一个（即_head）
哨兵位的前一个指向新结点

		void push_back(const T& x){Node* newnode = new Node(x);Node* tail = _head->_prev;tail->_next= newnode;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;}

第二种实现方式：
可以先不实现头插/头删，先实现insert/erase，可以用这个实现头插/头删。

3. insert和erase

这两个都是写在list中的，因为插入或删除链表中的结点。

1. insert可以在任意位置插入数据，无论是最后一个结点的前面还是哨兵位的前面都可以插入。（在哨兵位插入数据，哨兵位前一个不就是最后一个数据）
2. Return value：An iterator that points to the first of the newly inserted elements.（返回值：指向第一个新插入元素的迭代器）
3. erase不可以删除哨兵位的数据
4. Return value：An iterator pointing to the element that followed the last element erased by the function call. This is the container end if the operation erased the last element in the sequence.（返回值：一个迭代器（这个迭代器指向，通过函数调用函数所删除的元素的下一个元素（fallowed紧跟着，也就是下一个）如果删除了序列的最后一个元素，这就是容器的结尾）

重点：erase记得最后删除那个结点

4.push_back,push_front,pop_back,pop_front

返回值：none

push_back是尾插

插入insert是将position这个位置换成插入的结点，那不就是position在插入结点之后吗，那end()的前面就是最后一个结点。

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

头插push_front是在哨兵位之后，第一个结点之前。（第一个结点也就是lt.begin();)

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

尾删（返回值：none）

void pop_back()
{erase(iterator(end()--);
}
void pop_front()
{erase(begin());
}

构造

1. 默认构造

2. 迭代器区间构造

	    //迭代器区间构造template <class InputIterator>list(InputIterator first, InputIterator last){empty_init();while (first != last){push_back(*first);++first;}}

3. 拷贝构造(深拷贝)

在使用时的样子：lt2(lt1);

		list(const list<T>& lt){empty_init();for (const auto& e : lt){push_back(e);}}

用范围for进行尾插，但是要注意要加上&，范围for是*it赋值给给e，又是一个拷贝，e是T类型对象，依次取得容器中的数据，T如果是string类型，不断拷贝，push_back之后又销毁。

现代写法：

先使用迭代区间构造（值也一样），再将两个结点的头结点交换（头结点不同，那指向的下一个结点也就不一样了）

void swap(list<T>& lt)
{std::swap(_head, lt._head);
}		
list(const list<T>& lt)
{empty_init();list<T> tmp(lt.begin(), lt.end());swap(tmp);
}

4. 析构

对于list，有单独的clear()接口，list的析构可以直接复用clear()，同时还需要我们去释放掉头结点：

同时，我们也要知道clear()和~list()有什么区别
clear()只是将来自list容器的所有元素移除，再将size修改为0【clear()所有结点删除，哨兵位不动】
~list会将所有结点+哨兵位都删除

		~list(){clear();//哨兵位也释放掉delete _head;_head = nullptr;}void clear(){iterator it = begin();while (it != end()){it = erase(it);//erase()函数会返回(所删除元素)的下一个元素的迭代器,就相当于++了}}

赋值重载

传统：

		list<T>& operator=(list<T>& lt){if (this != &lt){clear();for (const auto& e : lt){push_back(e);}}return *this;}

现代：

若是想lt2=lt3；，需要先释放lt2，可以将参数改为list<T> lt;
先将lt3拷贝给给lt（lt和lt3有一样大的空间，一样大的值），这个时候可以将lt和lt2交换（这样子lt2时lt的内容，即和lt3一模一样。但同时lt3也没有被修改）

		list<T>& operator=(list<T> lt){swap(lt);return *this;}

4. list和vector对比

vector:vector的优点在于下标的随机访问，尾插尾删效率高，CPU高速缓存命中高。而缺点在于前面部分插入删除数据效率低O(N)，扩容有消耗，还存一定空间浪费。

list:list的优点在于无需扩容，按需申请释放，在任意位置插入删除O(1)。缺点在于不支持下标的随机访问，CPU高速缓存命中低。

vector和list的关系就像是在互补配合！

而对于string的insert和erase迭代器也会失效跟vector类似。但是我们并不太关注。因为string的接口参数大部分是下标支持，迭代器反而用得少。