简介
C++的STL有六大组件：仿函数， 空间配置器， 算法， 容器， 迭代器，配接器。list属于容器的一种。
list的设计使用了模板，是一种泛型编程。
初识list
模型
list是带哨兵位的双向循环链表。
链表是由一个一个的节点通过指针链接起来的。list的节点设计：prev指针指向前一个节点，next指针指向下一个节点，data储存数据。如下图
而list想要实现双向循环链表，只需用一个指针指向不储存数据的节点——哨兵位节点或头节点。让哨兵位节点将整条链表首尾相连。哨兵位的next是链表的头节点，哨兵位的prev是链表的尾节点，如下图
list容器的优缺点
优点：头部插入，头部删除，尾部插入，尾部删除的时间复杂度位O(1)。list的指针是一直指向哨兵位节点的，通过哨兵位节点能找到链表的头节点和尾节点，从而实现头插，头删，尾插，尾删操作。
缺点：对链表中的数据进行排序的时间复杂度会很高。找链表中的某一个数据时，需要遍历链表。
list的迭代器
list的每个节点在内存中储存不是连续的。
普通的指针不能完成对链表的遍历——加加指针不能使指针指向下一个节点，减减指针不能使指针指向上一个节点。指针的解引用不能完成对数据存取——普通指针解引用是整个节点，而不是节点里存的数据。
所以不能用普通指针做list的迭代器。应该对普通指针进行封装，将封装之后的普通指针作为list的迭代器。该迭代器能完成链表的遍历，数据的存取等操作。
具体怎样封装，下面介绍源代码思路和模拟实现时会详细讲解
迭代器失效：把迭代器指向的节点删除掉，会让该迭代器失效，类似于野指针的问题。在迭代器指向节点的前面或后面插入节点，不会使迭代器失效。
常用接口介绍
获取迭代器
begin
| 返回哨兵位前一个节点的位置 |
end
| 返回哨兵位节点的位置 |
empty
检测list是否为空，是返回true，否则返回false |
size
返回list中有效节点的个数 |
front
返回list的第一个节点中值的引用 |
back
返回list的最后一个节点中值的引用 |
insert
在list的 position 迭代器指向的节点之前插入值为val的节点,返回新插入节点的迭代器 |
push_front
| 在链表的头部插入一个值为val的节点 |
pop_front
| 删除头部位置的节点 |
erase
删除position迭代器指向的节点，或删除从first到last迭代器区间的节点，返回下一个位置的迭代器 |
push_back
| 在链表的尾部插入值为val的节点 |
pop_back
| 删除最后一个节点 |
clear
| 删除所有有效节点 |
源代码思路
下面内容参考侯捷老师的《STL源码剖析》
源代码中涉及空间配置器的部分不做重点讲解，只需知道空间配置器是为了给节点list申请空间的即可。
小编摘抄部分源码，带大家了解list设计的大概框架。具体实现的细节在模拟实现时讲解
节点设计
template <class T> struct __list_node { typedef void* void_pointer; void_pointer* prev; void_pointer* next; T data; }
struct在C语言中是结构体，在C++中是类。用struct封装不加访问限定符默认成员是公有的。迭代器和链表需要访问节点的数据，设计成共有是为了方便访问。设计成私有需要声明友元。
prev和next的指针是void*类型是因为不知道数据的类型，源码在实现其他接口时会把void*进行强转。和下面代码的设计是等价的
__list_node<T>* prev; __list_node<T>* next；
data是用来储存数据的
迭代器的设计
template <class T, class Ref, class Ptr> struct __list_iterator { typedef __list_iterator<T, T&, T*> iterator; typedef __list_iterator<T, Ref, Ptr> self; typedef T value_type; typedef Ptr pointer; typedef Ref reference; typedef __list_node<T>* link_type; link_type node; //节点指针 核心数据 //运算符重载，为了让node能像普通指针一样 //解引用重载 reference operator*()const //Ref { return (*node).data; } //->运算符重载 pointer operator->() const //Ptr { return &(operator*()); } //++运算符重载..... //--运算符重载.... //==运算符重载.... //...... }
成员全部共有，方便list访问
Ref和Ptr两个模板参数是为了区分普通迭代器和const迭代器，如下代码
typedef __list_iterator<T, T&, T*> iterator; //迭代器别名 typedef __list_iterator<T, const T&, const T*> const_iterator; //const迭代器别名
如下图
node是节点的指针，是核心数据。在迭代器这个类中，重载了* -> ++ -- == != 运算符是为了让结点指针能像普通指针一样，完成对链表的遍历和对数据的存取。这便是封装的魅力。
list的设计
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指向哨兵位节点，便可以通过迭代器对整条链表增删查改。
begin()
iterator begin() { return (link_type)((*node).next); }
获取哨兵位节点的下一个指针next，但next是void*类型的指针，需要强转成节点类型的指针
end()
iterator end() { return node; }
获取尾节点的下一个节点的指针——哨兵位节点指针
空构造
void empty_initialize() { node = get_node(); //为哨兵位开空间 node->next = node; //没有有效节点，首尾指针都指向自己 node->prev = node; } list()//构造函数，构造空链表 { empty_initialize(); }
list是允许构造空链表的
insert()
iterator insert (iterator position, const T& x) { link_type tmp = create_node(x); tmp->next = position.node; tmp->prev = position.node->prev; (link_type(position.node->prev))->net = tmp; position.node->prev = tmp; return tmp; }
上述代码中有经过封装的函数。但大致思路如下图
push_back
void push_back(const T& x) { insert(end(), x); }
复用insert
模拟实现
目的：源代码的变量经过了嵌套的typedef，函数经过层层封装。用源代码理解list的实现细节和运行机制并不容易。用源代码的的框架和实现思路实现一个简易的list，帮助我们更好的理解list。
模拟实现是用new和delete，管理list的内存。
节点设计
template <class T> struct __list_node { T* prev;//指向前一个节点 T* next;//指向后一个节点 T data;//储存数据 __list_node(const T& val = T()) //构造函数 :prev(nullptr) , next(nullptr) //参数列表 , data(val) { } };
迭代器设计
template <class T, class Ref, class Ptr> //封装指针 struct __list_iterator { typedef __list_iterator<T, Ref, Ptr> self; //迭代器别名 typedef __list_node<T> list_node; //节点别名别名 list_node* p_node; //节点指针 __list_iterator(list_node* val) :p_node(val) { }; T operator*()//解引用重载 { return p_node->data; }; Ref operator*()//解引用重载 { return p_node->data; }; T operator->() { return &p_node->data; } Ptr operator->() { return &p_node->data; } self& operator++()//加加运算符重载 { return p_node->next; }; bool operator!=(const self val)//不等于运算符重载 { return p_node != val.p_node; }; bool operator==(const self val)//等于运算符重载 { return p_node == val.p_node; }; };
list设计
框架
template <class T> class list { typedef __list_node<T> list_node; //节点指针别名 typedef __list_iterator<T, T&, T*> iterator; //迭代器别名 typedef __list_iterator<T, const T&, const T*> const_iterator; //const迭代器别名 public: //接口...... private: list_node* head_node;//头节点，只要一个指针便可代表整个链表 };
获取迭代器
iterator begin() { return head_node->next; } const_iterator begin() { return head_node->next; } iterator end() { return head_node; } const_iterator end() { return head_node; }
空构造
void empty_init() { head_node = new list_node; head_node->_prev = head_node; head_node->_next = head_node; } list() { empty_init(); }
insert
iterator insert(iterator pos, const T& x)//指定位置插入 { list_node* cur = pos.p_node; //用临时指针指向迭代器位置的节点 list_node* prev = cur->prev; //用临时指针指向该节点的下一个节点 list_node* newnode = new list_node(x); //构造新节点 prev->next = newnode; //改变指向 newnode->next = cur; cur->prev = newnode; newnode->prev = prev; return newnode; //返回新节点的迭代器 }
代码思路如下图
erase
iterator erase(iterator pos)//指定位置删除 { assert(pos != end()); //不能删哨兵位 list_node* cur = pos.p_node; //用临时指针指向前中后三个节点 list_node* prev = cur->prev; list_node* next = cur->next; prev->next = next; //改变指向 next->prev = prev; delete cur;//删除该节点 return next; //返回下一个位置的节点的迭代器 }
赋值重载
现在写法
void swap(list<T>& lt) { std::swap(head_node, lt.head_node); } list<T>& operator=(list<T> lt) { swap(lt); return *this; }
其他接口
void push_back(const T& x) { insert(end(), x); } void push_front(const T& x) { insert(begin(), x); } void pop_back() { erase(--end()); } void pop_front() { erase(begin()); }
本篇内容到此结束啦
