国外建站企业,wordpress打教程,哈尔滨网站制作推广,东莞推广号前言#xff1a;
有了前面的string和vector两个模板的基础#xff0c;我们接下来就来模拟实现一下list链表模板#xff0c;我还是要强调的一点是#xff0c;我们模拟实现模板的目的是熟练的去使用以及去学习一些对于我们本身学习C有用的知识和用法#xff0c;而不是单纯的…前言
有了前面的string和vector两个模板的基础我们接下来就来模拟实现一下list链表模板我还是要强调的一点是我们模拟实现模板的目的是熟练的去使用以及去学习一些对于我们本身学习C有用的知识和用法而不是单纯的去模拟实现。希望大家在学习之前先搞清楚目的再去行动切忌盲目努力。
list的大致介绍
在STL模板中list模板实现的是一个双向带头循环的链表。 1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器并且该容器可以前后双向迭代。 2. list的底层是双向链表结构双向链表中每个元素存储在互不相关的独立节点中在节点中通过指针指向其前一个元素和后一个元素。 3. list与forward_list非常相似最主要的不同在于forward_list是单链表只能朝前迭代已让其更简单高效。 4. 与其他的序列式容器相比(arrayvectordeque)list通常在任意位置进行插入、移除元素的执行效率更好。 5. 与其他序列式容器相比list和forward_list最大的缺陷是不支持任意位置的随机访问比如要访问list的第6个元素必须从已知的位置(比如头部或者尾部)迭代到该位置在这段位置上迭代需要线性的时间开销list还需要一些额外的空间以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素) 所以在这里我想说一下对于想要频繁支持任意位置增删的数据来说使用list更为划算但list遍历却很麻烦但vector对于增删很麻烦需要全部串动一遍数据不过对于任意位置的访问却很简单这就是两者在不同情况下的使用特点我们应该按照不同的场景去灵活使用。 可以用下面的这张图来理解 有了前面的双向带头循环链表模拟实现的基础现在让我们正式开始模拟实现吧。
模拟实现list:
1.节点 链表
节点
首先对于链表来说每一个节点都应该是一个独立的结构体我在这里将其设为结构体其目的就是让其数据都是开放的在C中默认struct类型是public权限的然后就是常规的节点结构体的书写方法如下
templateclass T
struct list_node
{T _data;list_nodeT* _next;list_nodeT* _prev;list_node(const T xT())//注意这里不要给赋值CSTL模板也是支持对内置类型进行拷贝构造的而这里的数据不一定是内置类型一旦是自定义类型就得调用拷贝构造了所以我们这里使用匿名构造:_data(x),,_next(nullptr),_prev(nullptr){}
};处于为了让我们的每一个节点可存储的数据是任意类型的我们使用模板来定义类同时我们写出来我们这个节点类的构造函数其原理很简单但是我们要注意我们的缺省参数的给法在模板使用之后我们的内置类型也开始能支持构造函数的同时我们的节点的数据也有可能是自定义类型所以我们在这里给缺省值直接给其匿名构造的缺省值这样同时满足了内置类型和自定义类型双重数据类型可以通过拷贝构造这个很关键我在vector那里讲过在这里我再提及一次。然后就是很常规的把指针先指向空和我们的数据给过去即可。
链表
首先由于我们要实现的是一个双向带头循环的链表那么自然我们只需要记录我们的头节点即可通过头节点我们可以去访问任意的数据通过指针的迭代即可。所以我们的链表类的成员只要包含一个头节点的指针以及一个记录数据个数的size即可如下
private:Node* _head;//类的成员只有一个哨兵位节点作为头节点size_t _size;//利用这个变量实时统计就省去了从头遍历一遍链表的时间我们同样需要对头节点进行初始化我在这里这样实现
void empty_init()//空初始化,创建一个哨兵节点出来
{_head new Node;_head-_next _head;_head-_prev _head;
}
list()//构造函数
{empty_init();_size 0;
}有了对头节点的初始化我们同时直接把链表类的构造函数写出来即初始化头节点的同时再初始化size即可。 有了这两步我们的链表的大体模型就出来了创造节点类和链表类链接。
2.迭代器
首先让我们考虑一下迭代器的本质我们都知道迭代器的本质是对指针进行操控解引用迭代加加判断是否到结尾。通过封装一个指针我们是可以做到这些的例如string和vector因为首先他们都是以数组为基本的容器去处理的并且他们很多都是单一的数据类型直接解引用就能得到但是节点不同首先节点内部就存在多个成员变量也就是说对于自定义类型的解引用是没有默认的我们必须要自己去写运算符重载才可以。再说加加和减减的问题。我们为什么可以对vector和string加加和减减呢这是因为它们的底层都是数组其空间地址是连续的指针可以通过加加连续的迭代但是对于链表来说每一个节点都是一个独立的个体他们的空间位置是不连续的你指针的加加和减减毫无意义包括判断结尾也是你没有默认的判断方式你可以用下面这张图理解我的意思 那怎样解决这个问题呢由此我们就封装一个类来模拟迭代器通过运算符重载去解决问题这个便是我们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){}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;}Ref operator*()//迭代器的解引用{return _node-_data;}Ptr operator-()//箭头解引用针对数据_data为自定义类型的时候方便我们去访问数据{return _node-_data;}bool operator!(const self s){return _node ! s._node;}bool operator(const self s){return _node s-_node;}
};在这里我同样使用一个struct来封装类这样方便我们后续的数据访问不会受到权限的限制我们的成员只有一个那便是我们的节点的指针Node* node我们依旧是去模拟指针的作用 1.首先是构造函数对于迭代器来说他没有缺省值的可能性也就是说只要使用了迭代器必然要为其赋一个初值。然后就是常规的构造过程我在这类不多赘述了。 2.下一个便是前置加加和后置加加的问题结合前面学过的知识为了区分他们两个我们要在后置带上一个int以示区分在这里注意前置和后置的返回值问题前置由于直接操作指针故我们返回的是之前存在的node故我们引用返回而对于后置来说我们返回的是当前的指针但实际上我们的node已经指向下一个了这就需要我们再创建一个变量来存储原先的位置所以我们的返回值是传值返回这个细节要注意别弄错了。 3.对于解引用的问题同样由于我们的data本身就是存在的所以我们依旧使用引用返回由于node本身是结构体的指针故我们要使用箭头去访问而不是.。 4.对于箭头的返回我们在这里返回的是我们data的地址而不是data本身因为我们的data也有可能是一个自定义类型的数据这导致我们可能还需要一层访问去确定访问我们data数据里的哪一个数值。 在这里有一个很奇怪的地方如果我们的data真的是自定义类型如下
struct AA
{AA(int a10,int a20)//自定义类型的构造函数:_a1(a1),_a2(a2){}int _a1;int _a2;
};
void test3()
{listAA a1;listAA::iterator it1 a1.begin();while (it1 ! a1.end()){cout it1-_a1 it1-_a2 endl;//在这里它隐藏了一个箭头因为我们哪怕是访问it1里面的operator的data后这里的data也是AA类型的然后才能去访问AA里面的数据由于我们取地址所以我们访问也是-去访问这是一个很奇怪的点希望特殊去记住,这里本来是it1.operator-()-_a1但是在这里直接省略了一个箭头it1;}你会发现一个问题是我们只需要一个箭头就能访问到a1或者a2但实际上我们的第一个箭头应该是先访问我们的data的地址然后通过data再去访问我们里面的具体元素也就是说在这里它省略了一个箭头但是这样也可以访问我认为其本质原因在于用两个箭头对于我们来说不是很好理解所以编译器在这里优化了一下省略了其中的一个箭头变得让我们更好理解了但我们自身不能忽略实际上它应该是it1.operator-()-_a1. 5.对于判断相等和不相等的问题很简单我们直接利用指针是否相等即可。 这样通过运算符重载和封装我们变得到了我们的迭代器类但是此时我们还有一个问题需要解决即对于const类型的数据访问我们要特殊处理这时候就有人提出了一个问题这不是很简单么直接在我们的iterator迭代器上加一个const不就解决问题了么 这是个很严重的误解如果我们对iterator前面加上const在这里我们甚至没法对指针本身进行修改了因为它const限制的是我们类里面的数据而我们是需要类里的node的变化去访问数据的所以显然直接加const是不行的我们可以再去定义一个新的类型const_iterator让它作为我们的const迭代器即可但是重新写一个未免太麻烦了能不能用模板的知识来简化代码呢 这是完全可以的让我们看一看我们迭代器代码的前几行
templateclass T,class Ref,class Ptr
struct __list_iterator
{typedef list_nodeT Node;typedef __list_iteratorT,Ref,Ptr self;你会发现我同时定义了三个模板变量那这是为什么呢 让我们想一想我们模拟指针主要模拟的是哪些东西解引用指针操作数据本身他们实际上反映在我们的返回值上也就是T T T*这三个方面其他的对于const迭代器和非const迭代器来说都是相同的因此我们定义三个模板变量让编译器自己去做选择你可以看到我迭代器的返回值直接就是Ref Ptr然后我下面的list去typedef的时候就直接是
templateclass T
class list
{typedef list_nodeT Node;
public:typedef __list_iteratorT,T,T* iterator;typedef __list_iteratorT,const T,const T* const_iterator;这样编译器根据你的名字为其自动匹配迭代器是const还是非const从而在返回值部分返回对应的模板实例化的返回类型从而让我们实现了一份代码就可以实现双类型迭代器的作用这个很关键是list的核心部分我的建议是反复研究琢磨透为止。 封装了我们的迭代器iterator 和const_iterator后我们接下来的函数功能就很简单了我下面几乎都上代码做简单的讲解
3.增删
1.任意插入
iterator insert(iterator pos,const T x)//任意插,在pos位置之前去插入一个值
{Node* cur pos._node;Node* newnode new Node(x);Node* prev cur-_prev;prev-_next newnode;newnode-_prev prev;newnode-_next cur;cur-_prev newnode;_size;return newnode;
}2.任意删除
iterator erase(iterator pos)//任意删,这里会涉及到迭代器失效的问题pos对应的空间被释放后pos的指向就无效了故我们在这里返回它的下一个位置以防止迭代器失效
{Node* cur pos._node;Node* prev cur-_prev;Node* next cur-_next;delete cur;prev-_next next;next-_prev prev;_size--;return next;
}4.链表节点个数
size_t size()//链表的节点个数
{return _size;
}这里便是我为何要创建一个size成员的原因因为链表的遍历统计个数很麻烦所以我们实时统计直接就省去了遍历的过程节省运算的时间。
5.头尾迭代器位置返回
const_iterator begin()const
{return _head-_next;
}const_iterator end()const
{return _head;
}iterator begin()//构成重载自动匹配
{return _head-_next;
}iterator end()
{return _head;
}你会看到这里有了我们的模板我们的一套迭代器就可以像以前那样去使用了。 在这里我要说我对迭代器的理解 迭代器完美体现了封装倘若不模拟我们之只需要一套方法使用但是模拟是完全不同的封装屏蔽了底层实现和封装细节提供统一的增删查改的遍历方式你会发现对于任意的数据类型他们的迭代器的底层是天差地别的但是他们使用起来确实方法相同的这便是迭代器最为巧妙的地方。
6.拷贝构造 赋值运算符重载
拷贝构造
我们的拷贝构造在这里由于浅拷贝的原因我们和我们的vector一样同样使用依次遍历尾插到结尾的方式如下
list(const listT it)//拷贝构造
{empty_init();for (auto ch : it)//遍历it一个一个插入到我们要构造的list中{push_back(ch);}
}赋值运算符重载
利用现代写法直接交换头节点即可
void swap(listT it)
{std::swap(_head, it._head);//注意我们的交换在这里要用std自带的交换在这里直接交换头指针即可其他的根本不用交换成员里本身也没有std::swap(_size, it._size);
}
listT operator(listT it)//赋值运算符重载现代写法,即直接拷贝构造交换即可
{swap(it);return *this;
}7.清除数据和析构函数
清除数据
注意在这里要注意的问题是我们的清除数据不是将整个链表销毁而是清楚数据所以我们要保留我们的头节点头节点是在析构函数的时候才会被消除的这是清除数据和析构函数的不同之处我们要想清楚。
void clear()//清除数据注意清理数据不是完全销毁链表所以我们不销毁头节点
{iterator it begin();while (it ! end()){iterase(it);//这里不用加加it自动返回下一个节点,我们直接用it接收即可}
}在这里我们采用一个一个删除的方式进行注意我们的erase是会返回下一个位置的值的故我们的it要接收否则会有迭代器失效的问题。
析构函数
本质上就是清除数据销毁头节点 ~list()//析构函数{clear();delete _head;_head nullptr;_size 0;}以上便是我们的list最关键的一些功能的模拟实现其余的功能有了这些基础实现起来是很简单的在这里我就不多说了。
总结
对于list来说封装一个迭代器这个是很关键的我认为这是我们对类和对象的进一步理解才能完全掌握的知识所以我的建议是我们要反复思考和模拟实现这个迭代器或者你可以上网去找一找我们STL–list库的底层其琢磨为何要这样去实现库这将有助于我们理解迭代器同时帮助我们去更好的使用list模板库。
