阿巴阿巴，list的博客来喽！
文章目录
1.list是嘛玩意？
之前的vector是一个顺序表。总所周知，学完顺序表肯定不能不学链表，所以list就来了！
list是一个可以在任何地方进行插入删除的序列式容器，可以进行前后双向迭代
说人话就是：list是一个双向带头循环链表
这不巧了嘛！之前我写过用C语言实现双向带头循环链表的博客
其优缺点也很明显
- 支持快速插入删除
O(1) - 支持前后双向迭代访问
- 不支持任意位置的随机访问
STL中的list也满足上面的这些优缺点
话不多说，来看看list的函数接口吧！
https://m.cplusplus.com/reference/list/list/
函数接口
大部分接口和前面所学的两个容器都是一样的啦，这里就不贴完整截图了（见上方链接）
这里还多了一个emplace_front，看完函数解释后可知它也是一个头插
2.简单了解使用
2.1构造
list支持的构造函数如下
这些函数和vector完全一致，这里就不过多介绍了
2.2迭代器
| 迭代器 | 说明 |
|---|---|
| begin+end | 获取第一个数据位置iterator/const_iterator， 获取最后一个数据的下一个位置iterator/const_iterator |
| rbegin+rend | 获取最后一个数据位置的reverse_iterator，获取第一个数据前一个位置的 reverse_iterator |
都是老样子，没有啥好说的
除了迭代器以外，一般的容器都会提供front和back两个参数来访问头部/尾部数据。但是我们并不常用这个，迭代器用的更多一些
2.3长度操作
库函数中给我们提供了两个和list长度相关的操作，因为是链表，所以也不存在扩容问题，每一个节点都是一个独立的空间
- empty 判断是否为空，是空返回true
- size 计算list中有效数据长度
关于插入和删除操作，list和vector/string基本都是一致的，学会一个基本都会用！
2.4迭代器失效问题
和vector一样，list也会遇到一定程度的迭代器失效问题。
因为list是一个链表，其在插入操作的时候是在迭代器所指节点前一个位置进行插入，不会影响该节点和这个节点之后的结构，也不会导致迭代器失效。
只有在删除的时候才会导致迭代器失效
解决办法也很简单，使用迭代器删除数据的时候，接收返回值更新一下迭代器即可！
基本了解了函数接口后，让我们来试试模拟实现吧！
3.模拟实现
模拟实现和STL-list源码见我的Gitee
下图是之前C语言版本链表博客里，我画的双向带头循环链表的结构图
list的结构和这个图片是一样的。但因为我们现在所使用的是C++中的类和对象，所以我们的操作都需要尊崇stl库的命名规则和使用方法，其结构的实现也会有所不同。
比如在STL源码中可以看到，list的主结构中只有一个node，即头节点。
3.1 节点结构
在list中，我们不直接在list主类中放入单个节点的结构，而是使用一个自定义类型作为节点。
复习：在
struct中，成员默认是共有
template<class T>
struct list_node
{
list_node<T>* _next;
list_node<T>* _prev;
T _data;
list_node(const T& val = T())
:_next(nullptr),
_prev(nullptr),
_data(val)
{}
};
这样后面的插入删除操作就可以直接new一个新的node，并调用构造函数完成_data的赋值。
在list的主类中，我们遵循库的方法，只用一个头节点的指针作为成员
private:
Node* _head;//头节点指针
3.2 插入删除
因为之前写过C语言的代码，关于插入和删除操作相对较为熟练，代码如下👇
//在pos之前插入
iterator insert(iterator pos, const T& x)
{
Node* newnode = new Node(x);
Node* cur = pos._node;
newnode->_next = cur;
cur->_prev->_next = newnode;
newnode->_prev = cur->_prev;
cur->_prev = newnode;
return iterator(newnode);
}
//删除pos位置
iterator erase(iterator pos)
{
assert(_head->_next != _head && pos._node!=_head);
Node* next = pos._node->_next;
Node* prev = pos._node->_prev;
prev->_next = next;
next->_prev = prev;
delete pos._node;
return iterator(next);
}
而头插/头删/尾插/尾删这类方法，我们直接复用insert和earse即可！
3.3 迭代器（重要）
在上面的插入和删除代码中，我已经使用了迭代器作为参数和返回值。由于list的主类中并没有直接存放3.1节点结构，我们需要自己单独完成一个迭代器的类，来实现迭代器的相关操作
- vector/string是顺序表，迭代器可以直接用指针替代，在本类中模拟实现
- list是顺序表，迭代器的
+和-操作其实是通过next和prev指针往后往前找内容，所以需要单独的模拟实现
在STL源码中的list也是单独重载了一个迭代器类
其基本结构如下
template<class T, class Ref, class Ptr>
struct __list_iterator
{
typedef list_node<T> Node;//节点结构
typedef __list_iterator<T, Ref, Ptr> self;//本类
Node* _node;//存放节点指针
__list_iterator(Node* node)
:_node(node)
{}
}
这里解释一下为何有3个模板参数：ref指代引用，ptr指代指针
因为在后续的操作中我们需要传入T的引用T&和指针T*，如果之传入一个T，编译器无法确认是否为const类型，也就无法阻止用户使用迭代器修改值，成员的数据就不够安全，且const的成员函数无法调用迭代器。
重载3个模板参数后，我们就可以用传入的模板参数来控制const类型
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;
基本的结构弄清楚之后，下面一起来看看，迭代器的++和--，解引用以及指针->分别对应了链表的什么操作呢？
3.3.1 加减
好吧，前面已经提到过了，我们需要用 next/prev指针来完成加减操作
//前置++
self& operator++()
{
_node = _node->_next;
return *this;
}
//后置++
self operator++(int)
{
//self是本类的别名，因为没有重载=操作符
//所以不能使用相等，要用构造函数
//self tmp = _node;
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;
}
注意前置和后置的区别，后置加减需要先用一个tmp变量储存原本的迭代器位置，再让迭代器指向下一个节点
而当我们解引用迭代器的时候，想获取的其实是_data的值，而不是节点的地址（这里迭代器依旧是用指针模拟的）
3.3.2 解引用和指针操作
所以重载后的解引用操作如下
Ref operator*()
{
return _node->_data;//返回值的引用
}
Ptr operator->()
{
return &(_node->_data);//返回地址
}
3.3.3 判断相等/不相等
最后判断相等和不相等就很简单了，因为本身就是指针，我们直接调用原生的!=进行判断即可
bool operator!=(const self& it)
{
return _node != it._node;
}
bool operator==(const self& it)
{
return _node == it._node;
}
到这里，一个建议版本的正向迭代器我们就实现啦！
3.3.4 begin/end
这里我们需要在List的本类中获取迭代器的begin和end，这里我们是调用了迭代器的构造函数，构造出来一个迭代器并进行返回
const_iterator begin() const
{
//return _head->_next;//不能直接返回指针！！
return const_iterator(_head->_next);
}
const_iterator end() const
{
return const_iterator(_head);
}
iterator begin()
{
return iterator(_head->_next);
}
iterator end()
{
return iterator(_head);
}
现在就可以愉快的用迭代器进行打印操作了！
3.4 构造函数
有了迭代器，现在就可以完成库函数里面的几个构造函数了（主要是迭代器区间的那个函数）
默认构造函数如下，先创建一个头节点，再让它的前后都指向自己。在C语言的初始化函数中，我们也是这么做的
list()
:_head(nullptr)
{
//_head = new Node;
_head = new Node();
_head->_next = _head;
_head->_prev = _head;
}
但其他的构造函数由于_head为空，所以我们需要单独实现一个空初始化函数来创建头节点
//当使用其他构造函数的时候，head还不存在，需要手动构造一个
void empty_init()
{
_head = new Node();
_head->_next = _head;
_head->_prev = _head;
}
当然，上面那个空的构造函数list()也可以复用empty_init()，这样代码更整洁
迭代器区间构造和vector是一样的，其主要是解引用后直接将值进行头插（这里就用上了之前迭代器里重载的解引用操作）
template <class InputIterator>
list(InputIterator first, InputIterator last)
{
empty_init();
InputIterator cur = first;
while (cur != last)
{
//push_back(cur._node->_data);
push_back(*cur);
cur++;
}
}
而拷贝构造就可以直接复用迭代器区间构造，赋值重载就直接swap即可。这部分的实现和vector是一样的，有问题可以在评论区提出哦！
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
}
list(const list<T>& lt)
{
empty_init();
list tmp(lt.begin(), lt.end());
swap(tmp);
}
list<T>& operator=(list<T> lt)
{
//传参没有传引用，lt已经是拷贝构造之后的结果了
//完全没必要再用tmp拷贝构造一次
//list<T> tmp(lt);
//clear();//因为tmp出了生命周期后会销毁，所以不需要手动clear
swap(lt);
return *this;
}
3.5 析构函数
因为链表需要我们一个一个去删除每一个节点的空间，这里需要单独实现一个clear函数供析构函数使用
void clear()
{
//assert(_head->_next != _head);
iterator it = begin();
while (it != end())
{
//需要用一个临时变量储存该节点的迭代器，避免迭代器失效
iterator its = it;
it++;
delete its._node;
}
}
~list()
{
clear();
delete _head;
}
上面这个函数就有些麻烦，我们其实可以直接复用erase进行删除操作+更新迭代器！
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}
到这里，一个基本的list就模拟实现完成了！
3.6 操作自定义类型
我们刚刚实现的list和STL库中的一样，都可以存放自定义类型
struct TA
{
TA(int a1 = 0, int a2 = 0)
:_a1(a1),
_a2(a2)
{}
int _a1;
int _a2;
};
void test03()
{
list<TA> lt;
lt.push_back(TA(1, 1));
lt.push_back(TA(2, 2));
lt.push_back(TA(3, 3));
lt.push_back(TA(4, 4));
//这里因为TA类的流插入没有重载，所以需要我们手动写
list<TA>::iterator it = lt.begin();
while (it != lt.end())
{
cout << it->_a1 << "-" << it->_a2 << " ";
++it;
}
cout << endl;
}
但在打印和访问自定义类型的时候，我们重载的解引用操作符就不能用了，这就是为啥要重载->操作符，此时我们还可以通过->获取到迭代器所指的对象的成员，这时候直接打印成员变量即可！
你可能觉得，这不对啊！之前重载的这个操作符不是返回的节点_data的地址吗？为啥可以直接访问_data的成员？
Ptr operator->()
{
return &(_node->_data);//返回地址
}
实际上，这里应该是it->->_a1，但是编译器在处理的时候直接将两个访问箭头简化成了一个，即增加了代码可读性，也方便使用了！
3.7 反向迭代器（适配问题）
关于反向迭代器，这里牵扯到一个更深的适配问题。我用我的笨话稍微解释一下，有问题或者有啥错误的话欢迎在评论区提出！😂
我们知道，反向迭代器是从后往前走的，它的加减操作和正向迭代器相反。
那么比起单独实现一个反向迭代器的类，我们可否利用正向迭代器，直接适配出一个反向迭代器呢？毕竟看起来它们只有方向不同！
template<class Iterator, class Ref, class Ptr>
struct Reverse_iterator
{
Iterator _it;
typedef Reverse_iterator<Iterator, Ref, Ptr> Self;
Reverse_iterator(Iterator it)
:_it(it)
{}
};
说上就上，这里我们先将反向迭代器设定为和正向相似的结构，不过它的模板参数变成了正向迭代器，而不是参数类型T，这在后续typdef的时候需要注意（不然会报错）
除了下面的解引用操作之外，其他只需要吧正向迭代器反过来用，就可以达到我们的目的！
Ref operator*()
{
Iterator tmp = _it;
return *(--tmp);//反向迭代器解引用访问的是前一个位置的数据
}
Ptr operator->()
{
return &(operator*());
}
解引用访问前一个数据的原因是，我们判断结束是用!=rend()，而rend()指向的是列表的第一个有效数据，如果直接解引用当前内容，最后一个数据就无法访问到，出现了缺漏
//前置++
Self& operator++()
{
--_it;
return *this;
}
//前置--
Self& operator--()
{
++_it;
return *this;
}
bool operator!=(const Self& s)
{
return _it != s._it;
}
更加完整的源码可以去看我的Gitee仓库哦！
完成了上面的代码后，我们需要在list本类里面进行一波操作，让它能够支持反向迭代器
//支持反向迭代器
typedef Reverse_iterator<iterator, T&, T*> reverse_iterator;
typedef Reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;
注意上面的模板参数，第一个需要传入正向迭代器，而不是T
//调用反向迭代器的构造函数
reverse_iterator rbegin()
{
return reverse_iterator(end());
}
reverse_iterator rend()
{
return reverse_iterator(begin());
}
const_reverse_iterator rbegin()const
{
return const_reverse_iterator(end());
}
const_reverse_iterator rend()const
{
return const_reverse_iterator(begin());
}
用一个打印代码便可以测试出我们的操作是否正确！
可以看到，完美逆向打印出了内容！
利用正向迭代器进行适配的最大好处，那就是其他模拟实现的容器也可以直接调用这个反向迭代器，只要在本类中加入上面的typedef和4个函数即可！
就以上篇博客的vector为例，加上上述代码后，她也能支持反向迭代器了！（源码也上传到仓库里面了）
结语
本次list的模拟实现，我们尝试模拟了一个更加详细的迭代器类，并实现了反向迭代器
有任何问题，或者本博客有错误，都欢迎在评论区提出哦！