探索C嘎嘎的奇妙世界:第十九关---STL(list的模拟实现)

1. 基本框架

首先，我们先从节点的准备工作入手，请看示例：        

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
//节点
template<class T>
struct ListNode
{ListNode<T>* _next;ListNode<T>* _prev;T _data;ListNode(const T& data = T()):_next(nullptr), _prev(nullptr), _data(data){}
};

在上述代码中：先定义一个双向链表的节点结构ListNode。节点结构ListNode包含以下成员变量：
        1. _next：指向下一个节点的指针。
        2. _prev：指向上一个节点的指针。
        3. _data：存储节点数据的变量。

        节点结构ListNode还包含一个构造函数，用于初始化成员变量。构造函数接受一个参数data，用于初始化_data成员变量。如果没有提供参数，则_data成员变量的默认值为T()，即T类型的默认构造函数的返回值。

        该头文件还使用了iostream和assert.h两个标准头文件，并使用了std命名空间。

2. 封装迭代器

请看示例代码：

	//迭代器template<class T, class Ref, class Ptr>struct ListIterator{typedef ListNode<T> Node;typedef ListIterator<T, Ref, Ptr> Self;Node* _node;ListIterator(Node* node):_node(node){}// ++it;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;}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!=(const Self& it){return _node != it._node;}bool operator==(const Self& it){return _node == it._node;}};

在上述代码中：定义了一个迭代器结构ListIterator，用于遍历双向链表。迭代器结构ListIterator包含以下成员变量和成员函数：
成员变量： _node：指向当前迭代器所指向的节点的指针。

成员函数如下：
        1. 构造函数：接受一个参数node，用于初始化迭代器的节点指针。
        2. 前置递增运算符（++it）：将迭代器指向下一个节点，并返回自身的引用。
        3. 前置递减运算符（--it）：将迭代器指向上一个节点，并返回自身的引用。
        4. 后置递增运算符（it++）：将迭代器指向下一个节点，并返回之前的迭代器的副本。
        5. 后置递减运算符（it--）：将迭代器指向上一个节点，并返回之前的迭代器的副本。
        6. 解引用运算符（*）：返回迭代器指向节点的数据的引用。
        7. 成员访问运算符（->）：返回迭代器指向节点数据的指针。
        8. 不等于运算符（!=）：判断当前迭代器是否与另一个迭代器不相等。
        9. 等于运算符（==）：判断当前迭代器是否与另一个迭代器相等。

迭代器结构ListIterator还使用了两个类型别名：
        1. Node：表示节点类型ListNode<T>。
        2. Self：表示迭代器自身类型ListIterator<T, Ref, Ptr>。

3. 迭代器和构造函数

请看示例代码：

	template<class T>class list{typedef ListNode<T> Node;public:// 不符合迭代器的行为，无法遍历//typedef Node* iterator;//typedef ListIterator<T> iterator;//typedef ListConstIterator<T> const_iterator;typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T, const T&, const T*> const_iterator;iterator begin(){//iterator it(_head->_next);//return it;return iterator(_head->_next);}const_iterator begin() const{return const_iterator(_head->_next);}iterator end(){return iterator(_head);}const_iterator end() const{return const_iterator(_head);}list(){_head = new Node();_head->_next = _head;_head->_prev = _head;}

该部分定义了一个双向链表类list。

list类包含以下成员变量和成员函数：
        1. typedef Node：类型别名，表示节点类型ListNode<T>。
        2. typedef iterator：类型别名，表示迭代器类型ListIterator<T, T&, T*>。
        3. typedef const_iterator：类型别名，表示常量迭代器类型ListIterator<T, const T&, const T*>。

成员函数如下：
        1. begin()：返回头节点的下一个节点的迭代器，用于遍历链表。
        2. begin() const：返回头节点的下一个节点的常量迭代器，用于遍历常量链表。
        3. end()：返回头节点的迭代器，用于判断迭代结束。
        4. end() const：返回头节点的常量迭代器，用于判断常量迭代结束。
        5. 构造函数：初始化头节点，将头节点的_next和_prev指向自身。

注意：由于ListIterator的设计不符合迭代器的行为，无法进行迭代，所以在list类中注释掉了typedef iterator和typedef const_iterator的定义。

3. push_back、pop_back、push_front和pop_front

请看示例代码：

void push_back(const T& x)
{/*Node* newnode = new Node(x);Node* tail = _head->_prev;tail->_next = newnode;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;*/insert(end(), x);
}void pop_back()
{erase(--end());
}void push_front(const T& x)
{insert(begin(), x);
}void pop_front()
{erase(begin());
}

这部分代码实现了list类的push_back、pop_back、push_front和pop_front成员函数。

        1. push_back：在链表末尾添加一个节点。首先创建一个新的节点newnode，然后获取链表末尾的节点tail，将tail的_next指向newnode，newnode的_prev指向tail，newnode的_next指向头节点_head，头节点的_prev指向newnode。最后调用insert函数，在末尾迭代器的位置插入新节点。
        2. pop_back：删除链表末尾的节点。首先获取链表末尾节点的前一个节点，然后调用erase函数，将末尾迭代器的前一个位置的节点删除。
        3. push_front：在链表开头添加一个节点。调用insert函数，在开头迭代器的位置插入新节点。
        4. pop_front：删除链表开头的节点。调用erase函数，将开头迭代器的位置的节点删除。

4. insert和erase

请看示例代码：

		// 没有iterator失效iterator insert(iterator pos, const T& x){Node* cur = pos._node;Node* newnode = new Node(x);Node* prev = cur->_prev;// prev  newnode  curprev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;return iterator(newnode);}// erase 后 pos失效了，pos指向节点被释放了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;delete cur;return iterator(next);}

这部分代码实现了list类的insert和erase成员函数。

        1. insert：在指定位置前插入一个节点。首先获取迭代器pos所指向的节点cur，创建一个新的节点newnode，然后获取pos的前一个节点prev。将prev的_next指向newnode，newnode的_prev指向prev，newnode的_next指向cur，cur的_prev指向newnode。最后返回一个指向新节点的迭代器。
        2. erase：删除指定位置的节点。首先断言pos不等于end()，即pos不是指向末尾的迭代器。然后获取迭代器pos所指向的节点cur，分别获取cur的前一个节点prev和后一个节点next。将prev的_next指向next，next的_prev指向prev。删除cur节点，并释放内存。最后返回一个指向删除节点后的节点的迭代器。

        需要注意的是，在使用erase函数删除节点时，要确保操作前的迭代器pos不会失效，否则会导致未定义行为。

        到此我们只是简单的模拟实现了一下STL中list的相关接口~,后续我们会一一展开学习的,希望这篇博客能给您带来一些启发和思考!那我们下次再一起探险喽,欢迎在评论区进行讨论~~~