前言

本文将从list的使用，再到根据sgi库对于list实现作为参考模拟实现一下list。通过模拟实现来增加对它的理解。

介绍list

list是一个由带头双向循环链表实现的STL容器，它提供常规时间内对数据进行插入和删除操作。
list在内存中存储不连续的空间存储，这样避免了连续存储的扩容问题。
list支持双向迭代器，即支持从前往后遍历容器和从后往前遍历容器。

list的使用

下面写一份简单的代码介绍一下list的基本接口。

在insert接口和erase接口的使用中，list相较于vector来说用起来有些区别。
vector调用insert()接口要在第二个元素位置之后，可以直接使用迭代器+2作为参数传递。而list不可以。list想要做到在第二个元素之后插入的话，需要先将迭代器移动到指定位置后，在插入数据。

int main()
{vector<int> v(4,0);list<int> lt(4,0);// 在第二个元素后插入一个值v.insert(v.begin() + 2, 10);auto ite = lt.begin();int n = 2while(n--){++ite;}lt.insert(ite, 10);return 0;
}

为什么list不像vector一样能直接将迭代器+2传参呢？我们知道vector存储在一段连续的空间中，而list不一定是存储在一段连续的空间中。从技术实现的角度来说，list使用迭代器+2找到第二个元素后的位置是肯定可以实现的。至于为什么不这么做呢？我个人看来，可能是标准委员会的大佬们觉得list头尾插入删除效率极佳，如果支持的话有些使用者不了解底层的实现原理，势必不了解list效率上的不足，这样一来可以引导程序员在大量数据删除、插入操作在容器中间位置时，去用vector存储数据以便操作。

既然谈到了vector和list存储特点上有区别，下面引申出一些关于迭代器为什么不实现了operator < 、operator >等，而是统一用operator!=或operator==做条件判断的操作符。因为list、map、set等容器都不是存储在一段连续的空间上，所以，并不意味着第一个元素的地址就在第二个元素的地址前面。迭代器这样实现上为了兼容非线性存储结构的容器也能正常的使用迭代器进行操作。

list迭代器失效问题

vector的insert()和erase()后都会导致迭代器失效问题，因为vector的insert()涉及到扩容操作会导致迭代器失效，以及erase接口删除特定位置元素后导致的迭代器失效问题。那么list会存在迭代器失效问题吗？答案是会。但是，insert接口不会涉及迭代器失效问题。list底层实现不涉及扩容操作，所也就不存在迭代器失效了。

而erase接口依旧会导致迭代器失效问题。

简介迭代器

STL库对于STL容器的迭代器实现分为三类，一种是单向迭代器（forward iterator），单链表（forward_list）、哈希表(unordered_map/unordered_set)使用的就是单向迭代器，单项迭代器只能从前往后进行迭代，所以只提供了operator++重载。另一种是双向迭代器（bidirectional iterator ），双向链表（list）、红黑树系列（map/set）所使用的是双向迭代器。双向迭代器提供了operator++、operator–。还有一种是随机迭代器（random access iterator ）。vector、deque、string都是使用的随机迭代器。相较于双向迭代器，随机迭代器支持了对于迭代器的operator+、operator-的重载和operator[]的重载。

聊一聊list提供的操作接口

由于list并不支持随机迭代器，所以算法库中的sort是无法调用的，因为底层使用快速排序实现的，必须使用随机迭代器才能调用。而list库中提供的sort底层是用归并排序实现的。list的sort相比于算法库里的sort其实效率是拉胯的。
在百万级以上的数据排序下，list的sort甚至不如将list的数据拷贝到vector排序，再拷贝回list。下面做一组对照实验带大家看看。我们的两组对照组，排序数据是1000w个随机值，一组我们使用list库的sort，与另一个测试组，现将数据拷贝到vector后，再调算法库的sort，最后再拷贝回list。通过比对两者时间差距便知。

可以看到在1000w个数据的量级下，list排序和拷贝到vector排序后再拷回来的时间差距是一个接近二倍的差距。

list的sort，在数据量小的情况下其实使用起来问题不大。提供sort接口更多是为了可以配合以下的接口进行使用。merge()函数，用于归并两个有序地链表。unique函数，用于有序链表的去重操作。

归并两个有序链表的操作

对有序链表去重

reverse()逆置链表操作

remove()删除指定值的元素

splice()转移链表到指定位置。

模拟实现list

首先我们搭一个最简单的框架，然后再慢慢完善它。

首先是先把类给定义出来，这里不仅需要定义list类，还需要定义一个描述节点的类。


push_back()接口实现思路这里简单说一下，我们先定义一个局部变量tail存一下原链表的尾，以方便尾插。然后就是创建新节点。让新节点的_prev指向tail，让tail的_next指向新节点。让_head节点的_next结点指向新节点，最后让新节点的_prev指向_head即可。

