List的模拟实现（2）

前言

上一节我们讲解了list的基本功能，那么本节我们就结合底层代码来分析list是怎么实现的，那么废话不多说，我们正式进入今天的学习：）

List的底层结构

我们先来看一下list的底层基本结构：

这里比较奇怪的一点是底层选择了void*来表示链表的指针，其实可以不用这么做

接下来是迭代器部分：

模拟实现链表难就难在实现迭代器，因为链表的物理空间不是连续的，所以不能简单的通过typedef一个指针变量来达到实现迭代器的目的

链表为空的初始化：

链表为空时不是简单的把所有的指针都赋空指针，而是创建一个节点，让这个节点的next和prev指针都指向自己。这就是创造了一个头节点，这里涉及到数据结构阶段双向带头链表的基本知识

get_node是申请节点，调用了内存池，由于我们还没有学习内存池，所以可以简单地将这里理解为malloc

下面是源代码中的头插尾插接口：

通过这些，我们可以知道，单纯实现链表的功能是没有什么难度的，和我们之前实现string和vector差不多，难就难在理解迭代器的实现

既然底层结构已经看的差不多了，那我们现在就来实现一下list吧

List的模拟实现

节点的基本结构

首先要实现链表的基本结构，链表的基本结构是节点：

	template<class T>struct list_node{list_node(const T& data = T()):_data(data),_next(nullptr),_prev(nullptr){}T _data;list_node<T>* _next;list_node<T>* _prev;};

链表的借本结构

构造函数 

先来实现一下构造函数，根据底层是双向带头循环链表，写出代码如下：

	template<class T>class list{public:typedef list_node<T> Node;list(){_head = new Node(T());_head->_next = _head;_head->_prev = _head;_size = 0;}private:Node* _head;size_t _size;};

 size和empty函数

实现size和empty函数，由于代码很简单，就不做讲解了：

		size_t size(){return _size;}bool empty(){return _size == 0;}

迭代器

因为不是每一个STL的容器都是存储在连续的物理空间之中，所以并不是每一个容器都支持下标+[]访问，但是所有的容器都有迭代器，都支持范围for，因此实现迭代器是很重要的一个步骤，我们来逐步分析迭代器的实现：

我们知道，对于一个节点而言，*解引用以后找到的不是节点的值，而是节点的地址；因为存储空间不连续，不能通过++来找到下一个节点，所以就不能仅通过typedef来实现迭代器，此时我们就应该考虑封装+运算符重载来实现迭代器，主要内容就是重载 *  ++    != 等，让其满足与其他迭代器相同的作用

	template<class T>struct list_iterator{Node* _node;};

迭代器的构造函数

---

		list_iterator(Node* node):_node(node){}

重载*

		T& operator*(){return _node->_data;}

重载前置++、--

由于++以后返回的数据类型依旧是迭代器，为了书写简便一点，调用typedef：

		Self& operator++(){_node = _node->_next;return *this;}Self& operator--(){_node = _node->_prev;return *this;}

重载后置++、-- 

因为后置++和--是将当前的值使用以后再执行++或者--，所以我们需要把原本的值拷贝一份，用于完成返回操作：

		Self& operator++(int){Self tmp(*this);_node = _node->_next;return tmp;}Self& operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}

重载!=、==

		bool operator!=(const Self& s){return _node != s._node;}bool operator==(const Self& s){return _node == s._node;}

重载-> 

先来分析一下为什么需要重载->这个符号：

接下来先构造一个使用->的情景：

假设有一个这样的结构体：

	struct AA{int _aa1 = 1;int _aa2 = 2;};

此时我们要在链表中存入这个结构体并且打印：

		list<AA> ltaa;ltaa.push_back(AA());ltaa.push_back(AA());ltaa.push_back(AA());ltaa.push_back(AA());list<AA>::iterator itaa = ltaa.begin();while (itaa != ltaa.end()){cout << *itaa << " ";++itaa;}cout << endl;

此时运行以后发现编译不通过

这里面的itaa通过解引用会得到节点中的data，data的数据类型是T，也就是自定义类型AA。因为没有重载流插入，所以这里的自定义类型无法打印，要想解决这个问题有两种方法：

第一种方法：给AA重载流插入

第二种方法：逐一访问结构体中的元素

		list<AA>::iterator itaa = ltaa.begin();while (itaa != ltaa.end()){cout << (*itaa)._aa1 << " and " << (*itaa)._aa2 << endl;++itaa;}cout << endl;

此时代码就成功运行了

但是这样写就很麻烦，此时就可以重载->这个运算符，这里先把代码写出来再对其进行分析：

		T* operator->(){return &_node->_data;}

		list<AA>::iterator itaa = ltaa.begin();while (itaa != ltaa.end()){cout << itaa->_aa1 << " and " << itaa->_aa2 << endl;++itaa;}cout << endl;

