自我名言：只有努力，才能追逐梦想，只有努力，才不会欺骗自己。
喜欢的点赞，收藏，关注一下把！

库里面的list类模板，实现的是带头双向循环链表。这里我们和库实现的是一样的。

1.链表结点

这里链表结点实现的是一个模板，因为我们并不知道别人想在结点里放什么数据。

其次库里面结点指针是void*，而我们和库里面有一些细微差别，

//链表结点
template<class T>
struct __list_node
{__list_node* _prev;__list_node* _next;T _date;
};
//struct和class一样，也可以是类关键字，并且里面的成员变量和成员函数默认都是public的。

2.类模板基本框架

template<class T>
class List
{//每次都要写太长了，所以typedef一下typedef __list_node<T> node;
public:private:node* —_head;
};

3.构造

template<class T>
struct __list_node
{__list_node* _prev;__list_node* _next;T _date;__list_node(const T& val):_prev(nullptr),_next(nullptr),_date(val){}
};//构造list(){//new对自定义类型会调用它的构造函数，因此，结点类必须要有一个构造_head = new node(T());_head->_prev = _head;_head->_next = _head;}

4.插入+普通迭代器实现

4.1尾插

	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;}

4.2普通迭代器实现

这使用库里面的iterator,遍历链表。

注意list遍历只能用迭代器，或者范围for(底层是迭代器)，不能用下标+[]，因为vector物理结构是数组，而list底层是一个个按需申请的结点。

接下来我们自己实现一个迭代器。遍历链表。
首先来认识认识迭代器。

std::list<int>::iterator it = It.begin();

链表结点是一个个申请的，而vector和stirng是一次就申请连续的空间。

由于在前面学过封装，这里我们可以把指针封装起来，并且加上运算符重载（* ，++， !=）来支持，迭代器的行为。

template<class T>
struct __lsit_iterator
{typedef __list_node<T> node;node* _pnode;T& operator*(){return _pnode->_date;}__lsit_iterator<T>& operator++(){_pnode = _pnode->_next;return *this;}bool operator!=(const __lsit_iterator<T>& It){return _pnode != It._pnode;}
};

//迭代器
iterator begin()
{//这里是匿名构造，但是__list_iterator缺少了构造，所以增加一下return iterator(_head->_next);
}iterator end()
{return iterator(_head);
}

普通迭代器部分模板

template<class T>
struct __lsit_iterator
{typedef __list_node<T> node;node* _pnode;__lsit_iterator(node* _node):_pnode(_node){}T& operator*(){return _pnode->_date;}__lsit_iterator<T>& operator++(){_pnode = _pnode->_next;return *this;}bool operator!=(const __lsit_iterator<T>& It){return _pnode != It._pnode;}
};

我们使用自己的iterator，结果也是正确的。这里不太懂得，可以调试一下，帮助理解。

4.3对比list和vector的iterator

iteratorr------->1.内置类型 2.行为像指针一样。
范围【begin(),end())

list，vector迭代器上层使用都是一样的。但是它们底层实现不一样。list的迭代器是自定义类型（封装+运算符重载），但vector的迭代器并不一定就是内置类型（原生指针）。

就如在linux环境和vs环境下，erase后pos位置失效不失效的问题，在linux环境下pos不失效，而vs环境下pos失效，这是因为在两个不同环境下，iterator底层实现是不一样的。linux下iterator是原生指针，vs对vector的iterator和list的iterator一样，都是指针的封装。所以iterator不一定就是指针

为什么vector和list这里都用" != “，而不是” < "呢？

这是因为，vector的物理结构（数组）可以满足" < "，但是list的物理结构并不能确定前一个结点与后一个结点位置谁大谁小，所以统一用 " != "，可以满足不同容器的迭代器。

4.4迭代器的价值

1.封装底层实现，不暴露底层的实现细节。
2.提供统一的访问方式，降低使用成本。

迭代器是一种框架，可能代码我们都会写，但是这种框架思维是最重要的。

从物理层面上看，vector和list的iterator物理结构都是指针，请问大小是几个字节呢？

vector迭代器是一个原生指针，list迭代器是一个指针类模板，类的大小是成员变量的大小+内存对齐，list迭代器我们就放一个node*指针，我们知道32位指针大小为4，64位指针大小为8；所以大小都是4/8字节。

虽然iterator变化都是指针的变化，但是它们的类型是不一样的，vector的iterator是内置类型（原生指针），list的iterator是自定义类型，编译器根据类型的不同所走的方式不同，list的iterator走的是调用函数，如++it，调用it.operator++()再把结构返回来，而vector直接使用，指针直接像后走4个字节。。这就是类型的力量。