模拟实现迭代器

由于list的迭代器需要重载operator++、operator–、operator!=、operator==以及operator* 等运算符重载。其中operator*是访问节点的数据而不是获取节点。我们需要用自定义类型来封装list的迭代器。这与string、vector等连续空间存储的容器不同，它们的迭代器可以是原生指针来定义的（vs用的是结构体定义自定义类型封装）。而list它是非连续空间存储。所以迭代器实现采用自定义类型封装。

template<class T>
struct __list_iterator
{typedef list_node<T> Node;//成员变量Node* _node;__list_iterator(Node* node):_node(node){}__list_iterator<T>& operator++(){_node = _node->_next;return *this;}__list_iterator<T>& operator++(int){__list_iterator<T> tmp(*this);_node = _node->_next;return tmp;}__list_iterator<T>& operator--(){_node = _node->_prev;return *this;}__list_iterator<T>& operator--(int){__list_iterator<T> tmp(*this);_node = _node->_prev;return tmp;}T& operator*(){return _node->_data;}bool operator!=(const __list_iterator<T>& it){return _node != it._node;}bool operator==(const __list_iterator<T>& it){return _node == it._node;}
};

这里我们就实现了一份简易的迭代器，下面我们简单测试一下。

那const迭代器要如何实现呢？直接定义吗？答案是不是的。list的const迭代器是为了保证指向的数据不被修改，但是迭代器本身还是要支持修改的。所以我们可以再上面的基础上把我们的operator*的参数修改一下即可。

template<class T>
struct __list_const_iterator
{typedef list_node<T> Node;//成员变量Node* _node;__list_const_iterator(Node* node):_node(node){}__list_const_iterator<T>& operator++(){_node = _node->_next;return *this;}__list_const_iterator<T>& operator++(int){__list_const_iterator<T> tmp(*this);_node = _node->_next;return tmp;}__list_const_iterator<T>& operator--(){_node = _node->_prev;return *this;}__list_const_iterator<T>& operator--(int){__list_const_iterator tmp(*this);_node = _node->_prev;return tmp;}const T& operator*(){return _node->_data;}bool operator!=(const __list_const_iterator<T>& it){return _node != it._node;}bool operator==(const __list_const_iterator<T>& it){return _node == it._node;}
};

那这样设计是不是太冗余了，我们这时候可以参看一下SGI库大佬实现的思路了。多加两个模板参数，分别是Ref（用作operator*的返回值类型）以及Ptr（用作operator->的返回值类型）。这样我们就不用实现两份代码了，进需要控制模板的参数即可完成const迭代器和普通迭代器的实现了。

//typedef __list_iterator<T, T&, T*> iterator;
//typedef __list_iterator<T, const T&, const T*> const_iterator;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){}Self& operator++(){_node = _node->_next;return *this;}Self operator++(int){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;}Ptr operator->(){return &_node->_data;}Ref operator*(){return _node->_data;}bool operator!=(const Self& it){return _node != it._node;}bool operator==(const Self& it){return _node == it._node;}
};

补充聊一下编译器对于operator->调用时的特殊处理。

其实按照c语言的语法来看我们使用迭代器访问A类型的两个成员变量时，应该是it->->_a1。但是，由于这样写实在是太过于复杂，甚至还不如不实现这个operator->。于是c++委员会规定编译器可以对这个做一个特殊处理，省略一个->，以保证代码的可读性。

erase()和insert()的模拟实现

erase的实现思路如下，断言判断一下迭代器的有效性。定义两个变量保存前后的节点。修改前后节点的指向，然后释放节点，最后返回当前位置的下一个位置的迭代器即可。由于我们定义了成员变量来记录size的值，所以还需要注意修改。

向pop_back()、pop_front()这类接口复用erase即可。

insert()实现思路如下，定义两个变量保存前后节点，new一个新节点。修改前后节点的指向后，修改一下size的值，最后返回新节点。

clear()与析构函数的模拟实现

实现clear接口思路如下，遍历一遍链表依次erase即可，最后清空size的值即可。

析构函数实现思路如下只需要先调用clear()释放所有的有效节点，最后delete哨兵位头结点即可。

拷贝构造实现

我们需要new一个头结点并初始化它，随后我们可以依次将被拷贝对象尾插到头结点后。

operator=的模拟实现

使用现代写法实现，因为在operator=的形参是实参的临时拷贝，将它的内容交换给成员变量就可以达到赋值的效果。

总结

本文重点在于list的迭代器部分的实现，通过三个模板参数实现一份迭代器，不仅仅加深了我们对于泛型编程的理解，还加深了我们对于STL容器如何做到操作一致性的原理以及背后设计思路的理解。不得不感慨语言的发展真的是一个不亚于特破某个实体领域的技术壁垒。