当前位置：首页 > news >正文

list底层原理

news 来源：原创 2025/7/20 3:42:31

一.结构体的构建

这个用结构体更好，因为我们需要不断的访问节点，类中的成员函数一般都是私有的，需要还用友元函数什么的。

这个是我们来实现的类，我们实现的是双向带头循环链表，这个是实用性最高的一个链表的形式。

这个_head就是一个头的作用，没有实际意义。

二.构造函数

这个就是我们的构造函数了，这个就是给头申请一块空间，让next和prev都指向头节点，这样就不会出现空指针的问题了，更加的方便。

三.push_back

这个是我们的插入函数，大家可以结合下面的图理解着看一下。

大家可以结合着上面的代码自己画一下图就很好理解了，这个就是创建一个新节点，然后先找到原来链表的最后一个节点也就是_head->prev，然后再让链表的最后一个元素指向新的节点，再让新的节点的next指向_head，再让新的节点的prev指向指向原链表的最后一个节点，最后让_head的prev指向新节点即可。

四.迭代器

下面来实现一下迭代器。

我们会遇到一些问题，我们难道也要像实现vector的迭代器一样，实现一个指针吗？

typedef list_node<T>* iterator;//这样实现会面临很多问题，我们的解引用是一个结构体而不是一个值，况且空间不连续，我们的++操作也没法完成，那我们该怎么办呢？

我们可以封装一个结构体来完成。

这就是我们迭代器的所需的一个结构体，就是通过node来接收我们的list_node<T>的结构体，通过构造初始化，就是传入我们需要的节点，接下来我们来完成迭代器的一些基本操作吧。

4.1 operator*（）

通过赋值运算符的重载直接返回这个节点的值就可以了。

4.2 operator++（）

这个就是我们的++操作，直接让我们的node=node->_next即可完成，也是很简单的。

4.3 operator！=（）

这个就是两个list_iterator<T>对象进行比较的，通过比较它们的node是否相等即可。

4.4 operator==（）

这个就是把上面的代码的！=改成等于了。

4.5 begin（）和end（）

这就是我们完成的begin和end函数，返回了iterator对象。

接下来我们来测试一下。

我们发现都是符合我们的预期的。

五.const的迭代器

我们都知道迭代器一般都有两种一种是普通版本的，一种则是const版本的。

const版本的实现起来也是很简单的。

这就是我们的const版本的迭代器，也是很简单的，只需要改一下返回值什么的就行了。

这是它的begin和end方法。

为什么报错了呢?

因为l1不是const类型的，它会优先匹配自己的迭代器，而不是const类型的迭代器，两个不同的类型都是优先匹配到自己的类型的begin和end方法。

这个就是it是const_iterator类型的，但是l1.end()是iterator类型的，类型不匹配。

我们发现出现了问题，无法使用*，因为我们的A类中没有重载。

如图所示就得到了解决，但是又发现了几个常犯的错误，那为什么我这里的l1调用不到const类型的begin和end函数呢?实际上，非 const 对象 l1 是可以调用 const 版本的 begin 和 end 函数的。不过，当非 const 对象调用成员函数时，编译器会优先选择非 const 版本的函数。

为什么我们的l2调用不到其他的函数呢？当你在qrh::list<A<int>>前面加上const后，该对象就成为了常量对象。对于常量对象，只能调用其const成员函数。

最后一条语句也可以验证我们上面所说的类型。

我们来看一下结果。