前言
本文章进入C++STL之list的模拟实现。
一、list的三个类的关系分析图
在STL标准库实现的list中，这个链表是一个== 双向带头循环链表==。
说明：
list是一个类，成员变量为_head
节点类node，是每一个节点。
list的迭代器也升级成了类，成员变量为node。
- 把迭代器升级成类是为了能够重载++，–，*，！=等可以用在vector迭代器上的操作。
vector和list的区别
| vector | list | |
| 底层结构 | 是一块连续的空间 | 不是连续的空间 |
| 随机访问 | 支持下标随机访问 | 不支持下标随机访问 |
| 插入和删除 | 如果是头插头删，效率为O(n) ，如果插入时需要扩容，会付出更高的代价 | 头插头删都很方便，O(1)的效率 |
| 空间利用情况 | 底层为连续的动态空间，内存碎片小，空间利用率高 | 底层是一块一块不连续的空间，内存碎片多，空间利用率较低 |
| 迭代器 | 使用天然的原生迭代器 | 将迭代器封装起来再对外开放 |
| 迭代器失效 | 在进行插入删除时，插入/删除位置及其之后，空间不再属于自己，由于空间是连续的，其之后的迭代器全部失效 | 在插入时迭代器不会失效，只有在删除时迭代器会失效，且不会影响其他迭代器 |
| 使用场景 | 需要进行大量随机访问，需要高效存储，不关心插入删除。 | 大量插入删除操作时，不关心随机访问 |
vector在内存中是一块连续的地址空间，vector下标就是天然的迭代器。
list在内存中并不连续，所以不支持随机访问。为了能够让list完成诸如vector的操作，比如：
list<int>:: iterator it = lt1.begin(); while (it != lt1.end()) { cout << *it << " "; ++it; }
我们对list的迭代器进行封装，重载各种操作符，以便完成上述的操作。
1.节点的成员变量以及构造函数
在数据结构之链表中，我们知道一个节点必须包含prev,next,val三个变量，在STL的list也是如此。
template<class T> //class list_node 如果这样写，节点的所有成员都是私有的，无法直接访问 struct list_node { list_node<T>* _prev; list_node<T>* _next; T _val; //节点的构造函数 list_node(const T& val = T()) :_prev(nullptr) , _next(nullptr) , _val(val) {} };
注意：
1.在C++，struct升级成了类，但如果不标明，struct的所有成员都是公有的。
2.类名不是类型，不能使用list_node*来作为指针的类型。要使用模板来作为类型。
2.list的迭代器
需要注意的一个点：
- list的迭代器是用来访问的，而不是用来管理节点的空间，所以list的空间是由自己管理和释放的，我们知道，程序崩溃主要就是同一块空间释放两次。
- 所以list的迭代器在进行拷贝构造时可以使用浅拷贝，不会造成程序的崩溃。
list<int>:: iterator it = lt1.begin();
对这行代码来说，迭代器不是直接赋值给it的，因为迭代器升级成了类，而不是一个指针。这里会调用迭代器的拷贝构造函数。
list迭代器代码如下：
//迭代器也封装起来，形成我们熟悉的*it,++it template<class T, class Ref, class Ptr> //class __list_iterator 如果这样写，迭代器是私有的，无法直接使用 //迭代器使用类模板，为了重载Ref，Ptr，设置3个模板参数 struct __list_iterator { typedef list_node<T> Node; typedef __list_iterator<T, Ref, Ptr> self; //等价于： //typedef __list_iterator<T, T&, T*> self; Node* _node; //成员 __list_iterator(Node* node) :_node(node) {} //返回引用，可读可写 Ref operator*() { return _node->_val; } //返回地址 Ptr operator->() { return &_node->_val; } //返回迭代器本身 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; } bool operator!=(const self& it) const { return _node != it._node; } bool operator==(const self& it) const { return _node == it._node; } };
- 1.使用三个模板参数的原因：
- 要求返回指针，如：用指针->访问成员的情况；或者返回迭代器本身的情况，如 ++ ，–操作。
- 2.在重载operator->()时，返回的是val的地址，所以我们在调用该函数时，需要进行两次->操作才能访问成员变量。
比如：
struct A { A(int a1 = 0, int a2 = 0) :_a1(a1) , _a2(a2) {} int _a1; int _a2; }; bit::list<A>lt2; lt2.insert(lt2.begin(), A(1, 1)); lt2.insert(lt2.begin(), A(2, 2)); list<A>::iterator it = lt2.begin(); while (it != lt2.end()) { //迭代器重载了*，返回T&,也就是A本身 cout << it->_a1 << " " << it->_a1 << endl; ++it; } cout << endl;
本质上，应该需要 it->->_al，it->->_a2才能够访问成员。
第一个it->是调用operator->重载，返回val的地址，第二个->是通过地址访问成员。
编译器为了简化操作，以及看起来没有那么别扭，对it->->_a1进行简化成了it->_a1。
- 3.类模板中的Ref是Reference，是引用的意思，Ptr是Pointer，是指针的意思。通过这两个模板名可以知道迭代器需要支持&，和*的操作。
- 4.迭代器被重命名成self，也就是迭代器本身，在++，–操作时，需要返回迭代器本身。
二、list的增删查改工作
2.1insert()
在pos位置之前插入val值。
首先要获取pos位置的前一个节点，记为posprev。
将新的节点插入即可。
iterator insert(iterator pos, const T& val) { Node* newnode = new Node(val); Node* inspos = pos._node; Node* posprev = inspos->_prev; newnode->_next = inspos; inspos->_prev = newnode; newnode->_prev = posprev; posprev->_next = newnode; ++_size; return posprev; }
list的插入没有迭代器的失效问题。
2.2erase()
删除pos位置的节点，并返回pos位置的下一个位置的迭代器。
iterator erase(iterator pos) { assert(pos != end()); Node* erapos = pos._node; Node* eraprev = erapos->_prev; Node* eranext = erapos->_next; eraprev->_next = eranext; eranext->_prev = eraprev; erapos->_prev = erapos->_next = nullptr; delete erapos; --_size; return eranext; }
erase后pos位置的迭代器会失效，我们需要返回下一个位置的迭代器来防止继续访问出现失效的情况。
删除后如果迭代器不更新，继续访问会出现野指针问题。
2.3 push_back(),pop_back(),push_front(),pop_front()
这几个函数分别是：尾插，尾删，头插，头删，我们复用insert和erase即可完成。
void push_back(const T& x) { insert(end(), x); } void pop_back() { erase(--end()); } void push_front(const T& x) { insert(begin(), x); } void pop_front() { erase(begin()); }
2.4clear()
该函数是将链表的所有节点全部释放，哨兵位头节点除外。
//把所有的节点都释放了，除了哨兵位的头节点 void clear() { iterator it = begin(); while (it != end()) { //为防止迭代器失效，erase后会返回pos位置的下一个位置，所以it不需要++ it = erase(it); } _size = 0; }
注意：erase（）删除pos节点后，会返回pos位置的下一个位置，所以这里不需要++it
三、list的默认成员函数
3.1 构造函数
首先申请一个哨兵位的头节点。
void empty_init() { _head = new Node; _head->_prev = _head; _head->_next = _head; _size = 0; } //构造函数，构造出一个链表 list() { empty_init(); }
2.2 拷贝构造
由于我们将迭代器进行了封装升级，现在可以使用++it等操作。
拷贝构造是深拷贝，先new一个_head哨兵位的头节点，再逐个节点进行尾插。
list(list<T>& lt) { empty_init(); list<T>::iterator it = lt.begin(); while (it != lt.end()) { push_back(*it); ++it; ++_size; } }
2.3析构
调用clear函数释放所有空间，再释放头节点。
~list() { clear(); delete _head; _head = nullptr; }
完整代码
namespace bit { //c++不喜欢使用内部类，所以把节点类放在list外面 //节点封装成类 template<class T> //class list_node 如果这样写，节点的所有成员都是私有的，无法直接访问 struct list_node { list_node<T>* _prev; list_node<T>* _next; T _val; //节点的构造函数 list_node(const T& val = T()) :_prev(nullptr) , _next(nullptr) , _val(val) {} }; //迭代器也封装起来，形成我们熟悉的*it,++it template<class T, class Ref, class Ptr> //class __list_iterator 如果这样写，迭代器是私有的，无法直接使用 //迭代器使用类模板，为了重载Ref，Ptr，设置3个模板参数 struct __list_iterator { typedef list_node<T> Node; typedef __list_iterator<T, Ref, Ptr> self; //等价于： //typedef __list_iterator<T, T&, T*> self; Node* _node; //成员 __list_iterator(Node* node) :_node(node) {} //返回引用，可读可写 Ref operator*() { return _node->_val; } //返回地址 Ptr operator->() { return &_node->_val; } //返回迭代器本身 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; } bool operator!=(const self& it) const { return _node != it._node; } bool operator==(const self& it) const { return _node == it._node; } }; template<class T> class list { //节点不希望对外开发,把节点封装起来。 typedef list_node<T> Node; public: //迭代器对外开放即可访问节点 //这个迭代器是给链表用的。 typedef __list_iterator<T, T&, T*> iterator; typedef __list_iterator<T, const T&, const T*> const_iterator; iterator begin() { //return iterator(_head->_next); return _head->_next; // 单参数的构造函数可以进行隐式类型转换，从节点的指针转换成一个类 } iterator end() { //return iterator(_head); return _head; } const_iterator begin() const { return const_iterator(_head->_next); //return _head->_next; // 单参数的构造函数可以进行隐式类型转换，从节点的指针转换成一个类 } const_iterator end() const { return const_iterator(_head); //return _head; } void empty_init() { _head = new Node; _head->_prev = _head; _head->_next = _head; _size = 0; } //构造函数，构造出一个链表 list() { empty_init(); } //拷贝构造 //lt2(lt1) list(list<T>& lt) { empty_init(); list<T>::iterator it = lt.begin(); while (it != lt.end()) { push_back(*it); ++it; ++_size; } } //析构 ~list() { clear(); delete _head; _head = nullptr; } //把所有的节点都释放了，除了哨兵位的头节点 void clear() { iterator it = begin(); while (it != end()) { //为防止迭代器失效，erase后会返回pos位置的下一个位置，所以it不需要++ it = erase(it); } _size = 0; } void swap(list<T>& tmp) { std::swap(_head, tmp._head); std::swap(_size, tmp._size); } //赋值运算符重载 //先调用拷贝构造，再调用赋值重载 //lt3 = lt1 //lt1先拷贝构造给tmp list<T>& operator=(list<T> tmp) { swap(tmp); //出了作用域，调用析构 return *this; } size_t size() const { return _size; } //尾插传过来的是一个数据，而不是一个节点 void push_back(const T& x) { //Node* tail = _head->_prev; 调用构造 //Node* newnode = new Node(x); //tail->_next = newnode; //newnode->_prev = tail; //_head->_prev = newnode; //newnode->_next = _head; insert(end(), x); } void pop_back() { //Node* del = _head->_prev; //_head->_prev = del->_prev; //del->_prev->_next = _head; //del->_next = del->_prev = nullptr; //delete del; //左闭右开，需要-- erase(--end()); } void push_front(const T& x) { insert(begin(), x); } void pop_front() { erase(begin()); } //在pos位置之前插入val //不会出现迭代器失效问题 iterator insert(iterator pos, const T& val) { Node* newnode = new Node(val); Node* inspos = pos._node; Node* posprev = inspos->_prev; newnode->_next = inspos; inspos->_prev = newnode; newnode->_prev = posprev; posprev->_next = newnode; ++_size; return posprev; } //迭代器封装成了类，所以需要通过迭代器找到节点 //防止迭代器失效，返回删除节点的下一个 iterator erase(iterator pos) { assert(pos != end()); Node* erapos = pos._node; Node* eraprev = erapos->_prev; Node* eranext = erapos->_next; eraprev->_next = eranext; eranext->_prev = eraprev; erapos->_prev = erapos->_next = nullptr; delete erapos; --_size; return eranext; } private: Node* _head; size_t _size; }; }
总结
本文章完成了list的常用接口的模拟实现。
