STL—list—模拟实现【迭代器的实现(重要)】【基本接口的实现】

STL—list—模拟实现

1.list源代码

要想模拟实现list，还是要看一下STL库中的源代码。

_list_node里面装着指向上一个节点的指针prev，和指向下一个节点的指针next，还有数据data

并且它给的是void*，导致后面进行节点指针的返回时需要进行强转

前面的link_type就是节点的指针类型，对(*node).next进行强转。

这样有点麻烦，我自己的模拟实现就不搞这个void*了，直接给节点的指针类型，这样后面不用强转。

2.list模拟实现

为了避免和库里的list发生冲突，我们要自己开辟一个命名空间。名字随意。

首先节点__list_node是一个自定义类型，list是一个带头双向循环链表。

__list_node需要存放三个成员变量，存放的就是一个指向上一个节点的指针_prev，一个指向下一个节点的指针_next，还有存放的数据_data。

list需要存放一个指向头节点（哨兵位）的指针_head

namespace wzf
{template<class T>struct __list_node{__list_node<T>* _prev;__list_node<T >* _next;T _data;__list_node(const T& x = T()) // 要给缺省值。因为头节点不好给值，用默认的初始值:_next(nullptr),_prev(nullptr),_data(x){}};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;typedef Reverse_list_iterator<iterator> reverse_iterator;typedef Reverse_list_iterator<const_iterator>const_reverse_iterator;private:Node* _head; };
}

2.1构造函数

list是带头双向循环链表。构造函数的话就开辟一个空间给头节点，然后再让其自身的两个指针指向自己就OK。

		list(){_head = new Node;_head->_next = _head;_head->_prev = _head;}

2.2正向迭代器（重要）

在list的模拟实现中，最重要的就是迭代器的实现。因为他不在是简单的指针了，它有一个自定义类型进行了封装，这个类型里面装的还是节点的指针，通过重载++等运算符去实现迭代器的移动。

为什么要这么做？【因为list是链表，链表的节点不是在物理上不是连续的地址，是一块块的，只是由指针链接到了一起而已。如果直接用节点的指针来做迭代器，在进行++等操作就会出现错误。】

list的迭代器实现：

简单来说就是用一个类型去封装节点的指针，从而构成一个自定义类型。再去重载++等操作符，在重载中去实现节点的迭代

对于实现一个迭代器来说，有两种方法。

一种是原生指针，就是之前的vector的迭代器
第二组就是对一个自定义类型进行封装，让它具备指针的功能。

而我们对list的迭代器实现要通过对自定义类型进行封装

因此这个自定义的类，我们要对其进行封装，重载操作符，让其具备基本功能：

能够进行解引用，因此要重载operator*
能够进行指针的->操作来访问存储的成员的空间，因此要重载operator->
能够进行迭代器的迭代，比如++等操作。因此要重载++，这里前置和后置++都要重载
由于list是带头双向循环链表，因此可以进行–操作，要重载–，前置和后置–都要重载
迭代器要支持是否相等或者不相等，因此要重载!= 和 ==

还有一个要注意的地方，迭代器的应用场景还有一个const迭代器。因此有些情况我们会将容器作为参数传给一个函数，在该函数当中我们并不想去改变容器对象的本身，因此函数的形参是const，我们就需要用const迭代器。具体的一个场景如下：

下面这个函数只想要打印链表的内容，但是不想去改变链表本身，因此形参是const list<int>& l，这个时候const迭代器就派上用场了。

