广州专业做网站,广东智慧团建系统登录入口,云南网站建设公司,四川建设厅网站复查中一.list介绍 list底层是一个双向带头循环链表#xff0c;这个我们以前用C语言模拟实现过#xff0c;-双向带头循环链表 下面是list的文档介绍#xff1a; list文档介绍 我们会根据 list 的文档来模拟实现 list 的增删查改及其它接口。 二.list模拟实现思路 既然是用C模拟…一.list介绍 list底层是一个双向带头循环链表这个我们以前用C语言模拟实现过-双向带头循环链表 下面是list的文档介绍 list文档介绍 我们会根据 list 的文档来模拟实现 list 的增删查改及其它接口。 二.list模拟实现思路 既然是用C模拟实现的那么一定要封装在类里。 为了适合各种类型的数据会使用模板。 节点 Node 了解双向循环带头链表的都知道我们需要一个节点 Node之前用C语言实现的时候我们写了一个叫做 BuynewNode 的函数来获取节点而在C里我们用类封装一个注意这个用 struct 封装比较好因为 struct 默认是公有的这样方便我们访问所以可以写一个类 struct list_node 迭代器 iterator 我们知道C提供了一种统一的方式来访问容器这就是迭代器string 和 vector 的迭代器模拟实现很简单因为 string 和 vector 底层是用数组实现的数组是一段连续的物理空间支持随机访问所以它是天然的迭代器 但是链表不一样它不是一段连续的物理空间不支持随机访问所以想让 list 的迭代器在表面上和 stringvector 的迭代器用起来没有区别我们在底层上就需要用类封装迭代器然后再迭代器类的内部重载 -- * - ! 这些迭代器会用到的运算符 所以创建一个迭代器类 struct list_iterator const 迭代器 const_iterator 实现的普通的迭代器还有 const 迭代器const 迭代器的意思是让指针指向的内容不变而指针本身可以改变例如指针指针-- 这种操作所以 const 迭代器与普通迭代器的不同只有 重载 * 运算符的返回值不同它是 const T T是模板参数重写一个const 迭代器类又显得太冗余代码的可读性就降低了 前面在学习模板时我们知道不同的模板参数编译器会生成不同的函数所以我们选择加一个模板参数 Ref 。这样只要在显示实例化模板参数时 普通迭代器就传 T const 迭代器就传 const T - 运算符重载
看下面这段代码
using namespace std;struct A
{A(int a1,int a2):_a1(a1),_a2(a2){}int _a1;int _a2;
};void test_list()
{listA lt; //实例化自定义类型lt.push_back(A(1, 1));lt.push_back(A(2, 2));lt.push_back(A(3, 3));lt.push_back(A(4, 4));listA::iterator it lt.begin();while (it ! lt.end()){cout it-_a1 it-_a2 endl; //像指针一样访问自定义类型里的成员变量it;}
}int main()
{test_list();return 0;
} 有时候实例化的模板参数是自定义类型我们想要像指针一样访问访问自定义类型力的成员变量这样显得更通俗易懂所以就要重载 - 运算符它的返回值是 T* 但是正常来说这里应该是这样访问的 it - - _a1 因为迭代器指向的是 整个自定义类型要想再访问其内部成员应该再使用一次 - 这个-就不是重载的 - 就是普通的 - 但是上面的代码为什么就写了一个 - 这个是C语法把这里特殊化了。 那该怎么在迭代器类里重载 - 运算符呢 和const 迭代器一样只需要再加一个模板参数 Ptr 显示实例化的时候传 T* 就行了。 迭代器类 模拟实现源码 struct list_iterator 以上的都算 list 模拟实现的难点其他的像 重载 什么的对于学过数据结构的小伙伴们是非常简单的就不赘述了没学过的可以看看这篇文章双向带头循环链表 templateclass T,class Ref,class Ptr //三个模板参数struct list_iterator //封装迭代器{typedef list_nodeT Node; //重命名节点typedef list_iteratorT, Ref, Ptr self; //重命名迭代器类型Node* _node;list_iterator(Node*node) //构造函数单参数的构造函数支持隐式类型转换:_node(node){}//重载 * -- ! -Ref operator*() const{return _node-_val;}Ptr operator-() const{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 lt) const{return _node ! lt._node;}bool operator(const self lt) const{return _node lt._node;}};
list 我们在用C语言实现双向带头循环链表时会先初始化链表的头head即让它的 前驱指针prev和后继指针next都指向自己 在C的模拟实现 list 中我们会创建一个类 list 来管理链表的节点并实现增删查改及其它接口所以 list 的构建函数就是初始化 头head节点。 三.源码
list.h 我们可以模拟实现以上接口具体函数的逻辑可以查阅文档实现起来都是很简单的。 namespace nagi //把模拟实现list的类都放在一个命名空间里封装起来
{templateclass Tstruct list_node //创建节点{list_nodeT* _prev;list_nodeT* _next;T _val;list_node(const T val T()) //构造函数初始化节点:_prev(nullptr),_next(nullptr),_val(val){}};templateclass T,class Ref,class Ptr //三个模板参数struct list_iterator //封装迭代器{typedef list_nodeT Node;typedef list_iteratorT, Ref, Ptr self;Node* _node;list_iterator(Node*node) //构造函数单参数的构造函数支持隐式类型转换:_node(node){}//重载 * -- ! -Ref operator*() const{return _node-_val;}Ptr operator-() const{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 lt) const{return _node ! lt._node;}bool operator(const self lt) const{return _node lt._node;}};templateclass Tclass list{typedef list_nodeT Node;public:typedef list_iteratorT, T, T* iterator; //重命名普通迭代器typedef list_iteratorT, const T, const T* const_iterator; //重命名const迭代器void empty_init() //因为构造函数和拷贝构造都会初始化头节点所以就写成一个函数了{_head new Node;_head-_prev _head;_head-_next _head;_sz 0;}list() //构造函数{empty_init();}//普通迭代器iterator begin(){return _head-_next;}iterator end(){return _head;}//const迭代器const_iterator begin() const{return _head-_next;}const_iterator end() const{return _head;}iterator insert(iterator pos, const T x) //在pos之前插入{Node* newnode new Node(x);Node* cur pos._node;Node* prev cur-_prev;prev-_next newnode;newnode-_prev prev;newnode-_next cur;cur-_prev newnode;_sz;return newnode;}iterator erase(iterator pos) //删除pos位置注意删除的时候不能把头节点也删了所以要做pos检查{assert(pos ! end());Node* cur pos._node;Node* prev cur-_prev;Node* next cur-_next;prev-_next next;next-_prev prev;delete cur;_sz--;return next; //库里规定返回删除节点的下一个节点}void push_back(const T x) //尾插{insert(end(), x);}void push_front(const T x) //头插{insert(begin(), x);}void pop_back() //尾删{erase(--end());}void pop_front() //头删{erase(begin());}void clear() //清楚除了头节点以外的所有节点{iterator it begin();while (it ! end()){iterase(it);}_sz 0;}~list() //析构函数{clear();delete _head;_head nullptr;}list(const listT lt) //拷贝构造{empty_init();for (auto e : lt){push_back(e);}}void swap(listT lt){std::swap(_head, lt._head);std::swap(_sz, lt._sz);}listT operator(listT lt) //赋值重载{swap(lt);return *this;}private:Node* _head; //头节点size_t _sz; //记录链表的长度};} 本篇文章到此就结束了 若有错误或是建议的话欢迎小伙伴们指出️ 希望小伙伴们能支持支持博主啊你们的支持对我很重要哦 谢谢你的阅读。
