STL-list是什么
STL里面的list本质上就是一个双向带头循环链表,如果不知道什么是双链表的话可以去看看这篇文章双链表
就像下面这种C语言双链表结构
只不过在这个原有的基础之上添加了增删查改的功能，让他变得更高级更实用
相当于把这个list封装了一遍，让我们可以调用他的接口，更加方便快捷，下面我们来看看具体怎么实现
list的模拟实现
在list里面有点麻烦的就是他的迭代器，这个和string还有vector的迭代器有点不一样，他的内存空间不是连续的，我们不能随机访问
所以我们把list分为3个部分写成两个struct和一个class，（struct的默认是公有的，这样我们在调用迭代器，还有创建节点的时候会方便一**些不像class默认是私有的）第一个是节点，这里定义了节点的数据域，还有指向前驱和后继指针的指针域，第二个是迭代器，这里我们可以简单的把迭代器理解成一个指针，用来对list进行操作，**最后一个用来定义list本身。
下面我们看看代码
template<class type>struct list_node{type data;list_node<type>* _next;list_node<type>* _prev;list_node(const type& val = type()):data(val), _next(nullptr), _prev(nullptr){}};
这里就是节点本身有数据域和指针域，这里我们用了一个模板，让编译器自动推导，这样的好处是可以存放任何数据，使用性更加广泛，
这里我们用了初始化列表，来作为默认构造函数
list_node(const type& val = type()):data(val), _next(nullptr), _prev(nullptr){}
**const type& val = type()**这里我们用了一个匿名对象来进行我们链表节点的构造，这样的好处就是，我们在构造节点的时候不用去手动去拿一个类去构造对象，这里的匿名对象自动去调用属于他自己的默认构造，列如int会去调用int的默认构造，匿名对象只在当前行起作用，出了当前行就自动销毁。
list的迭代器
template<class type, class ref, class ptr>struct list_iterator{list_node<type>* _node;list_iterator(list_node<type>* node):_node(node){}list_iterator<type, ref, ptr>& operator++(){this->_node = _node->_next;return *this;}list_iterator<type, ref, ptr>& operator--(){this->_node = _node->_prev;return *this;}list_iterator<type, ref, ptr> operator++(int){list_iterator<type, ref, ptr> temp = *this;this->_node = _node->_next;return temp;}list_iterator<type, ref, ptr> operator--(int){list_iterator<type, ref, ptr> temp = *this;this->_node = _node->_prev;return temp;}// l1 != l2bool operator !=(list_iterator<type, ref, ptr> l2){if (this->_node != l2._node){return true;}else{return false;}}bool operator == (list_iterator<type, ref, ptr> l2){return this->_node == l2._node;}ref operator*(){return this->_node->data;}ptr operator->(){&_node->data;}};
这里我们实现了主要的常用的迭代器的功能
template<class type, class ref, class ptr>
这里的定义的模板参数需要讲一下，这里，实现了类模板给编译器，给了编译器不同的参数，编译器实例化了两个不同的类第一个是type就是数据类型，下面这个ref就是引用,ptr就是指针，这样是为了方便const调用,ref,ptr具体是什么不用管，编译器会根据传的数据类型来推导创建相对应的类，传const引用就是const ref ,const ptr，不传就是普通指针，普通引用，如果不用模板，就要写两个非常相似的类，这样就太冗余了，非常麻烦
list_node<type>* _node;list_iterator(list_node<type>* node):_node(node){}
这里就是迭代器的默认构造，也是走的初始化列表，这里传了一个list_node类型的数据，也就是创建的节点来当构造参数，这里的迭代器我们可以把他理解成一个为我们list服务的专有指针，所以是list_node* _node类型，这个_node就是指针
list_iterator<type, ref, ptr>& operator++(){this->_node = _node->_next;return *this;}
这里就是实现迭代器++我们需要返回引用，因为要改变当前的迭代器的位置，这里的++不像vector还有string那样可以用原生指针，list的内存空间不连续，但他有指向前一个和下一个的指针
所以我们++就要返回当前迭代器指向的下一个地址就行了
list_iterator<type, ref, ptr>& operator--(){this->_node = _node->_prev;return *this;}
迭代器–也同理
下面是后置++迭代器，后置++，这里他会改变当前迭代器指向的位置，但会返回原来迭代器的位置，所以我们要创建一个temp变量来存放当前迭代器的值
list_iterator<type, ref, ptr> operator++(int){list_iterator<type, ref, ptr> temp = *this;this->_node = _node->_next;return temp;}
迭代器–也同理
bool operator !=(list_iterator<type, ref, ptr> l2){if (this->_node != l2._node){return true;}else{return false;}}
这里是判断两个迭代器的是不是不相等的，用当前迭代器指向的位置来判断，
判断相等也同理
bool operator == (list_iterator<type, ref, ptr> l2){return this->_node == l2._node;}
这里是对*的运算符重载，返回当前迭代器下面的数据域，这里就体现模板的作用了，这里的ref是没有被定义的可以返回普通的，也可以是const的
ref operator*()
{return this->_node->data;
}
我们可以来试一下
这里迭代器就讲解完了，我们来说说list
list
下面是代码
template<class type, class ref, class ptr>
class list
{
public:void init_empty(){_head = new list_node<type>;_head->_next = _head;_head->_prev = _head;_size = 0;}list(){init_empty();}//l2(l1)list(const list<type, ref, ptr>& l1){init_empty();list_iterator<type, const ref, const ptr> it = l1.const_begin();while (it.operator!=(l1.const_end())){this->push_back(*it);it++;}}void swap(list<type, ref, ptr>& li){std::swap(this->_head, li._head);std::swap(this->_size, li._size);}// l1 l2list<type, ref, ptr>& operator=(list<type, ref, ptr>& li){swap(li);return *this;}void clear(){auto it = this->begin();while (it != this->end()){it = this->erase(it);}}~list(){clear();delete this->_head;this->_head = nullptr;}list_iterator<type, ref, ptr> begin(){return _head->_next;}list_iterator<type, ref, ptr> end(){return _head;}list_iterator<type, const ref, const ptr> const_begin() const{return _head->_next;}list_iterator<type, const ref, const ptr> const_end() const{return _head;}//tail newnode headvoid push_back(const type& input){list_node<type>* newnode = new list_node<type>(input);list_node<type>* tail = this->_head->_prev;newnode->_next = this->_head;newnode->_prev = tail;tail->_next = newnode;this->_head->_prev = newnode;_size++;}//pos newnode nextvoid insert(list_iterator<type, ref, ptr> pos, const type& input){list_node<type>* newnode = new list_node<type>(input);list_node<type>* next = pos._node->_next;list_node<type>* poser = pos._node;newnode->_next = next;newnode->_prev = poser;pos._node->_next = newnode;next->_prev = newnode;_size++;}// prev pos nextlist_iterator<type, ref, ptr> erase(list_iterator<type, ref, ptr> pos){list_node<type>* poser = pos._node;list_node<type>* next = poser->_next;list_node<type>* prev = poser->_prev;delete poser;prev->_next = next;next->_prev = prev;return next;}void pop_fornt(){erase(this->begin());}void pop_back(){erase(this->end()--);}size_t size(){return this->_size;}size_t size() const{return this->_size;}bool is_empty(){return this->_size == 0;}
private:size_t _size;list_node<type>* _head;
};
这里，因为我们是双向循环带头链表，在初始化的时候就需要创建一个头节点，这个头节点不存放任何东西
void init_empty(){_head = new list_node<type>;_head->_next = _head;_head->_prev = _head;_size = 0;}
所以我们的默认构造函数，就要调用init_empty()来满足这个双向链表的结构特点
list()
{init_empty();
}
在有头节点之后，我们在进行对数据的插入，修改等
下面是拷贝构造函数
//l2(l1)list(const list<type, ref, ptr>& l1){init_empty();list_iterator<type, const ref, const ptr> it = l1.const_begin();while (it.operator!=(l1.const_end())){this->push_back(*it);it++;}}
这个拷贝构造函数很巧妙，用了一个尾插来解决，把原始list里面的值复制一份拿下来，这里的必须是 const ref, const ptr，因为拷贝构造传的参数必须是const对类类型的对象的引用，这段代码用了迭代器来完成拷贝构造，it获取最先开始的位置，依次++直到最后一个迭代器位置
接下来就是赋值运算符重载
// l1 l2list<type, ref, ptr>& operator=(list<type, ref, ptr>& li){swap(li);return *this;}void swap(list<type, ref, ptr>& li){std::swap(this->_head, li._head);std::swap(this->_size, li._size);}
这里很巧妙，直接交换两个对象指向的指针，还有大小，就行了，假设把l2复制给l1，this指针是指向l1，交换完之后this就是指向l2了，当swap函数结束之后，l1会自动销毁，带走l1所指向的链表，直接返回*this就可以了,就完成了赋值，
下面是析构函数
void clear(){auto it = this->begin();while (it != this->end()){it = this->erase(it);}}~list(){clear();delete this->_head;this->_head = nullptr;}
这里我们通过erase(it)这个函数来实现析构，这个函数就是删除当前节点函数，也是通过两个迭代器来控制区间，最后就是删除头节点
下面这些就是非常简单的小函数了，返回开始和结束的迭代器，还有const版本
list_iterator<type, ref, ptr> begin()
{return _head->_next;
}
list_iterator<type, ref, ptr> end()
{return _head;
}
list_iterator<type, const ref, const ptr> const_begin() const
{return _head->_next;
}
list_iterator<type, const ref, const ptr> const_end() const
{return _head;
}
下面我们来说说erase
list_iterator<type, ref, ptr> erase(list_iterator<type, ref, ptr> pos)
{list_node<type>* poser = pos._node;list_node<type>* next = poser->_next;list_node<type>* prev = poser->_prev;delete poser;prev->_next = next;next->_prev = prev;return next;
}
这里我们可以画图来理解一下
像push_back和insert可以看看开头给的文章链接，里面有更详细的讲解
void pop_fornt(){erase(this->begin());_size--;}void pop_back(){erase(this->end()--);_size--;}size_t size(){return this->_size;}size_t size() const{return this->_size;}bool is_empty(){return this->_size == 0;}
这些小函数就不需要过多的讲解了删除头部，和删除尾部都可以调用erase来解决，判空可以判断_size是不是为0，size，我们在对链表中push_back ，insert, 等，里面都有对size进行统计，这样统计size更加方便，不用在去新写一个函数进行对size进行统计
print打印函数
template<class print_type>
void print(print_type& p1)
{list_iterator<int, int&, int*> it = p1.begin();while (it != p1.end()){cout << *it << " ";it++;}cout << endl;
}
这里，我们创建了一个模板类，这里和上面一样可以传不同的数据类型进来进行打印，不同的数据类型实例化不同的类型，提高了函数的利用性
以上就是对list的主要接口的实现，如果有什么问题欢迎指正！
完
