拖更了半个月，我终于来填c++的坑啦。上次我们说的vetcor不知道小伙伴还记得多少呢？今天我们要讲list的模拟实现。

架构

我们之前也写过c语言版本的链表，当时很麻烦，还要传二级指针。但是现在不用了引用就能解决。我们先把大体的架构搭出来。

结点

list是一个个的结点指针链接，而且我们看手册的时候，会发现ist是一个双向带头的链表。所以我们先写节点的代码加粗样式。

template<class T>
struct ListNode
{
//为什么要用struct？其实用class也ok，但是要整个public，因为节点我希望你可以随时申请，所以不能弄成私有。ListNode(const T& val=T()):_prev(nullptr),_next(nullptr),data(val){}ListNode<T>* _prev;//为什么是ListNode<T>*的指针呢？因为我们将来要指向//ListNode<T>类型的节点。ListNode<T>* _next;T data;
};

list表的结构

我们也说了是双向带头链表，所以list一定要有头结点。

template<class T>class list{public:typedef ListNode<T> Node;private:Node* _head;//头结点是一个节点指针类型。size_t _size;//因为库中有size这个接口，这里存一个会方便一点。};

构造函数

在我们之前实现过得带头双向链表，在刚开始的时候，就是对头结点进行处理，让头结点的前后指针指向自己。

	list(){_head = new Node;//给头一个空间_head->_prev = _head;_head->_next = _head;_size = 0;}

尾插push_back()

尾插，我们很熟悉了。就是先new出一个节点的大小，然后把这个节点连接到链表的尾部。如图：

void push_back(const T& val)
{Node* node = new Node(val);//申请节点Node* tail = _head->_prev;//如何找到4？是_head->prev！保存起来方便我们使用。node->_prev = tail;//链接node->_next = _head;tail->_next = node;_head->_prev = node;_size++;//修改size
}

尾删pop_back()

尾删也是老朋友了。话不多说如图：

简单叙述过程：就是先找到尾巴，然后保存一起来(方便我们删除)。然后将指针链接到尾删的前一个值。

void pop_back()
{Node* tail = _head->_prev;//保存_head->_prev = tail->_prev;//更改指向tail->_prev->_next = _head;delete tail;//删除节点_size--;//别忘了修改个数
}

计算个数：size()

这个就很简单了，因为我们内置了个数，所以直接返回就好了。

size_t size()
{return _size;
}

判断空empty()

bool empty()
{return _size == 0;
}

※迭代器问题

链表的迭代器很麻烦，不像vector那样用下标访问就可以的我们先把迭代器的主体写出来，分析一下，我们都需要什么吧。

bit::list<int>::const it = lt2.begin();
while (it != lt2.end())
{std::cout << *it << " ";it++;
}

我们平时访问数据的时候就这些，例如：迭代器本身、*星号、begin()、end()、自增++。那怎么写呢？

普通迭代器

问题：迭代器本身怎么写，还用T* 吗？写在list中码？(一定要思考这个问题！)

---

答案：不不不，我问你的自增，你在增谁？增加的list还是迭代器？我们要写operator++()，你一定要明白是谁在++。如果你把迭代器写到list中，你operator++()自增的是谁？一定要把这个问题想清楚。

自增的迭代器本身。那么我们的自增就不能写到list中，也就表示迭代器不能写在list中。那么我们就需要另外写一个类封装了。OK！开写！

迭代器主体

我们要遍历这个list链表的时候，我们一定要有这个地方的节点指针，我们才能访问这里的数据对吧，所以里面的成员变量是Node* _node;

template<class T>
class List_Iterator
{
public:typedef ListNode<T> Node;Node* _node;List_Iterator(Node* node):_node(node){}
};

begin()和end()

begin()和end()多好写，begin()是返回数据的开始和end()返回头结点(有效数据的下一个)。

问题：你写在哪？list类？还是iterator类？
答：思考一下，你的数据在哪？你的数据在list 里面对吧，我要访问遍历数据，我去哪里拿数据？list中，那么你的begin()和end()一定不能写在iterator。begin()和end()应该写在list中。

template<class T>class list{public:typedef ListNode<T> Node;iterator begin(){//这里存在单参数构造函数的隐式类型转换//按道理 return iterator(_head->next);//应该是这样的，匿名对象，但是单参数的构造函数可以进行隐式类型转换。return _head->_next;}iterator end(){return _head;}private:Node* _head;//头结点是一个节点指针类型。size_t _size;//因为库中有size这个接口，这里存一个会方便一点。};

operator*()

因为我们遍历一般都是要打印出它的值，所星号也是必不可少的。星号表示解压用。那么我们只需要返回当前节点的值就可以了。

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

前置++ operator++()

自增很简单，我们只需要下一个节点的指针就好，那么我们怎么找到下一个节点呢？是不是当前节点的_next?那就更简单了。

List_Iterator<T>& operator++()
{//this->_node= this->_node->_next;_node= _node->_next;return *this;
}

后置++ operator++(int)

后置++，就是我们创建一个临时变量，然后返回临时变量，但是让实际已经指向下一个节点了。注：不能返回引用，因为是临时变量。

List_Iterator<T> operator++(int)
{List_Iterator<T> tmp(*this);_node = _node->_next;return tmp;
}

前置-- operator–()

为什么要重载自减呢？是因为有些地方我们还是有需要的，所以就直写了。

List_Iterator<T> & operator--()
{_node= _node->_prev;return *this;
}

后置-- operator–(int)

List_Iterator<T> operator--(int)
{Self tmp(*this);_node = _node->_prev;return tmp;
}

重载不等于 operator!=(const Self& rhs)

问题：在比较的时候，我们比的是节点指针还是数值呢？
答：节点指针！数值可能重复。

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

重载箭头 operator->()

为什么要重载operator->？我们一直用int内置类型来作为样例，这没有问题，但是我想问你，你的list只存int吗？没有自定义类型吗？如果我希望能存一个student类呢？可能你说(*it).成员变量也可以啊，但是你觉得方便吗？所以我们要重载->。

箭头的运算符重载：

从图上我们能发现，他隐藏了一个箭头，他应该是it.operator->()->_a1;但是事实上只有意见箭头，就表明了，他隐藏了一个箭头。

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

const迭代器问题

以上，我们用的都是普通的迭代器，那么const迭代器怎么写呢？你会说，我知道了！只要让他不改变不就好了？OK！说干就干。显示就是，依然改了，并没有用。

解决方法一：创建新的类。

问题就出在了你迭代器本身，你的返回值依然是普通的，我依然可以改。那你突然灵光一现，我在写一个const_ListIterator类就好了！好说干就干。你用了一下，真好用。但是你有没有发现代码很冗余？唯独只有operator*()和operator->()的返回值改变了，因为在拿取值的时候，我们要返回const类型的。

template<class T>
class List_ConstIterator
{
public:typedef ListNode<T> Node;typedef List_ConstIterator<T> Self;Node* _node;List_ConstIterator(Node* node):_node(node){}//前置++Self& operator++(){_node = _node->_next;return *this;}//后置++Self operator++(int){Self tmp(*this);_node = _node->_next;return tmp;}//前置--Self& operator--(){_node = _node->_prev;return *this;}//后置--Self operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const Self& rhs)  {return rhs._node != _node;}bool operator==(const Self& rhs){return _node == rhs._node;}const T& operator* (){return _node->data;}const T* operator->(){return &_node->data;}
};

解决方法二：模板

我们上面也说只是两个成员函数的返回类型不同，那么我们在处理返回类型不同的时候怎么做的呢？对！就是模板！模板是不是可以传不同类型呀？那么我们就只需要改一下。

list类中：

template<class T ,class Ref ,class Ptr>
class List_Iterator
{
public:typedef ListNode<T> Node;typedef List_Iterator< T, Ref, Ptr> Self;Node* _node;List_Iterator(Node* node):_node(node){}//前置++Self& operator++(){_node= _node->_next;return *this;}//后置++Self operator++(int){Self tmp(*this);_node = _node->_next;return tmp;}//前置--Self& operator--(){_node= _node->_prev;return *this;}//后置--Self operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const Self& rhs ){return rhs._node != _node;}bool operator==(const Self& rhs){return _node == rhs._node;}Ptr operator->(){return &_node->data;}Ref operator* (){return _node->data;}
};

在某个位置前插入 insert()

库中给我们了三种，我们只实现第一种。需要迭代器类型的pos和 T val。刚好迭代器问题我们刚刚解决。

连接方式，如图：

iterator insert(iterator pos, const T& val)
{//我写的不美观Node* node = new Node(val);Node* tmp=pos._node->_prev;tmp->_next = node;node->_prev = tmp;node->_next = pos._node;pos._node->_prev = node;_size++;return _head;// Node* node = new Node(val);// Node* prev=pos->prev;// node->prev=prev;// node->next=pos;// pos->prev=node;// prev->next=node;// _size++;// return _head
}

删除某位置的值 erase()

这里我们要注意，库中要求返回被删除值的下一个的迭代器。

		iterator erase(iterator pos){//不美观版本assert(pos != end());//这里我担心有人有人恶意传迭代器，所以就判断了一下。Node* tmp = pos._node->_prev;tmp->_next = pos._node->_next;pos._node->_next->_prev = tmp;delete pos._node;_size--;return tmp->_next;/*美观版本Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;return next;*/}

清空链表 clear()

注意，我们清空的链表，不需要清头指针，所以直接用迭代器，pop_back()就可以了。

void clear()
{iterator it = begin();while (it != end()){it = erase(it);}_size = 0;
}

拷贝构造

拷贝构造这里有几个问题。

问题1：直接push_back()可以吗？
答：不可以。你的头指针没有初始化，都是空，插入直接空指针访问。所以你需要初始化。
问题2：用我注释部分的迭代器可以吗？
答：不行，如果你传进来是一个const类型的迭代器呢？普通迭代器类型不匹配，除非你用auto。

//lt1(lt2)
list(const list<T>& lt)
{empty_init();//初始化头结点。for (auto& e : lt){push_back(e);}iterator it = lt.begin();类型不明确，用范围for更好//auto it = lt.begin();//这样也可以//while (it != lt.end())//{//	push_back(*it);//	it++;//}
}

析构函数

释放空间，并且还有头结点！！！有些小伙伴以为只用释放各个数据的节点就可以了，但是头结点也是你开出来的空间啊，所以也要记得释放。

~list()
{clear();//复用delete _head;
}

问题

如果我什么都写了，只有拷贝构造没有写，下面图代码对吗？

答：不对，因为传值传参回去调用拷贝构造，没有写拷贝构造就是浅拷贝，当函数结束 临时对象会被析构。但是浅拷贝导致本对象被析构，当整体结束的时候会导致二次析构。

实现整体代码

#pragma once
#include<iostream>
#include<assert.h>namespace bit {template<class T>struct ListNode{ListNode(const T& val=T()):_prev(nullptr),_next(nullptr),data(val){}ListNode<T>* _prev;//为什么是ListNode<T>*的指针呢？因为我们将来要指向//ListNode<T>类型的节点。ListNode<T>* _next;T data;};template<class T ,class Ref ,class Ptr>class List_Iterator{public:typedef ListNode<T> Node;typedef List_Iterator< T, Ref, Ptr> Self;Node* _node;List_Iterator(Node* node):_node(node){}//前置++Self& operator++(){_node= _node->_next;return *this;}//后置++Self operator++(int){Self tmp(*this);_node = _node->_next;return tmp;}//前置--Self& operator--(){_node= _node->_prev;return *this;}//后置--Self operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const Self& rhs ){return rhs._node != _node;}Ref operator* (){return _node->data;}bool operator==(const Self& rhs){return _node == rhs._node;}Ptr operator->(){return &_node->data;}};//template<class T>//class List_ConstIterator//{//public://	typedef ListNode<T> Node;//	typedef List_ConstIterator<T> Self;//	Node* _node;//	List_ConstIterator(Node* node)//		:_node(node)//	{}//	//前置++//	Self& operator++()//	{//		_node = _node->_next;//		return *this;//	}//	//后置++//	Self operator++(int)//	{//		Self tmp(*this);//		_node = _node->_next;//		return tmp;//	}//	//前置--//	Self& operator--()//	{//		_node = _node->_prev;//		return *this;//	}//	//后置--//	Self operator--(int)//	{//		Self tmp(*this);//		_node = _node->_prev;//		return tmp;//	}//	bool operator!=(const Self& rhs)  //	{//		return rhs._node != _node;//	}//	const T& operator* ()//	{//		return _node->data;//	}//	bool operator==(const Self& rhs)//	{//		return _node == rhs._node;//	}//	const T* operator->()//	{//		return &_node->data;//	}//};template<class T>class list{public:typedef ListNode<T> Node;typedef List_Iterator<T, T&, T*> iterator;typedef List_Iterator<T, const T&, const T*> const_iterator;//typedef List_Iterator<T> iterator;//typedef List_ConstIterator<T> const_iterator;void empty_init(){_head = new Node;//给头一个空间_head->_prev = _head;_head->_next = _head;_size = 0;}list(){empty_init();//刚创建一个链表的时候，没有插入任何数据，我们需要让他指向自己}~list(){clear();delete _head;}//lt1(lt2)list(const list<T>& lt){empty_init();for (auto& e : lt){push_back(e);}iterator it = lt.begin();类型不明确，用范围for更好//auto it = lt.begin();//这样也可以//while (it != lt.end())//{//	push_back(*it);//	it++;//}}void push_back(const T& val){/*Node* node = new Node(val);Node* tail = _head->_prev;node->_prev = tail;node->_next = _head;tail->_next = node;_head->_prev = node;*/insert(end(), val);}void pop_back(){/*Node* tail = _head->_prev;_head->_prev = tail->_prev;tail->_prev->_next = _head;delete tail;*/erase(--end());}//当我们想使用insert的时候，发现需要迭代器那么我们先实现迭代器，怎么做呢？iterator begin(){//这里存在单参数构造函数的隐式类型转换//return _head->_next;}iterator end(){return _head;}const_iterator begin()const{//这里存在单参数构造函数的隐式类型转换return _head->_next;}const_iterator end()const{return _head;}//目前测试的迭代器没有大碍，那么就写insertiterator insert(iterator pos, const T& val){//我写的不美观Node* node = new Node(val);Node* tmp=pos._node->_prev;tmp->_next = node;node->_prev = tmp;node->_next = pos._node;pos._node->_prev = node;_size++;return _head;// Node* node = new Node(val);// Node* prev=pos->prev;// node->prev=prev;// node->next=pos;// pos->prev=node;// prev->next=node;// _size++;// return _head}iterator erase(iterator pos){//我写的不美观assert(pos != end());Node* tmp = pos._node->_prev;tmp->_next = pos._node->_next;pos._node->_next->_prev = tmp;delete pos._node;_size--;return tmp->_next;//老师写的/*Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;return next;*/}size_t size(){return _size;}bool empty(){return _size == 0;}void clear(){iterator it = begin();while (it != end()){it = erase(it);}_size = 0;}private:Node* _head;size_t _size;};
}