阿巴阿巴，list的博客来喽！

[TOC]

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的主类中，我们遵循库的方法，只用一个头节点的指针作为成员

1 2	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类型

1 2	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本类里面进行一波操作，让它能够支持反向迭代器

1
2
3

//支持反向迭代器
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的模拟实现，我们尝试模拟了一个更加详细的迭代器类，并实现了反向迭代器

有任何问题，或者本博客有错误，都欢迎在评论区提出哦！