【决战西二旗】|理解STL list原理
一颗彩蛋
特别纪念一下这首歌，昨天(20191128)晚上10点多下班回来进小区，忽然想起一首歌《千里之外》，哼唱了几句，"薄如蝉翼的未来经不起谁来拆 #￥@#"
谁曾想前面有危险等着我，TM物业修路没收拾好，有个栏杆放地上，一下子给我绊倒了，咱跑半程马拉松的主儿腿脚快啊，90度扑在刚修不久的水泥路面，这砸地的声音估计把一楼的人都吵醒了，我屮艸芔茻，真尼玛疼啊啊！
当时我就气急败坏了 我早已经向生活低头了，不就是唱了几句歌嘛，生活啊至于这么对我下手吗？反过来想，之前立过flag：不管发生啥 心态不能崩
于是趁着四下无人爬起来，抓紧回来码字，毕竟跌倒了还能爬起来，科学文化知识落后了可不容易追上^_^，闲话少叙，滴滴滴，五道口大白号要发车了！
初识List
前面说了vector，今天说一下另外一个高频顺序容器list，你可能会问STL的list和普通自己写的链表有啥区别吗？
非要这么问只能告诉你，人家STL写的list更通用、更灵活、更高效、高节约，是一种高效的链表轮子，你可以简单地认为STL的list就是对平时自己业务中写的链表的封装和模板化，避免了一些不必要的轮子，更主要的是提供了丰富的接口，可以支持你常用的几乎所有操作，你说这玩意好不好。
list VS vector
list容器是本质是一个循环的双向链表，它的内存空间效率比vector容器更高。
原因不外乎两点 :
vector容器的内存空间是连续存储的，且为了避免复制在分配内存空间时会分配额外的可用空间，当然这也是vector可以随机存取的根本所在，鱼和熊掌不可兼得，辩证看待。
list容器的内存空间不一定是连续存储，内存之间是采用迭代器或节点指针进行连接，并且在插入或删除数据节点时，就配置或释放一个数据节点，并不会分配额外的内存空间，这两个操作过程都是常数时间。
list容器由于是基于链表实现的，因此在进行插入操作或拼接操作时，迭代器并不会失效，所以反过来看vector的插入和删除都是牵一发动全身的，会导致迭代器失效问题，这是使用容器时的一个坑，需要格外小心，别掉沟里。
但是也由于是基于非连续存储空间，因此不能以普通指针作为迭代器，因为普通指针的+或-操作只能指向连续空间的后移地址或前移个地址，不能保证指向list的下一个节点，list的迭代器必须是双向迭代器具备前移和后移的能力。
list的底层细节
在我们自己写list时，无论是单向还是双向链表都要先定义链表节点list_node，然后再定义链表结构，这个就相当于list_node是一节节的车厢，list是动车组列车，二者是这种关系。
list_node定义
在list容器中，list本身和list节点是分开设计的，list节点结构是存储数据和指向相邻节点的指针，源码如下：
//以下是list链表节点的数据结构
struct _List_node_base {
_List_node_base* _M_next;//指向直接后继节点
_List_node_base* _M_prev;//指向直接前驱节点
};
template <class _Tp>
struct _List_node : public _List_node_base {
_Tp _M_data;//节点存储的数据
};
list定义
list数据结构是只有一个指向链表节点的指针，因为list容器是循环双向链表，则足够遍历整个链表，如下源码所示：
//以下是双向链表list类的定义，分配器_Alloc默认为第二级配置器
template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
class list : protected _List_base<_Tp, _Alloc> {
...
public:
typedef _List_node<_Tp> _Node;
protected:
//定义指向链表节点指针
_List_node<_Tp>* _M_node;
...
};
哑结点
list的循环双向链表中有一个特殊的节点，不存储数据，只为这个链表的入口，先称作哑结点吧。迭代链表时，首先通过哑结点再next指向下一个节点就可以迭代所有数据。
哑结点作为list的end节点，哑结点的next为begin节点，这样就可以用[begin,end)这种左闭右开的形式来表示迭代器范围，和其他容器保持一致。
迭代器
迭代器分类
常用的迭代器按功能强弱分为：输入，输出，正向，双向，随机访问 五种。
（1）正向迭代器
假设p是一个正向迭代器，则p支持以下操作：
++p，p++，*p，两个迭代器可以进行相互赋值，以及==，!=比较
（2）双向迭代器
双向迭代器具有正向迭代器的所有功能，并且可以进行 --p 和 p-- 的操作
（3）随机访问迭代器
随机访问迭代器具有双向迭代器的所有功能，并且还可以进行以下操作，假设i是一个整型变量或常量：
p+=i：p往后移动i个元素
p-=i：p往前移动i个元素
p+i：返回p后面第i个元素的迭代器
p-i：返回p前面的第i个元素的迭代器
p[i]：返回p后面第i个元素的引用
两个随机访问迭代器还可以进行<，>，<=，>=，- 的操作
list迭代器
list容器的内存空间存储是非连续的，不能用普通指针做为迭代器，list容器的迭代器是双向迭代器，为了迭代所有数据，必须通过上个节点找到下个节点的地址，进而访问下个节点，也就是依靠pre和next来进行双向迭代，代码实现：
template<class T, class Ref, class Ptr>
struct __list_iterator {
typedef __list_node<T>* link_type;
link_type node; // 这个迭代器指向的节点
// 迭代器构造函数
__list_iterator(link_type x) : node(x) {}
__list_iterator() {}
__list_iterator(const iterator& x) : node(x.node) {}
// 迭代器必要的行为实现
bool operator==(const self& x) const { return node == x.node; }
bool operator!=(const self& x) const { return node != x.node; }
//迭起器取值，取得是节点的值
reference operator*() const { return (*node).data; }
//成员调用操作符
pointer operator->() const { return &(operator*()); }
// 先加１，再返回，类似与++i
self& operator++() {
node = (link_type)((*node).next);
return *this;
}
//先加１，然后返回加１前的数据，类似与i++
self operator++(int) {
self tmp = *this;
++*this;
return tmp;
}
// 先减１，再返回，类似于--i
self& operator--() {
node = (link_type)((*node).prev);
return *this;
}
//先减１，再返回减１前的数据，类似于i--
self operator--(int) {
self tmp = *this;
--*this;
return tmp;
}
};重点成员函数
erase
使用earase删除某个位置迭代器指向的节点与我们平时熟悉的链表删除节点基本类似，就是完成pre和next指向调整，再销毁删除节点的内存，从而实现删除工作，详细如下：
iterator erase(iterator position) {
link_type next_node = link_type(position.node->next);
link_type prev_node = link_type(position.node->prev);
prev_node->next = next_node;
next_node->prev = prev_node;
destroy_node(position.node);
return iterator(next_node);
}
remove
使用remove可以遍历删除指定值的元素，与stl中的remove算法有一些区别，详细如下：
template <class T, class Alloc>
void list<T, Alloc>::remove(const T& value) {
iterator first = begin();
iterator last = end();
while (first != last) {
iterator next = first;
++next;
if (*first == value) erase(first);
first = next;
}
}
reverse
链表逆序对我们来说非常熟悉，不过stl的实现跟我们平时写的不太一样，详细如下：
template <class T, class Alloc>
void list<T, Alloc>::reverse() {
if (node->next == node || link_type(node->next)->next == node) return;
iterator first = begin();
++first;
while (first != end()) {
iterator old = first;
++first;
//从链表begin开始，逐个插入begin之前
transfer(begin(), old, first);
}
}
merge
stl本身也有merge算法，但是由于list的迭代器不是随机迭代器，因此需要list自己实现merge，详细如下：
template <class T, class Alloc>
void list<T, Alloc>::merge(list<T, Alloc>& x) {
iterator first1 = begin();
iterator last1 = end();
iterator first2 = x.begin();
iterator last2 = x.end();
while (first1 != last1 && first2 != last2)
if (*first2 < *first1) {
iterator next = first2;
transfer(first1, first2, ++next);
first2 = next;
}
else
++first1;
if (first2 != last2) transfer(last1, first2, last2);
}
sort
list不能使用STL的sort算法，STL的sort算法必须接受随机迭代器RamdonAccessIterator，而sort的迭代器为双向迭代器Bidirectionaliterators，因此list自己实现了sort算法，详细如下：
template <class T, class Alloc>
void list<T, Alloc>::sort() {
//边界判断
if (node->next == node || link_type(node->next)->next == node) return;
//临时存储
list<T, Alloc> carry;
list<T, Alloc> counter[64];
int fill = 0;
while (!empty()) {
carry.splice(carry.begin(), *this, begin());
int i = 0;
while(i < fill && !counter[i].empty()) {
counter[i].merge(carry);
carry.swap(counter[i++]);
}
carry.swap(counter[i]);
if (i == fill) ++fill;
}
for (int i = 1; i < fill; ++i)
counter[i].merge(counter[i-1]);
swap(counter[fill-1]);
}小结
时间原因很多细节来不及说，stl中list的实现对于我们掌握链表这种数据结构非常有帮助，所以花一些时间来研究stl list的底层实现将对链表的理解、操作的实现、模板通用化等方面有更为深刻的认识。
参考资料
http://luodw.cc/2015/10/28/STL-list/
https://www.kancloud.cn/digest/stl-sources/177269
https://www.cnblogs.com/chen-cai/p/10321559.html