感谢大佬的光临各位，希望和大家一起进步，望得到你的三连，互三支持，一起进步
数据结构习题_LaNzikinh篮子的博客-CSDN博客
初阶数据结构_LaNzikinh篮子的博客-CSDN博客
收入专栏：C++_LaNzikinh篮子的博客-CSDN博客
其他专栏：c语言基础_LaNzikinh篮子的博客-CSDN博客
个人主页：LaNzikinh-CSDN博客
文章目录
前言一.迭代器二.list的底层实现三.list使用和细节总结前言
经过前面两个容器的讲解，其实已经对很多接口的使用都了解的差不多了，容器之间接口的使用真的都是大体相同的，但是底层的实现是不同的，今天我们来看看列表是如何实现这个功能的，在讲解列表的实现之前，我们先要再次来讲解这个迭代器
一.迭代器
迭代器的功能分为四种迭代器，反向迭代器，常数迭代器，反向常数迭代器，他的性质有三种，单向迭代器，双向迭代器和随机迭代器，性质的意思就是底层结构，底层结构可以决定可以用哪些算法
举个例子来说，比如说我们之前学过的排序算法，他在库里面就一个专门这样子的函数sort，他支持的就是随机的代替其他不支持，所以说在list创建的类就不能用这个库里面的算法，只能自己实现一个，又比如说逆置算法reverse（需要++/--）他支持双向迭代器，所以说随机的也可以，但是单向的就不行
我们的list就是双向迭代器，我们之前学过的vector和string就是随机迭代器，那我们后面的栈和队列是什么呢？
答案是根本不支持迭代,栈的特性是先进后出，队列的特性是先进先出，如果都满足了迭代器的遍历，那这些特性就不存在了，你支持了迭代器，那你的特性的意义在什么地方呢
二.list的底层实现
我们之前讲过了库函数的使用，直接看文档即可，在这里就不做多的了解了，和之前的使用string，vector是大致相同的，主要还是来看list的底层，他是一个带头双向循环列表，不是我们以前C语言学过的单链表
接下来了，我们先要来定义两个结构体，一个就是节点本身，还有一个就是指向节点的指针，即便它是一个带头双向循环列表，这两个也是必不可少的
2.1定义两个结构体
结点
const T& data = T()；利用缺省参数来进行初始化
template<class T>struct list_node{T _data;list_node<T>* _next;list_node<T>* _prev;list_node(const T& data = T()):_data(data), _next(nullptr), _prev(nullptr){}};指向节点的指针
注意：这里获取的迭代器，就是一个节点的指针
因为他是一个指针，所以说我们要用函数重载来定义它的加加减减和判断等于，还有解引用
template<class T>struct list_iterator{typedef list_node<T> Node;typedef list_iterator<T> Self;Node* _node;list_iterator(Node* node):_node(node){}T& operator*(){return _node->_data;}Self& operator++(){_node = _node->_next;return *this;}Self& operator--(){_node = _node->_prev;return *this;}bool operator!=(const Self& s) const{return _node != s._node;}bool operator==(const Self& s) const{return _node == s._node;}};2.2insert（）和 erase（）
迭代器失效问题
前面说过，此处大家可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。
insert（）
void insert(iterator pos, const T& x){Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);// prev newnode curnewnode->_next = cur;cur->_prev = newnode;newnode->_prev = prev;prev->_next = newnode;++_size;}erase（）
只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响
void erase(iterator pos){assert(pos != end());Node* prev = pos._node->_prev;Node* next = pos._node->_next;prev->_next = next;next->_prev = prev;delete pos._node;--_size;}所以要用返回值来改正，防止迭代器失效
int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };list<int> l(array, array+sizeof(array)/sizeof(array[0]));auto it = l.begin();while (it != l.end()){l.erase(it++); // it = l.erase(it);}2.3头插尾插一个数据
直接复用就可以了
void push_back(const T& x){insert(end(), x);}void push_front(const T& x){insert(begin(), x);}2.4析构函数和迭代器函数
iterator begin(){return _head->_next;}iterator end(){return _head;}list(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}2.4成员对象
private:Node* _head;size_t _size;三.list使用和细节
还是补充几个list一些独特的函数使用方式和一些使用它的细节
emplace：构造和插入元素
他是支持直接传构造函数对象的参数的
list<A> lt;A a1(1,1);lt.push_back(3,3);//不合理，不存在lt.emplace_back(3,3);//可以unique：删除重复值
注意：前提要有序不然删不完全
merge：合并排序列表
注意：合并排序列表，v1会被滞空
it.merge(v1);补：
如果要在pos的位置插入一个30大小的元素
auto it = lt.begin();int k = 3;while (k--){++*it;}it.insert(it, 30);因为他的迭代器只支持++
总结
链表容器结构到这里就结束了，下一章，我们将引入一个适配器的概念去完成栈与队列的知识