---

疑难解答：为什么operator-> 操作符重载函数返回值 T* 而不是 T&

在 list_iterator 这个迭代器类模板中，operator-> 操作符重载函数设计为返回 T* 而不是 T&，这与 operator-> 操作符的特殊语义和 C++ 语言的规定有关：

在 C++ 中，operator-> 操作符有特殊的处理规则。当我们使用 -> 操作符时，编译器会尝试不断应用 -> 操作，直到得到一个非指针类型的对象

简单地说就是：当你使用迭代器 it 调用 it->member 时，编译器会先调用 it.operator->()，如果 operator->() 返回的是一个指针，那么就直接访问该指针指向对象的成员；如果返回的不是指针，编译器会再次对返回值应用 ->

我们可以分两点来说明返回 T* 的合理性：

1. 符合使用习惯

迭代器的 operator-> 操作符通常用于模拟指针的行为，返回 T* 可以让迭代器像指针一样使用

例如，对于一个存储自定义类型 MyClass 的链表，使用迭代器访问 MyClass 的成员时，我们希望能够像使用指针一样直接通过 -> 操作符访问成员，如下所示：

namespace xiaobai
{template<class T>struct list_node{list_node(const T& data = T()): _data(data), _next(nullptr), _prev(nullptr) {}T _data;list_node<T>* _next;list_node<T>* _prev;};template<class T>struct list_iterator{typedef list_node<T> Node;typedef list_iterator<T> Self;list_iterator(Node* node) : _node(node){}T& operator*() {return _node->_data;}Self& operator++() {_node = _node->_next;return *this;}bool operator!=(const Self& s) {return _node != s._node;}T* operator->() {return &_node->_data;}Node* _node;};
}int main() 
{xiaobai::list_node<MyClass> node(MyClass(10));xiaobai::list_iterator<MyClass> it(&node);// 使用迭代器的 -> 操作符访问成员std::cout << it->value << std::endl;return 0;
}

在这个例子中，it->value 能够正常工作，因为 operator->() 返回的是 MyClass* 类型的指针，编译器可以直接通过该指针访问 value 成员

2. 避免额外的复杂度

如果 operator->() 返回 T&，编译器会再次对返回的引用应用 -> 操作，这会导致代码逻辑变得复杂，而且可能不符合用户的预期

例如：若T是一个自定义类型，由于T&不是指针类型，编译器会尝试调用 T 类型的 operator->() 函数，这可能会引发编译错误或意外的行为

所以T* operator->() 是为了让迭代器能够像指针一样使用，符合用户的使用习惯，并且遵循了 C++ 中 operator-> 操作符的特殊语义。而 T& operator->() 会破坏这种语义，导致代码逻辑复杂且不符合预期，因此通常不这样设计

---

这段代码初步看起来会很奇怪，它这里实际应该是两个箭头，但是为了可读性省略了一个箭头

（具体细节请浏览上面的疑难解答） 

cout << itaa.operator->()->_aa1 << " and " << itaa.operator->()->_aa2 << endl;

第一个箭头是运算符重载，返回的是AA*类型的变量

第二个箭头是原生指针，通过这个箭头就可以访问到list中的数据了

 迭代器代码初步集合

到这里我们就完成了迭代器：

	template<class T>struct list_iterator{typedef list_node<T> Node;typedef list_iterator<T> Self;list_iterator(Node* node):_node(node){}T& operator*(){return _node->_data;}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& s){return _node != s._node;}bool operator==(const Self& s){return _node == s._node;}T* operator->(){return &_node->_data;}Node* _node;};

此时再去链表的类中typedef迭代器，简化书写：

	template<class T>class list{public:typedef list_node<T> Node;typedef list_iterator<T> iterator;//.......private:Node* _head;size_t _size;};

---

重载打印容器以及对迭代器的修缮

实现了迭代器，就满足了范围for遍历，此时就可以写一个访问容器的接口，因为所有容器都具有迭代器，所以这个接口也可以访问其他STL容器

	template<class Container>void print_container(const Container& con){for (auto e : con){cout << e << " ";}cout << endl;}

现在测试一下这个打印：

		list<int> lt;ltaa.push_back(1);ltaa.push_back(2);ltaa.push_back(3);ltaa.push_back(4);print_container(lt);

此时运行代码却发现编译报错了，为什么函数外面使用范围for可以打印，但是print_container函数里面使用范围for却打印不了，这是为什么呢？

因为函数里面的参数是const参数，函数外面是普通的参数，我们还没有实现const迭代器，所以这里就会报错

再来分析一下const迭代器的特征：先思考一下const迭代器为什么是const_iterator而不是普通的iterator加上前置的const修饰?

要想想清楚这个问题，我们首先需要明白const迭代器是自身不能修改还是指向的内容不能修改。这里我们结合指针不同位置的const意义来理解：

T* const ptr;
const T* ptr;

第一种：指针本身不允许改变

第二种：指针指向的内容不允许改变

很明显的，const迭代器是想完成第二种功能，如果是const iterator的话，const的作用是确保iterator本身不被修改，迭代器本身不能修改的话就无法实现遍历。const迭代器的产生是为了在保证遍历的前提之下保证迭代器指向的内容也不被修改

那么该怎么修改代码来完成这一目的呢？

我们在实现迭代器这一个类时，对数据的修改接口是operator*以及operator->，对于const迭代器而言，返回类型就应该加上const：

		const T& operator*(){return _node->_data;}const T* operator->(){return &_node->_data;}

所以这里就需要拷贝之前的普通迭代器代码，再在*和->的重载中加上const完成const迭代器

	template<class T>struct list_const_iterator{typedef list_node<T> Node;typedef list_iterator<T> Self;list_iterator(Node* node):_node(node){}const T& operator*(){return _node->_data;}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& s){return _node != s._node;}bool operator==(const Self& s){return _node == s._node;}const T* operator->(){return &_node->_data;}Node* _node;};

