STL序列式容器之list

相较于vector的连续性空间，list相对比较复杂；list内部使用了双向环形链表的方式对数据进行存储；list在增加元素时，采用了精准的方式分配一片空间对数据及附加指针等信息进行存储；

list节点定义如下

template<class T>
struct __list_node{__list_node<T>* pre;   // 此处采用了书中建议的写法；与实际定义略有差异__list_node<T>* next;T data;
};

因为list存储节点不是T，所以其迭代器不能使用T*，所以定义了其迭代器

template<class T, class Ref, class Ptr>
struct __list_iterator {// ...typedef __list_node<T> * link_type;// ...link_type node;// ...
};

__list_iterator迭代器的操作符*，->操作符比较明显为：node->data, &node->data;

对于操作符++，和--，分别对应于node=node->next,及node=node->pre;

list采用双向环形链表，list成员只包含一个节点node；

template <class T, class Alloc = alloc>
class list {protected:typedef __list_node<T> list_node;public :typedef list_node* link_type;protected:link_type node;...
};

因为是环形结构，node本身即为list的end，node->next即为list的起始节点；

iterator begin() {return node->next;}
iterator end()   {return node;}
bool empty() const {return node->next == node;}
reference front() {return *begin();}
reference back() {return *(end()--);}

list的insert操作比较简明：

iterator insert(iterator position, const T&x) {link_type tmp = create_node(x);tmp->next = position.node;tmp->pre  = position.node->pre;position.node->pre->next = tmp;position.node->pre = tmp;return tmp;    }

指针插入前后指向情况如下

​​​​​​​

此外，lsit还提供了splice及merge操作，splice用于拼接，merge是两个有序list的合并，看上去很适合归并排序当中的合并操作；

此外在书中，提到了sort函数，用的快排的代码，用到了swap及merge，没能理解，（可能是前面漏掉了部分函数的定义，没有理解算法的含义；等看到了后再补充这块的学习内容）

参考文档《STL源码剖析--侯捷》