4.5insert

	iterator insert(iterator pos, const T& val){node* newnode = new node(val);node* cur = pos._pnode;node* prev = cur->_prev;prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;return iterator(newnode);}

4.6尾插头插复用写法

	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(end(), x);}void push_front(const T& x){insert(begin(), x);}

5.删除+erase

5.1erase

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;//返回pos下一个位置return iterator(next);}

5.2尾删头删复用写法

	__List_iterator<T>& operaotr--(){_pnode = _pnode->prev;return *this;}void pop_back(){//iterator没有实现--运算符重载，所以补充一下erase(--end());}void pop_front(){erase(begin());}

6.析构+empty+size+clear

6.1clear

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

6.2size

//一般想法就是遍历，统计一下个数，但是我们这里可以增加一个_size成员遍历，来统计个数
//然后再返回这个变量即可
//成员变量增加一个_size,构造都要改，但是我们实现了empty_initialize(),只要修改这里就可以void empty_initialize(){_head = new node(T());_head->_prev = _head;_head->_next = _head;_size = 0;}size_t size() const{return _size;}
//插入和删除也需要相应的把_size加上。

6.3 empty

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

6.4 析构

	~List(){clear();delete _head;_head = nullptr;}

7.拷贝构造+赋值运算符重载

7.1拷贝构造写法

	//拷贝构造传统写法List(const List<T>& it){//由于构造+拷贝构造+赋值都要有这样写法,为了减少代码冗余//专门写一个empty_initialize()//_head = new node(T());//_head->_prev = _head;//_head->_next = _head;empty_initialize();for (auto e : it){push_back(e);}}

但是这样写有一个问题。
list T是泛型， 如果T放的是内置类型还好说，但如果T放的是自定义类型，这里还涉及拷贝构造和析构。因此正确写法如下。

	//拷贝构造传统写法List(const List<T>& it){empty_initialize();//加个引用for (auto& e : it){push_back(e);}}

但是这样写，还是有问题，it是const修饰的对象，范围for变量底层是迭代器，走的是const的迭代器。但是在__List_iterator 还没有实现。这里先把拷贝构造和赋值写完，就说这个问题。

在string和vector模拟实现，拷贝构造和赋值运算符重载最终都用现代写法来实现。现代写法的主要思想：就是自己的事情让别人干，然后再交换一下。

拷贝构造现代写法复用构造函数

前面实现的是一个无参构造，想要复用构造函数，必须要实现这个一段区间的构造函数。

	template <class InputIterator>List(InputIterator first, InputIterator last){empty_initialize();while (first != last){push_back(*first);++first;}}

	void swap(List<int>& x){std::swap(_head, x._head);std::swap(_size,x._size);}//拷贝构造现代写法List(const List<T>& it){//这里必须要申请带头结点，不然交换就会野指针，tmp析构的是就会报错//也不能直接给_head(nullptr)，这样tmp析构也会报错empty_initialize();List<T> tmp(it.begin(), it.end());swap(tmp);}

7.2赋值运算符重载

	//传统写法List<T>& operator=(const List<T>& it){if (this != &it){//this->clear()clear();for (auto& e : it){//this->push_back(e);push_back(e);}}return *this;}

赋值运算符重载现代写法的思想：复用拷贝构造函数

	//赋值现代写法//it这里调用拷贝构造函数List<T>& operator=(List<T> it){swap(it);return *this;}

虽然现在已经实现了拷贝构造和赋值运算符重载，但是迭代器没有实现const iterator 上面代码都会报错。

接下来实现const迭代器

8.const迭代器

回想一下vector实现的const迭代器

	typedef T* iterator;typedef const T* const_iterator;

	List<int>::iterator it = It.begin();//可能会以为在前面加上const 就是const迭代器了，但这样是不对的const List<int>::iterator it = It.begin();

我们知道const修饰指针有不同位置

//const修饰*p1，*p1内容不能改变，p1指针可以改变const T* p1
//const修饰p2，p2指针不能改变，*p2内容可以改变T* const p2

而const迭代器类似p1的行为，保护指向对象不能改变，迭代器本身可以修改

//不符合迭代器的行为，因为它保护迭代器 本身不能修改，那么就不能++/--迭代器const List<int>::iterator it = It.begin();

所以考虑一下，放在__List_iterator中；

	//iterator it//*it//++itT& operator*(){return _pnode->_date;}//可能还会想这样写，const修饰指针*this//const iterator* const this  这样*this就不会改变了//但是*this 是const iterator it//*it//++it 这样的话，可以解引用，但是不能++itconst T& operator*() const{//引用赋值，必须权限缩小或者平移，所以返回类型是constreturn _pnode->_date;}

因此我们大多数人会再写一个const迭代器类

template<class T>
struct __List_iterator
{typedef __List_node<T> node;node* _pnode;__List_iterator(node* _node):_pnode(_node){}cosnt T& operator*(){return _pnode->_date;}__List_iterator<T>& operator++(){_pnode = _pnode->_next;return *this;}__List_iterator<T>& operator--(){_pnode = _pnode->_prev;return *this;}bool operator!=(const __List_iterator<T>& It){return _pnode != It._pnode;}
};

但是对比普通迭代器和const迭代器，发现就只有operator*不一样，其他运算符重载都一样。
我们看库里是怎么实现iterator的。
暂时先不用管Ptr参数。

看到大佬是把普通迭代器和const迭代器实现放在一块，然后用Ref参数来做区分。

我们知道一个模板类，由于类型不同可实现不同的类。
如list < int > , list< char > 虽然用的是统一模板，但是由于类型不同，因此是不同的类。所以大佬方法是非常厉害的。

//typedef __List_iterator<T,T&> iterator;
//typedef __List_iterator<T,const T&> const_iterator;
template<class T,class Ref>
struct __List_iterator
{typedef __List_node<T> node;typedef __List_iterator<T, Ref> self;node* _pnode;__List_iterator(node* _node):_pnode(_node){}Ref operator*(){return _pnode->_date;}//__List_iterator<T>& operator++()//{//	_pnode = _pnode->_next;//	return *this;//}//普通迭代器和const迭代器返回类型不一样，因此typedef一下，比较方便。self& operator++(){_pnode = _pnode->_next;return *this;}//__List_iterator<T>& operator--()//{//	_pnode = _pnode->_prev;//	return *this;//}self& operator--(){_pnode = _pnode->_prev;return *this;}//bool operator!=(const __List_iterator<T>& It)//{//	return _pnode != It._pnode;//}bool operator!=(const self& It){return _pnode != It._pnode;}
};

有了const迭代器，拷贝构造和赋值运算符重载就没问题了。

9.类名与类型的区别

普通类： 类名 等价于 类型
类模板： 类名 不等价于 类型

注意：在类外面 类名 != 类型 ,类里面 类名 == 类型

这样写是没有报错的，但是不建议这样写。如果别人这样写，能看懂即可。

就如库里面提供的拷贝构造+赋值就是这样写的

10.对于自定义类型迭代器遍历的功能实现

list< T >，T可能是内置类型，也有可能是自定义类型，如果是自定义类型，迭代器该如何遍历呢？

struct Pos
{int _row;int _col;Pos(int row = 0, int col = 0):_row(row),_col(col){}
};void test_list5()
{List<Pos> It;Pos p(1,1);It.push_back(p);It.push_back(p);It.push_back(Pos(2,2));It.push_back(Pos(3,3));List<Pos>::iterator it = It.begin();while (it != It.end()){//这里还这样解引用可以拿到想要的数据吗？cout << *it << " ";++it;}cout << endl;
}

解引用有三种访问方式
1.数组------> [ ]
2.普通指针（如int *p)------> *p
3.结构的指针（pos *p）-------> p----->

	List<Pos>::iterator it = It.begin();while (it != It.end()){//cout << *it << " ";//1.cout << (*it)._row << ":" << (*it)._col << endl;//2.cout << it->_row << ":" << it->_col << endl;++it;}cout << endl;

第一种方法，调用it.operator*，返回的是一个Pos对象，

第二种方法，需要调用it.operator->，因此给迭代器增加一个operator->()函数

	T* opearotr->(){//返回的是结点数据的地址return &_pnode->_date;}	

对于T是自定义类型，迭代器遍历，推荐it->_row这样的。

再看一个问题

void print_List(const List<Pos>& lt)
{List<Pos>::const_iterator it = lt.begin();while (it != lt.end()){//const迭代器，数据不能修改it->_row++;cout << it->_row << ":" << it->_col << endl;++it;}cout << endl;
}void test_list7()
{List<Pos> It;Pos p(1, 1);It.push_back(p);It.push_back(p);It.push_back(Pos(2, 2));It.push_back(Pos(3, 3));List<Pos>::iterator it = It.begin();while (it != It.end()){//普通迭代器，对于数据可以修改it->_row++;cout << it->_row << ":" << it->_col << endl;++it;}cout << endl;print_List(It);
}

注意运行结果，const迭代器竟然也能支持it->_row++了。这不符合const迭代器。

因此再次修改一下迭代器，但是我们的普通迭代器和const迭代器实现在一块，所以这里我们给__List_iterator第三个参数Ptr

	Ptr operator->(){return &_pnode->_date;}

11.迭代器完整代码

//typedef __List_iterator<T,T&,T*> iterator;
//typedef __List_iterator<T,const T&,const T*> const_iterator;
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* _node):_pnode(_node){}Ref operator*(){return _pnode->_date;}Ptr operator->(){return &_pnode->_date;}//++itself& operator++(){_pnode = _pnode->_next;return *this;}//it++//int是一个占位符，为了把前置++和后置++ 分开self operator++(int){self tmp(*this);_pnode = _pnode->next;return tmp;}//--itself& operator--(){_pnode = _pnode->_prev;return *this;}//it--self operator--(int){self tmp(*this);_pnode = _pnode->_prev;return tmp;}bool operator!=(const self& It){return _pnode != It._pnode;}bool operator==(const self& It){return _pnode == It._pnode;}
};

注意观察我们的迭代器和List模拟实现，成员变量都有node*（指针）。

List我们实现了析构函数释放所有结点，而迭代器我们并没有实现析构函数。那迭代器这里默认生成的析构会不会释放结点呢？

析构函数和构造函数一样，如果不写，默认生成的析构函数，对内置类型不处理，对自定义类型调用它的析构。

如果我们List我们不写析构，编译器默认生成的析构，敢不敢轻易释放指针所指向的结点呢？
我们的编译器非常尽责，默认生成的析构，对自定义类型调用它的析构，对内置类型不敢轻易处理。所以对于指针不敢轻易释放所指向的结点。

因此对于List，我们需要析构的时候释放所有结点，所以自己写了个析构。而迭代器我们没写析构，那编译器默认生成的析构，对这个指针指向的结点也不会释放。因为这个结点是链表的，迭代器只是借助结点的指针帮助去访问或修改数据。所以也不能自己写一个析构去把这个结点释放。

不是说有指针就需要去析构，一定要具体问题具体分析。

并且iterator我们也没有实现拷贝构造和赋值。使用的是默认生成的属于浅拷贝就够用了，这是因为默认生成的析构并不会释放指针所指向的结点，所以够用。

在类与对象中也总结过，需要写析构，就需要自己写拷贝构造和赋值。

12.vector与list对比

	vector	list
底层结构	动态顺序表，一段连续空间	带头结点的双向循环链表
随机访问	支持随机访问，访问某个元素效率O(1)	不支持随机访问，访问某个元素效率O(N)
插入和删除	任意位置插入和删除效率低，需要搬移元素，时间复杂度为O(N)，插入时有可能需要增容，增容：开辟新空间，拷贝元素，释放旧空间，导致效率更低	任意位置插入和删除效率高，不需要搬移元素，时间复杂度为O(1)
空间利用率	底层为连续空间，不容易造成内存碎片，空间利用率高，缓存利用率高	底层节点动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低
迭代器	原生态指针	对原生态指针(节点指针)进行封装
迭代器失效	在插入元素时，要给所有的迭代器重新赋值，因为插入元素有可能会导致重新扩容，致使原来迭代器失效，删除时，当前迭代器需要重新赋值否则会失效	在插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响
使用场景	需要高效存储，支持随机访问，不关心插入删除效率	大量插入和删除操作，不关心随机访问

12.1vector优缺点总结

优点
1.下标随机访问
2.尾插尾删效率高
3.cpu高速缓存命中高（因为vector物理结构是一段连续的数组）

缺点
1.前面部分插入删除效率低O(N)
2.扩容有销毁，还存在一定空间浪费

12.2list优缺点总结

优点
1.按需申请释放，无需扩容
2.任意位置插入删除O(1)

缺点
1.不支持下标随机访问
2.cpu高速缓存命中低（list物理结点是一个个按需申请的结点）

vector与list就像左右手一样，属于互补配合的关系。

13.迭代器失效问题

我们现在已经模拟实现了string，vector，list。
vector----->insert/erase (失效)
list-------->erase（失效）

string似乎从来没提过失效还是不失效的问题。那么string到底失效不失效呢？

stirng底层和vector一样，都是连续的空间。空间不够需要扩容，因此string也失效。

string------>insert/erase（失效），但是一般不关注string的失效。

vector的insert/erase给的是迭代器，string的insert/erase常用接口更多都是下标支持，迭代器支持用的很少。所以即使扩容或者删除对下标没什么影响。

自此关于list模拟实现内容结束了，有些接口没有实现，有兴趣可以实现一下。