此时在重载一下begin和end函数，给一个const迭代器版本，并且在list类中typedef const迭代器：

（普通迭代器可以调用const迭代器的begin和end，因为权限可以缩小；反之const迭代器无法调用普通迭代器的begin和end，因为权限不能放大）

	template<class T>class list{public:typedef list_node<T> Node;typedef list_iterator<T> iterator;typedef list_const_iterator<T> const_iterator;iterator begin(){return _head->_next;}iterator end(){return _head;}const_iterator begin() const{return _head->_next;}const_iterator end() const{return _head;}//........private:Node* _head;size_t _size;};

**************************************************************************************************************

在 list 类中重载 `begin` 和 `end` 函数（即提供 `const` 和非 `const` 版本）是为了支持对 `const` 对象和非 `const` 对象的迭代操作，下面详细解释原因：

1. 支持非 `const` 对象的迭代

当你有一个非 `const` 的 `list` 对象时，你可能希望能够修改列表中的元素。此时，你需要使用非 `const` 迭代器，因为非 `const` 迭代器允许对其所指向的元素进行修改。非 `const` 版本的 `begin` 和 `end` 函数返回的就是非 `const` 迭代器

2. 支持 `const` 对象的迭代

当你有一个 `const` 的 `list` 对象时，你不应该修改列表中的元素，因为这违反了 `const` 限定的语义。此时，你需要使用 `const` 迭代器，`const` 迭代器只能用于访问元素，而不能修改元素。`const` 版本的 `begin` 和 `end` 函数返回的就是 `const` 迭代器

3. 函数重载的实现

通过函数重载，编译器会根据对象是否为 `const` 来选择合适的 `begin` 和 `end` 函数版本。如果对象是 `const` 的，编译器会调用 `const` 版本的 `begin` 和 `end` 函数，返回 `const` 迭代器；如果对象是非 `const` 的，编译器会调用非 `const` 版本的 `begin` 和 `end` 函数，返回非 `const` 迭代器。

重载 `begin` 和 `end` 函数是为了提供对 `const` 对象和非 `const` 对象的一致迭代接口，同时保证 `const` 对象的元素不被意外修改，遵循了 C++ 的 `const` 正确性原则，使得代码更加安全和灵活。

**************************************************************************************************************

 此时用一个很特别的用例来测试一下代码（这里修改了一下print_container函数）：

	template<class Container>void print_container(const Container& con){list<int>::const_iterator it = con.begin();while(it != con.end()){*it += 10;cout << *it << " ";++it;}cout << endl;for (auto e : con){cout << e << " ";}cout << endl;}void test_list01(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);list<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;}

可以看到，这里非常奇怪，明明我们故意在打印容器代码里面修改了const迭代器指向的内容，想让它报错，但是代码却成功运行了，这是为什么呢？

这就涉及到我们之前提及的按需实例化，这里的代码存在着编译错误，' *it += 10 ' 中的*it返回的数据类型应该是const T&，对其进行+=10操作本身是应该编译报错的，但是这里非但没有报错反而还运行成功了

之所以产生这样的结果，是因为模板和类模板都会走按需实例化。模板不能被直接调用，模板用于将对应类型的代码实例化出来，实例化出来的代码才能够使用

因为我们在主函数中没有使用print_container函数，编译器在编译的过程中就不会去实例化print_container函数里面的内容，而没有实例化的代码编译器只会对其进行很简单的语法检查，比如：语句结束没加分号，对于细枝末节的操作编译器不会检查。

此时如果使用print_container函数就会报错：

        list<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;print_container(lt);

对迭代器代码的简化