	void print_list(const list<int>& l){// l是const对象，因此cit需要是const的迭代器list<int>::const_iterator cit = l.begin();while (cit != l.end()){cout << *cit << " ";++cit;}cout << endl;}

const迭代器可以通过传三个模版参数去控制调用的是const迭代器还是非const的迭代器

list_iterator<T, T&, T*> -> iterator

__list_iterator<T, const T&, const T*> -> const_iterator

【要注意不是迭代器这个类型的对象为const对象，不然++等操作会报错】

正向迭代器的代码如下：

	// 迭代器 (通过三个模版参数，来控制调用的是const迭代器还是非const的迭代器)// 【要注意不是迭代器这个类型的对象为const对象】// __list_iterator<T, T&, T*> -> iterator// __list_iterator<T, const T&, const T*> -> const_iteratortemplate<class T, class Ref, class Ptr>struct __list_iterator{typedef __list_node<T> Node;typedef __list_iterator<T, Ref, Ptr> Self;Node* _node; // 迭代器中的_node成员变量，存储着目前迭代器所指向的节点。__list_iterator(Node* node = nullptr):_node(node){}//返回Ref，const就返回const，非const返回非const Ref operator*(){return _node->_data; // this->_node->_data;}// Ptr控制返回的是const属性还是非constPtr operator->(){return &_node->_data;}// 前置++Self& operator++() {_node = _node->_next;return *this;}// 后置++Self& operator++(int) // 加这个int才能让编译器知道这个是后置++的重载{/*__list_iterator<T> tmp = *this;_node = _node->_next;return tmp; */// 考虑用代码复用Self tmp(this->_node); // Self tmp(*this); // 如果不实现拷贝构造，传*this去调用系统默认的拷贝构造也可以实现，但是是浅拷贝，要注意实际是否会出错++(*this);return tmp;}// 前置--Self& operator--(){_node = _node->_prev;return *this;}// 后置--Self& operator--(int){/*__list_iterator<T> tmp = *this;_node = _node->_prev; return tmp; */// 考虑用代码复用Self tmp(this->_node);--(*this);return tmp;}bool operator!=(const Self& it) const{return _node != it._node;}};

list的迭代器实现是list的模拟实现的一个重点，这个内容和之前我们的模拟实现不太一样，是通过封装成一个自定义类型实现的，需要仔细思考。

2.3反向迭代器（重要）

反向迭代器其实也可以像正向迭代器那样去实现，但是也可以借助正向迭代器去实现。

反向迭代器的++就是正向迭代器的–，反向迭代器的–就是正向迭代器的++。我们只需要对正向迭代器的接口进行包装就行了。

简单来说就是：反向迭代器内部可以包含一个正向迭代器

思路：

反向迭代器的rbegin指向最后一个数据，rend指向头节点。

具体实现如下：

	// 反向迭代器 (借助正向迭代器实现)template<class iterator>struct Reverse_list_iterator{// 注意：此处typename的作用是明确告诉编译器，Ref是Iterator类中的一个类型，而不是静态成员变量// 否则编译器编译时就不知道Ref是Iterator中的类型还是静态成员变量// 因为静态成员变量也是按照 类名::静态成员变量名 的方式访问的typedef typename iterator::Ref Ref;typedef typename iterator::Ptr Ptr;typedef Reverse_list_iterator<iterator> Self;iterator _it; // 给一个成员变量是 正向迭代器类型的// 构造函数Reverse_list_iterator(iterator it):_it(it){}// 能够具有指针类似行为的* 和 ->的重载Ref operator*(){iterator temp(_it);--temp; // 对于反向迭代器来说，正向迭代器的迭代器整体往后移动一次，才能正常使用。具体可以画图return *temp;}Ptr operator->(){//return &(operator*()); // 让自己去调用*拿到存储的数据Treturn &(_it._node)->_data; //等价于上面}// 具备移动能力，对++，--等运算符进行重载Self& operator++(){--_it; // 反向迭代器的++就是正向的--return *this;}Self& operator++(int){Self tmp(this->_it); // 也可以Self tmp(*this);--_it;return tmp;}Self& operator--(){++_it;return *this;}Self& operator--(int){Self tmp(this->_it);++_it;return *this;}// 具备相比的能力bool operator!=(const Self& rit) const{return _it != rit._it;}bool operator==(const Self& rit) const{return _it == rit._it;}};

2.3拷贝构造

拷贝构造还是我们老生常谈的问题了，要注意浅拷贝问题的出现。

这里如果有忘记要记得复习之前的内容，这里就直接贴代码了、

	// 拷贝构造list(const list<T>& l){_head = new Node;_head->_next = _head;_head->_prev = _head;// 遍历l，进行深拷贝const_iterator it = l.begin();while (it != l.end()){push_back(*it);++it;}// 要想代码简洁一点。可以用范围for，反正支持迭代期间就能支持范围for}

2.4赋值运算符重载

赋值运算符也要注意浅拷贝问题。

要注意赋值运算符的实现和拷贝构造的区别就是

l1(l2)时候的l1是不存在的。
l1 = l2的时候l1是存在的，要注意资源的清理，不然会内存泄漏

传统写法：

		// 赋值运算符重载list<T>& operator=(const list<T>& l){// 防止自己给自己赋值if (this != &l){// 先清除掉自身，清除完再尾插。clear(); // 不清除会内存泄漏。// 直接用范围for。for (auto e : l)push_back(e);}return *this;}

现代写法：

	// 赋值运算符——现代写法list<T>& operator=(list<T> l) // l通过拷贝构造就是我们要的{swap(_head, l._head); // 交换一下，把我们不要的给l，结束该作用域l会调用析构函数来销毁，清除我们不要的数据。return *this;}

2.5析构函数

析构函数我们先清除掉除了头节点的所有节点，然后在清除头节点。不能直接清除头节点，不然会造成内存泄漏

	~list(){clear(); // 除了头节点，其他节点都已经释放了。delete _head; // 释放头节点_head = nullptr;}

2.6 clear()

clear要删除除了头节点的所有节点。

clear通过erase的函数复用

		// clear要注意保留头节点(哨兵位)，因为clear之后可能继续插入数据。void clear(){iterator it = begin();while (it != end()){erase(it++); // ++的处理后，该迭代器不会失效}}

2.7 erase()

iterator erase(iterator pos)

erase要删除节点，要先将pos位置的节点前后关系处理好，再提前用ret记载好pos位置，

删除pos位置的节点，返回ret。

iterator erase(iterator pos)
{assert(pos != end()); // 不能删除哨兵位Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;iterator ret = ++pos; // 要返回pos的下一个节点，因为删除该位置的节点后pos会失效。delete cur; // cur是一个指针类型，指向节点（结构体）的指针cur = nullptr;return ret;
}

2.8 push_back()

list是带头双向循环链表，尾插时要处理好关系。如果忘记其基础物理结构要复习。

		void push_back(const T& x){// 无论该链表是否有节点，下面这段代码都能完成任务。Node* tail = _head->_prev;Node* newnode = new Node(x); // 数据已经插入节点了// 接下来要做的就是处理节点之间的链接关系newnode->_next = _head;newnode->_prev = tail; tail->_next = newnode;_head->_prev = newnode;}

实现了insert之后，可以用其代码复用：

		void push_back(const T& x){// 实现insert了之后，可以代码复用insert(end(), x);}

2.9 pop_back()

直接用erase代码复用

要注意由于erase不能删除头节点，因此要传--end()

		void pop_back(){// 用erase代码复用erase(--end());}

2.10 push_front

这里不再具体实现，直接用erase复现。push_back那边有具体实现

		void push_front(const T& x){// 可以和push_back一样，常规实现，也可以用insert代码复用.insert(begin(), x);}

2.11 pop_front

		void pop_front(){// 代码复用erase(begin());}

2.12 insert

		void insert(iterator pos, const T& x){Node* newnode = new Node(x); // 创建要插入的节点Node* cur = pos._node; // cur指向pos位置的节点Node* prev = cur->_prev; // prev指向pos位置的上一个节点cur->_prev = newnode;prev->_next = newnode;newnode->_next = cur;newnode->_prev = prev;}