STL中的list的介绍及模拟实现（C++）

list介绍list即数据结构中的链表STL中实现的是带头双向链表它的物理地址不连续。相比于vector由于其物理地址不连续的特点它的模拟实现较为复杂。咱们还是先介绍认识一下再尝试模拟实现构造函数list()默认构造list (const list x)拷贝构造list (InputIterator first, InputIterator last)通过任意容器的迭代器初始化list (size_type n, const value_type val value_type())初始化为n个value值迭代器的使用beginend分别返回指向第一个数据的迭代器和指向最后一个数据的下一个位置的迭代器rbeginrend分别返回指向最后一个数据的迭代器和指向第一个数据的前一个位置的迭代器empty判断是否为空size返回有效节点个数数据访问front返回第一个节点数据的引用back返回最后一个节点数据的引用增删查改push_front在首元素前插入数据pop_front删除首元素push_back尾插pop_back尾删insert指定位置插入数据erase指定位置删除数据swap交换两个listclear清空listlist模拟实现首先我们要构建框架因为是带头双向链表我们List类中成员只需包含哨兵位即链表的头然后即可跟随链表结点中的next和prev遍历链表。按照C语言版的数据结构中的思路List类中成员为头的地址指向下一个结点的next指针以及指向上一个结点的prev指针。STL则是将链表结点封装成了一个类我命名为List_node这样List 不用关心节点内部怎么存数据只操作节点指针新增 / 删除节点只需要创建 / 销毁List_node对象因此如下图所示我们的List类只有一个成员_head,其类型为List_node*即Node*此外List_node是struct类因为无论其成员函数还是成员变量均可默认为public由于list物理结构的特殊性迭代器的实现不能跟vector等的那么简单因为其前置或后置可能找到的不是当前结点的下一个结点由此我们要想办法结合前面的语法知识可以想到重载以使他走到下一个结点利用当前结点的_next少实现了一个函数我们如此费力地实现了迭代器我们可以不实现吗答案是利大于弊1、封装通用的相似的遍历容器的方式并且封装屏蔽容器结构的差异和底层实现细节2、通用/复用实现算法时用迭代器函数模板方式实现跟底层容器结构解耦接下来就是const_iterator无论是typedef还是函数重载都无法实现因此我们可以考虑再封装一个const_List_iterator类如下少实现了一个函数有上面的铺垫后我们在学习一下迭代器地两个模板类融合为一个类但能实现两个类的功能为了List代码的可读性做出如下处理构造函数empty_init函数给list创建哨兵位因为接下来的函数也要使用封装成了函数拷贝构造利用初始化列表构造listswap函数赋值运算符重载析构函数clear函数pop_back函数push_front函数pop_front函数有关迭代器函数利用匿名对象提高效率insert函数push_back函数这里实现较为复杂是因为push_back函数的设计在insert之前可以通过insert函数设计push_back函数代码十分简洁erase函数size函数如果list类中成员变量不含有效数据个数_size此处size函数实现较为复杂我们在list类中添加一个_size,size函数实现起来就简单多了