刚才那种实现方式我们的确能成功的完成任务，但是const迭代器和普通迭代器除了operator*和->的代码有区别以外，其他地方的代码一模一样，这么设计的话在代码长度上就会非常的冗余，我们去底层观察一下是怎么实现迭代器的：

可以看到，它没有将迭代器和const迭代器定义为两个类，而是同一个类模板。而且它除了传入了 T ，还传入了 T& 和 T* 这两个参数

如果是普通迭代器，它的中的参数是 T T& T* ，分别传给了参数 T Ref Ptr ，而 Ref 和 Ptr 分别被重命名为 reference 和 pointer ，而 reference 和 pointer 分别又是 operator* 和 operator-> 的返回值；

如果是const迭代器，它的中的参数是 T 、const T&、 const T* ，分别传给了参数 T Ref Ptr ， Ref 和 Ptr 分别被重命名为 reference 和 pointer ，而 reference 和 pointer 分别又是 operator* 和 operator-> 的返回值；

通过这种形式就控制住了operator*和->的返回值

虽然这两种写法在本质上没有区别，只是之前的写法是自己写了两个类，而这种方法是实现了一个类模板并且传了不同的模板参数给编译器，通过编译器来实例化出两个类。通过这样的方法，我们就可以实现精简代码的需求

那么就根据底层实现的原理来完善一下原来的代码吧：

	template<class T, class Ref, class Ptr>struct list_iterator{typedef list_node<T> Node;typedef list_iterator<T, Ref, Ptr> Self;Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}//.......Node* _node;};

	template<class T>class list{public:typedef list_node<T> Node;typedef list_iterator<T, T&, T*> iterator;typedef list_iterator<T, const T&, const T*> const_iterator;//.......private:Node* _head;size_t _size;};

 迭代器代码的最终整合

	template<class T, class Ref, class Ptr>struct list_iterator{typedef list_node<T> Node;typedef list_iterator<T, Ref, Ptr> Self;list_iterator(Node* node):_node(node){}Ref operator*(){return _node->_data;}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& s){return _node != s._node;}bool operator==(const Self& s){return _node == s._node;}Ptr operator->(){return &_node->_data;}Node* _node;};

---

begin、end函数

begin函数用于返回链表第一个元素：

		iterator begin(){iterator it(_head->_next);return it;}

也可以用返回匿名对象来简化代码：

			return iterator(_head->_next);

还有一种更加简单的写法：

			return _head->_next;

因为这里返回的是一个节点的指针，节点的指针是可以隐式类型转换成iterator的，单参数的构造函数支持隐式类型的转换

---

end函数同理：

		iterator end(){return _head->_prev;}

---

到这里，我们来测试一下：

		list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);list<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;

这里迭代器的设计相当完美，假设链表为空，此时就只有一个哨兵位的头节点。由于begin是_head的next，此时它指向的还是自己。end是_head，也同样指向自己，此时it = begin() == end在条件判断的时候就不会进入循环，造成非法访问

我们在实现迭代器的时候没有写拷贝构造函数，这就意味着指针在与指针的拷贝的时候进行的是浅拷贝，那么浅拷贝会不会出现问题呢？

答案是不会，我们就以上面的测试代码为例，我们给it赋了头节点，此时我们期望的就是it也指向原来的头节点，就是需要浅拷贝，而不是开一个新的链表，指向新的链表中的头节点

这里的迭代器只是一个访问和遍历链表的工具，它不像vector、string等容器一样，它所指向的资源并不是属于它自己的，它指向的资源是属于list的。所以它也不要写析构函数，它不能去释放list的空间

---

insert函数

insert函数用于在pos位置之前插入数据，要想实现这个功能还是比较简单的，仅需要通过简单的修改指针指向即可：

		void insert(iterator pos, const T& x){Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);newnode->_next = cur;cur->_prev = newnode;newnode->_prev = prev;prev->_next = newnode;}

---

push_back和push_front函数

可以通过复用insert函数完成这两个函数：

		void push_back(const T& x){insert(end(), x);}void push_front(const T& x){insert(begin(), x);}

---

erase函数

erase函数用于删除pos位置的节点，这个函数的实现也很简单，也是只需要修改指针指向再释放节点即可：

注意erase不能删除哨兵位的头节点，在这里加上assert断言

		void erase(iterator pos){assert(pos != end());Node* prev = pos._node->_prev;Node* next = pos._node->_next;prev->_next = next;next->_prev = prev;delete pos._node;}

---

pop_back和pop_front函数

通过复用erase即可实现这两个函数：

		void pop_back(iterator pos){erase(--end());}void pop_front(iterator pos){erase(begin());}

结尾

因为链表很多接口的实现非常简单，这里就没有把所有接口的实现代码一一列举出来了，下一节我们接着分析链表，我们将会分析迭代器失效。那么本节的内容就到此结束了，谢谢您的浏览！！！！！！！！！