1.list介绍

list 底层实际上是一个带头双向循环链表，链表的结构就是由一个又一个的结点组成，但是list 每次实例化出来的对象数据类型可能不一样，因此我们首先需要实现一个结点类，每一个结点所包含的信息有：数据、前驱指针、后继指针。同时，类中需要实现一个构造函数，该结点类能够根据数据类型构造出相应的结点。

template<class T>
struct ListNode
{
	ListNode<T>* _prev;//前驱指针
	ListNode<T>* _next;//后继指针
	T _date;//数据
 
	ListNode(const T& value = T())
		:_prev(nullptr)
		, _next(nullptr)
		, _date(value)
		{}
};

2.迭代器类的模拟实现

迭代器的目的

在解释相关原因之前，我们需要先明确迭代器的意义与目的。实际上，迭代器的核心目的是：无需关注底层的实现细节，能够以一种类似于指针的方式去访问容器中的内容与数据；简而言之，就是要模拟指针的行为（比如支持 ++、–、* 等操作）。

list特殊的迭代器

string和vector的迭代器我们不用去自己实现，list的迭代器是类，需要我们自己实现，实际上是因为底层空间结构，string 和 vector 是一段连续的空间，他们底层的迭代器就是原生的指针！

list底层结构是随机的，所有不能用原生指针节点作为迭代器，对++，–这类操作符就不在适用，因为空间不连续，++后的地址不是我们想要的。

所以，当内置类型（如原生的结点指针）无法满足我们所需的行为时，我们可以将其封装为自定义类。也就是说，把原生的结点指针封装成一个类后，它就成为了自定义类型；而对于类，我们能够进行运算符重载。比如，表面上是对迭代器执行 ++ 操作，但其底层实际上是让结点指针指向 node->next。如此设计，不就正好契合迭代器存在的目的了吗？

迭代器类函数模版

template<class T,class Ref,class Ptr> 

这个参数的存在就是就是因为迭代器实际有两种，一个是非const，一个为const对象提供的。

typedef list_iterator<T, T&, T*> iterator;
typedef list_iterator<T, const T&, const T*> const_iterator;

可以看到Ref对应的是T引用，Ptr对应的就是T指针，他们会根据传进来的类型自动匹配！如果不设计就很难区分。
为啥要一个引用，一个指针呢？实际和运算符重载有关，接着向下看！

迭代器类模拟实现及功能注意

下面图片是迭代器的具体实现，可以学习一下

这里有些功能需要注意

1. *运算符重载

这个操作实际上相当于指针的解引用，*it，访问数据，对于解引用操作，我们不仅可以对当前是数据进行读操作，还能重新赋值，也就是可读可写，所以采用引用返回！所以原本是 T&，但由于要区分 const T&，就用了 Ref 这个模板参数，这就是它的由来

2. ->运算符重载

部分时候还是用得到

比如上面这段代码，在*it时会发生错误，因为解引用只是访问到A而已，没有访问到里面的成员变量

这里就需要使用到运算符->重载，实际上这里完整的写法是：it.operator->()->_a,缩写就是两个->->,第一
个->实际上获取的是A*,第二个是对A*指针的解引用。编译器为了代码可读性，省略了一个

3.list类的模拟实现

默认成员函数

public:
typedef ListNode<T>  Node;
typedef ListIterator<T, T&, T*> iterator;
typedef ListIterator<T, const T&, const T*> const_iterator;
 
//成员变量
private:
Node* _head;
size_t _size;

还有一个初始化空链表

	void empty_init()
	{
		_head = new Node;
		_head->_next = _head;
		_head->_prev = _head;
		_size = 0;
	}

构造函数

• 无参构造

list()
{
	empty_init();
}

• 特定值初始化

list(int n, const T& value = T())
{
	empty_init();
	for (int i = 0; i < n; i++)
	{
		push_back(value);//尾插数据即可
	}
}

• 迭代器区间初始化

template <class Iterator>
list(Iterator first, Iterator last)
{
	empty_init();
	while (first != last)
	{
		push_back(*first);
		++first;
	}
}

拷贝构造

//拷贝构造
//it1(it2)
list(const list<T>& l)
{
	empty_init();
	for (auto& e : l)
	{
		push_back(e);
	}
}

赋值重载

//赋值构造
//it1=it2
list<T>& operator=(list<T> l)//引用返回支持连续赋值
{
	swap(l);
	return *this;
}

析构函数

//析构函数
~list()
{
	clear();
	delete _head;
	_head = nullptr;
}

4.迭代器

begin+end	返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器
rbegin+ rend	返回第一个元素的reverse_iterator,即end位置，返回最后一个元素下一个位置的reverse_iterator,即begin位置

这篇文章详细讲解过迭代器，迭代器

1. begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
2. rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动

5.访问数据

front和back

front: 返回list的第一个结点中值的引用，就是取头数据
back: 返回list的最后一个结点中值的引用，就是取尾数据

 T& front() 
 { 	
 return _head->_next->_date;
  }

T& back() 
{ 	
return _head->_prev->_date; 
}

6.增删查改

insert

iterator insert(iterator pos, const T& x)
{
	Node* newnode = new Node(x);
	Node* cur = pos._node;
	Node* prev = cur->_prev;
 
	prev->_next = newnode;
	newnode->_prev = prev;
	newnode->_next = cur;
	cur->_prev = newnode;
 
	++_size;
 
	return pos;
}

erase

删除pos位置的值，并返回pos位置的迭代器。所以这里会存在迭代器失效的问题，注意只是当前迭代器失效，之后的其他迭代器并不会受到任何影响

iterator erase(iterator pos)
{
	Node* cur = pos._node;
	Node* prev = cur->_prev;
	Node* next = cur->_next;
 
	prev->_next = next;
	next->_prev = prev;
	delete cur;
	--_size;
 
	return next;
}

push_back 和push_front

这里直接复用就可以

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

pop_back 和pop_front

void pop_front()
{
	erase(begin());
}
void pop_back()
{
	erase(--end());//这里只能--end，不能end-1因为end是传值返回的
}

clear

清理除了头结点外的所有节点。

void clear()
{
	iterator it = begin();
	while (it != end())
	{
		it=erase(it);//注意这里一定要更新迭代器，因为会失效
	}
}

swap

void swap(list<T>& l)
{
	std::swap(_head, l._head);
	std::swap(_size, l._size);
}

7.容量

size

这里我们在插入和删除操作，都加上了++size或者–size了。所以keyi1直接调用

size_t size()const
{
	return _size;
}

empty

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