商城网站 搭建湖南网络优化
目录
1.引言
2.C++模拟实现
2.1模拟实现结点
2.2模拟实现list前序
1）构造函数
2）push_back函数
2.3模拟实现迭代器
1）iterator
构造函数和析构函数：
*操作符重载函数：
前置/后置++/--：
==/!=操作符重载函数：
->操作符重载函数：
2）const_iterator
2.4模拟实现list后序
3）insert函数
4）erase函数
5）头插头删尾插尾删函数
6）size函数
7）begin/end函数
8）clear函数
9）析构函数
3.完整list
1.引言
先来说说为什么要模拟实现库里的list？
我认为，模拟实现list有以下几个意义和好处:
1. 学习：通过自己实现一个类似于STL中的list数据结构，可以加深对数据结构和算法的理解。通过亲自编码实现，能更好地理解list的内部工作原理，以及C++语言中与数据结构相关的特性和语法。
2. 练习：编写一个类似于STL中的list可以作为练习和提升编码能力的手段。这有助于加强对C++语言的掌握，并提高面向对象编程的技能。
3. 定制化需求：有时候，STL中提供的list功能不能完全满足特定需求，此时可以通过自己实现一个list类来扩展或定制list的功能，以更好地适应特定的应用场景。
2.C++模拟实现
提前声明，由于list不同类型的函数重载太多太杂，本篇仅仅模拟实现简单的构造，析构，操作符重载，深浅拷贝，增删查改等部分函数的介绍，感谢读者的支持！
建议先创建一个list.hpp头文件，单独创建一个命名空间，防止已经展开了std的命名空间，实现的list与库中list发生冲突。
我们就定义命名空间为drw，接下来完成三个部分的编写：
2.1模拟实现结点
思路：
- 我们先来定义一个结构体__list_node来代表list中存放数据的结点，方便list中函数操作等等访问要求
- 设置一个模板class T来接受各种类型的显式实例化
- 这里不能将__list_node直接命名为Node是为了防止与其他同名结构体冲突
- 设置三个成员变量，分别为:prev next val，用来储存前后结点以及此处结点的数值
- 使用初始化列表完成构造和析构函数
实现：
template<class T>
struct __list_node
{__list_node<T>* prev;__list_node<T>* next;T val;__list_node(const T& t=T()):prev(nullptr),next(nullptr),val(t){}~__list_node(){prev = nullptr;next = nullptr;val = 0;}
};2.2模拟实现list前序
由于list同样需要模板class T来显式实例化，那么我们先设置一个class T模板参数，为什么是先呢？是因为后面还会有补充，请耐心看完~
因为list不希望结点被外界访问，将结点进行了封装，所以可以先将__list_node重命名为Node来方便表示，并且只能在public之外重命名，list类中只有一个私有成员变量，就是Node* _head，这代表头结点。接下来完成成员函数：
1）构造函数
思路：
- 这里我们实现两个构造函数，分别是直接构造和拷贝构造
- 因为这两种构造都要先初始化一个头结点，我们不妨设置一个Emptyinit函数来做这个事情，方便复用
- 在Emptyinit函数中，先new一个Node，对val不做处理，让prev指向自己，next也指向自己
- 直接构造：就是Emptyinit函数的过程，直接复用
- 拷贝构造：参数是const list<T>& l，除了调用Emptyinit之外还要调用push_back对新的list进行尾插拷贝，这里的push_back后续会讲解
实现：
void Emptyinit()
{Node* guard = new Node;guard->prev = guard;guard->next = guard;_head = guard;
}list()
{Emptyinit();
}list(const list<T>& l)
{Emptyinit();for (auto& e : l)//加上&防止自定义类型深拷贝{push_back(e);}
}2）push_back函数
思路：
- 先new一个新结点node，将t传进去初始化node
- 再将新结点的prev设置为_head的prev，next为_head
- 更新_head的prev以及原先_head之前结点的next
实现：
void push_back(const T& t)
{Node* newnode = new Node(t);newnode->prev = _head->prev;_head->prev->next = newnode;newnode->next = _head;_head->prev = newnode;//双向带头循环链表，需要复习！
}
void push_back(const T& t)
{insert(_head, t);
}这里还可以直接调用insert函数，后面介绍！由于后续函数需要迭代器，这里穿插介绍模拟实现迭代器：
2.3模拟实现迭代器
在使用list的时候，我们知道迭代器可以++/--，但是不能+/-，因为list迭代器属于双向迭代器但不属于随机迭代器，但每个结点存储位置是分散开的啊，这怎么实现++/--呢，于是可以定义一个迭代器结构体，将其封装成类，就可以进行这一操作了！
设置模板template<class T>，定义__list_iterator，为了方便表示__list_node，这里也提前重命名一下为Node，设置成员变量为node
1）iterator
构造函数和析构函数：
思路：直接使用初始化列表进行赋值nullptr即可，同样赋值nullptr进行析构，因为node已经有默认构造和析构，就不需要更多的处理
实现：
__list_iterator(Node* _node):node(_node)
{ }~__list_iterator()
{node = nullptr;
}*操作符重载函数：
思路：直接返回node代表的val即可
实现：
T& operator*()
{return node->val;
}前置/后置++/--：
思路：++：前置就让node指向next即可，后置就拷贝tmp，让node指向next返回tmp
--：前置node指向prev，后置拷贝tmp，node指向prev返回tmp
实现：
__list_iterator<T>& operator++()//前置
{node = node->next;return *this;
}__list_iterator<T>& operator++(int)//后置
{__list_iterator<T> tmp(*this);node = node->prev;return tmp;
}__list_iterator<T>& operator--()//前置
{node = node->next;return *this;
}__list_iterator<T>& operator--(int)//后置
{__list_iterator<T> tmp(*this);node = node->prev;return tmp;
}==/!=操作符重载函数：
思路：判断一下是否相等即可
实现：
bool operator!=(const __list_iterator<T>& it){return node != it.node;}bool operator==(const __list_iterator<T>& it){return node == it.node;}->操作符重载函数：
思路：为什么要有这个函数？是因为如果list存储的是含有多个成员变量的结构体，那么想要访问成员变量不应该仅仅有*.还应该提供->
这里直接返回T*类型的&(node->val)即可就不进行实现展示了。
2）const_iterator
思考：const迭代器与iterator相差在哪里呢？无非就是*操作符重载函数多了一些const，其他大致相同，所以我们就不必再去大费周章重新写，这里增加一个模板参数Ref，在显式实例化的时候传T&或者const T&就可以解决这个问题：
那么这仅仅解决了*函数的重载问题，->函数呢？这当然又需要一个模板参数Ptr，传参方法是一样的。为了简化类型，将 __list_iterator<T, Ref,Ptr> 重命名为self
演示整个迭代器：
template<class T,class Ref,class Ptr>//为什么要传Ref是因为两个结构体太累赘，这样可以简化，要传Ptr是为了给->函数的返回类型也进行模板化
struct __list_iterator
{typedef __list_node<T> Node;typedef __list_iterator<T, Ref,Ptr> self;//这里再次重定义一下方便Node* node;__list_iterator(Node* _node):node(_node){ }Ref operator*(){return node->val;}Ptr operator->()//为什么要重载访问成员操作符呢？是因为显式实例化传参也就是vector里面可能保存的是自定义类型而不是内置类型{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){return node != it.node;}bool operator==(const self& it){return node == it.node;}~__list_iterator(){node = nullptr;}
};2.4模拟实现list后序
3）insert函数
思路：
- insert函数就是在迭代器位置为pos的地方插入数据
- 开辟一个新结点newnode，将数据传入初始化，记录一下pos的前一个结点地址prev
- 让prev的next指向newnode，newnode的prev指向prev，newnode的next指向pos，pos的prev指向newnode，返回newnode
实现：
iterator insert(iterator pos, const T& t)
{//无需断言Node* prev = pos.node->prev;Node* newnode = new Node(t);prev->next = newnode;newnode->prev = prev;newnode->next = pos.node;pos.node->prev = newnode;return newnode;
}4）erase函数
思路：
- 判断一下pos是否合法，不能删除头结点
- 记录一下前一个和后一个结点地址，分别为prev和next
- 让prev的next指向next，next的prev指向prev
- 释放掉pos结点，返回next的地址，这是防止迭代器失效的措施
实现：
iterator 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;return next;
}5）头插头删尾插尾删函数
思路：
- 由于实现了insert和erase，这里直接复用就方便多了
实现：
void push_back(const T& t)
{insert(_head, t);
}void pop_back()
{erase(_head->prev);
}void push_front(const T& t)
{insert(_head->next, t);
}void pop_front()
{erase(_head->next);
}6）size函数
思路：
- 要计算链表中的结点个数，但不能算入头结点
- 定义size_t sz，从头结点的下一个开始遍历，到指针指向_head结束
实现：
size_t size()
{size_t sz = 0;iterator it = begin();while (it != end()){sz++;it++;}return sz;
}7）begin/end函数
思路：
- 直接将_head的下一个结点或者_head返回，因为end代表最后一个元素的下一个位置
实现：
iterator begin()
{return _head->next;
}iterator end()
{return _head;
}const_iterator begin()const
{return _head->next;
}const_iterator end()const
{return _head;
}8）clear函数
思路：
- clear函数是将list中的每一个结点进行释放删除，相当于清空链表
- 用循环实现即可，但是要注意迭代器的失效问题！erase之后的迭代器要及时更新
实现：
void clear()
{iterator it = begin();while (it != end()){it=erase(it);//迭代器失效了！！！要注意！！！}
}9）析构函数
思路：
- 调用clear函数之后释放掉头结点就完成了析构
实现：
~list()
{clear();delete _head;_head = nullptr;
}3.完整list
这里给出完整的实现代码：
#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
namespace drw
{template<class T>struct __list_node{__list_node<T>* prev;__list_node<T>* next;T val;__list_node(const T& t=T()):prev(nullptr),next(nullptr),val(t){}~__list_node(){prev = nullptr;next = nullptr;val = 0;}};template<class T,class Ref,class Ptr>//为什么要传Ref是因为两个结构体太累赘，这样可以简化，要传Ptr是为了给->函数的返回类型也进行模板化struct __list_iterator{typedef __list_node<T> Node;typedef __list_iterator<T, Ref,Ptr> self;//这里再次重定义一下方便Node* node;__list_iterator(Node* _node):node(_node){ }Ref operator*(){return node->val;}Ptr operator->()//为什么要重载访问成员操作符呢？是因为显式实例化传参也就是vector里面可能保存的是自定义类型而不是内置类型{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){return node != it.node;}bool operator==(const self& it){return node == it.node;}~__list_iterator(){node = nullptr;}};//这样实现太过于累赘，最好再添加一个模版参数来实现//template<class T>//struct __const_list_iterator//{// typedef __list_node<T> Node;// Node* node;// __const_list_iterator(Node* _node)// :node(_node)// {// }// const T& operator*()const// {// return node->val;// }//__const_list_iterator<T>& operator++()//前置//{// node = node->next;// return *this;//}//__const_list_iterator<T>& operator++(int)//后置//{// __const_list_iterator<T> tmp(*this);// node = node->next;// return tmp;//}// bool operator!=(const __const_list_iterator<T>& it)// {// return node != it.node;// }// bool operator==(const __const_list_iterator<T>& it)// {// return node == it.node;// }// ~__const_list_iterator()// {// node = nullptr;// }//};template<class T>class list{typedef __list_node<T> Node;public:/*typedef __list_iterator<T> iterator;typedef __const_list_iterator<T> const_iterator;*///typedef const __list_iterator<T> const_iterator;//不能这样使用 const迭代器那么迭代器就不能改变了typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;void Emptyinit(){Node* guard = new Node;guard->prev = guard;guard->next = guard;_head = guard;}list(){Emptyinit();}list(const list<T>& l){Emptyinit();for (auto& e : l)//加上&防止自定义类型深拷贝{push_back(e);}}list<T>& operator=(list<T> l){swap(_head, l._head);return *this;}//void push_back(const T& t)//{// Node* newnode = new Node(t);// newnode->prev = _head->prev;// _head->prev->next = newnode;// newnode->next = _head;// _head->prev = newnode;//双向带头循环链表，需要复习！//}void push_back(const T& t){insert(_head, t);}void pop_back(){erase(_head->prev);}void push_front(const T& t){insert(_head->next, t);}void pop_front(){erase(_head->next);}iterator begin(){return _head->next;}iterator end(){return _head;}const_iterator begin()const{return _head->next;}const_iterator end()const{return _head;}iterator insert(iterator pos, const T& t){//无需断言Node* prev = pos.node->prev;Node* newnode = new Node(t);prev->next = newnode;newnode->prev = prev;newnode->next = pos.node;pos.node->prev = newnode;return newnode;}iterator 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;return next;}size_t size(){size_t sz = 0;iterator it = begin();while (it != end()){sz++;it++;}return sz;}void clear(){iterator it = begin();while (it != end()){it=erase(it);//迭代器失效了！！！要注意！！！}}~list(){clear();delete _head;_head = nullptr;}private:Node* _head;};
}