当前位置: 首页 > ds >正文

list模拟实现

大家好,很高兴又和大家见面了!接下来我将模拟实现list

let's go!


前言

list是C++中STL库里面实现的一个双向循环链表

不同于在c语言中的链表实现,c++中的list通过封装面向对象编程,使得代码更加便捷,使用更加方便。


一、list实现接口概略

size、swap、begin、end、insert、

push_back、push_front、

erase、pop_back、pop_front、

构造函数、拷贝构造函数、析构函数

operator=、clear、

二、大体框架

#include <iostream>
#include <assert.h>
namespace zcy
{template<class T>struct list_node{};template<class T>class list{typedef list_node<T> Node;public:list(){}private:Node* _head;size_t _size;};
}

我们通过list_node这个类来维护节点信息,通过list来维护这些节点的增删查改

在list中我们需要维护一个_head指针这个来帮助我们的查找,但是_head里面不去存储值

_size去记录有效节点的个数

我们还要去实现一下我们list_node:

struct list_node
{list_node<T>* _prev;list_node<T>* _next;T _val;list_node(const T& val = T()): _prev(nullptr), _next(nullptr), _val(val){}
};

我们去实现两个指针,一个指向该节点的前方,一个指向该节点的后方

还有一个_val去维护该节点里面的值

其中实现了一个默认构造函数

给了一个缺省值:T()

这个东西我在前面的文章中有提到,我这里又提一下

由于我们不知道T到底是什么类型,我们给初始值怎么给呢?我们就给它的一个匿名对象(调用构造函数)

但是对于内置类型可以吗?

是可以的因为内置类型在c++中被升级成了类,这样就可以去方便我们实现这个了

三、iterator迭代器的实现

对于iterator来讲,我们需要通过它来遍历链表,通过它来访问数据,但是我们的链表中由于数据不是连续的,我们就无法找到一个对应适合的指针去作为我们的迭代器。

我们的迭代器还要实现++ 、--、*之类的操作所以我们就需要通过一个类来实现这个迭代器了

template<class T>
struct __list_iterator
{typedef list_node<T> Node;Node* _node;//维护一个节点__list_iterator(Node* node): _node(node){}};

我们通过这么一个类,在里面对对应节点指针进行操作,然后重载运算符,就可以实现迭代器的功能。

我们在其中要实现这么几个功能:

前置++,后置++,前置--,后置--

*,->

!= 、==

我们再思考一下?对于++,--这些在const类型的迭代器中也是可以进行的,只是将迭代器移动到其他节点而已,但是*和->我们是在const类型的迭代器中是不可以进行修改的,所以我们为了能够让const类型的迭代器可以使用这个类,我们就得加上其他的模版参数

对于普通类型的迭代器,在->中返回的是T*,对于const类型的迭代器,我们返回的是const T* 

对于普通类型的迭代器,在*中返回的是T&,对于const类型的迭代器,我们返回的是const T&

我们只需要再来两个模版参数Ref和Ptr去接收即可:

template<class T, class Ref, class Ptr>
struct __list_iterator
{typedef __list_iterator<T, Ref, Ptr> self;typedef list_node<T> Node;Node* _node;//维护一个节点__list_iterator(Node* node): _node(node){}
}

3.1.operator*、operator->实现

Ref operator*()
{return _node->_val;
}Ptr operator->()
{return &(_node->_val);//如果T是结构体呢?//那么我们就得将对应的T val的地址返回去//便于直接访问其中内容
}

对于第一个*比较好理解,我们直接将对应的值返回去即可。

但是对于第二个->不太好理解,我们为什么要返回对应节点的_val的地址呢?

因为我们对应T是什么类型并不知道,如果T是一个结构体这样的自定义类型,我们就会遇到去访问这个结构体里面的内容而不是单单拿到一个结构体类型。

通过返回的地址我们就可以去->拿取其中内容了

我们使用的时候发现我们难道通过一个->拿到对应的地址,要访问内容我们还有用一个->去访问吗?

那样不就成了->->?

其实并不需要,因为需要可读性,编译器会帮助我们省略一个->

3.2.++、--实现

self& operator++()
{_node = _node->_next;return *this;
}
self operator++(int)
{self tmp = new self(_node);_node = _node->_next;return tmp;
}self& operator--()
{_node = _node->_prev;return *this;
}
self operator--(int)
{self tmp = new self(_node);_node = _node->_prev;return tmp;
}

这里的self我在前面有typedef重命名,本质为:__list_iterator<T, Ref, Ptr>

对于++和--,实现还是比较简单,只需要让对应的指针向后或者向前去走动即可

3.3.!= 、==实现

bool operator!=(const self& t) const
{return _node != t._node;
}
bool operator==(const self& t) const
{return _node == t._node;
}

我们每个节点所对应的地址都是不同的,我们只用比较一下节点的地址即可

实现不难,大家可以好好看看代码,记得在后面加上const,不然会出现错误,因为很可能会出现和const类型的迭代器去比较!

四、list接口实现

4.1.迭代器

template<class T>
class list
{typedef list_node<T> Node;typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;public:list(){}
private:Node* _head;size_t _size;
};

我们重命名类型,形成迭代器iterator,现在iterator就是结构体类型了

4.2.构造函数

void empty_init()
{_head = new Node;_head->_prev = _head;_head->_next = _head;_size = 0;
}
list()
{empty_init();
}

由于后面还会使用empty_init函数,我将它实现在外面

通过创建节点,然后让节点指向自己,形成循环链表,再让_size = 0;就初始化整个链表了

4.3.size函数

size_t size()
{return _size;
}

我们有对应的_size参数去记录,直接返回这个_size即可,实现很简单

4.4.swap函数

swap函数可以交换两个类的信息

void swap(list<T>& t)
{std::swap(t._head, _head);std::swap(t._size, _size);
}

这个的话,也很简单,我们调用一下库里面的swap交换函数,交换一下对应的_head和_size就交换完了两个类的信息。

4.5.begin、end函数

iterator begin()
{return _head->_next;
}
iterator end()
{return _head;//末尾节点的下一个节点
}
const_iterator begin() const
{return _head->_next;
}
const_iterator end() const
{return _head;
}

由于我的_head是一个无效的值,我们_head的下一个位置才是begin有效节点的开始

那么又由于是一个双向循环链表,这里的_head可以理解为最后一个有效节点的下一个位置。

我们就可以让end()去指向_head了。

4.6.insert函数

iterator insert(iterator pos, const T& x)
{//在pos位置插入xNode* tmp = new Node(x);Node* cur = pos._node;//pos是一个结构tmp->_next = cur;tmp->_prev = cur->_prev;cur->_prev->_next = tmp;cur->_prev = tmp;_size++;return tmp;
}

我们的插入函数是在pos指针指向的位置进行插入,插入值为x的元素

首先就需要一个新的节点去放置该元素,所以我们就一来先new Node(x)去创建了这么一个节点

现在就是需要将节点链接起来。

对于新节点的链接大家可以照我的思路来就避免出现错误了!

首先,先处理新节点的前后指针,将新节点链接到当前指针指向节点的前一个位置

然后,再处理原来指针指向节点cur的链接关系,先让cur的前置节点指向新节点,再修改cur的前置节点为新节点。

这样我们就将这几条链接不出错的整好了!

我们插入完后一定要返回插入节点的地址,以免出现迭代器失效。

4.7.push_back、push_front函数

我们有了insert函数后,这两个函数就简单了

void push_back(const T& x)
{insert(end(), x);
}
void push_front(const T& x)
{insert(begin(), x);
}

我们去附用前面的代码即可。

4.8.erase函数

iterator erase(iterator pos)
{assert(pos != end());Node* cur = pos._node;Node* next = cur->_next;Node* prev = cur->_prev;prev->_next = next;next->_prev = prev;delete cur;_size--;return next;
}

对于erase函数首先就得判断一下删除节点的正确与否,避免出现问题

现在就是删除的逻辑了

我们将要删除的节点用cur标记

首先就是需要将cur前后节点先链接起来

cur的前置节点的下一个节点就可以先指向cur的后置节点

cur的后置节点的前一个节点就可以指向cur的前置节点

这样就将cur的前后节点链接起来,后面就是删除cur节点,并--_size

最后需要返回删除节点的下一个节点的地址,避免出现迭代器失效的问题!

4.9.pop_back、pop_front函数

void pop_back()
{erase(--end());
}
void pop_front()
{erase(begin());
}

有了erase函数后,这里就可以直接附用erase

4.10.拷贝构造函数

list(const list<T>& t)
{//拷贝构造函数empty_init();for (auto e : t){push_back(e);}}

拷贝构造函数,我们先将自己给初始化一下,然后通过push_back函数将数据拷贝过来就行。

这里实现也是全部利用了前面的代码

也避免了这里的复杂操作,一举多得

4.11.operator=函数

list<T>& operator=(const list<T> t)
{swap(t);return *this;
}

我们这里还是使用的现代写法,我们通过传值调用,传入的时候就创建出来临时变量t

通过临时变量将原来的数据进行交换,返回自己。

出了函数后,就使得对应的临时变量带着自己的那份数据销毁掉了。!

4.12.clear函数

void clear()
{iterator it = begin();while (it != end()){it = erase(it);}_size = 0;
}

clear清空里面的数据,通过迭代器,挨个进行删除,最后将_size置为0.

这样我们就可以清空数据

4.13.析构函数

~list()
{clear();delete _head;_head = nullptr;
}

析构函数,首先就需要清空数据,我们就可以直接附用clear函数了,最后将_head指针进行析构即可,置空即可。

总结

很高兴大家对我的支持,这部分的list最主要的还是迭代器那里,跟之前的几个容器并不相同,由于其数据结构的不同,我们必须使用类来封装它,大家要仔细看看!

多多点赞 + 收藏 + 关注!谢谢大家

http://www.xdnf.cn/news/17960.html

相关文章:

  • 2025 年电赛 C 题 发挥部分 1:多正方形 / 重叠正方形高精度识别与最小边长测量
  • 36 C++ STL模板库5-string
  • %in%与`==
  • pnpm常用命令;为什么使用pnpm?
  • CV 医学影像分类、分割、目标检测,之【肺结节目标检测】项目拆解
  • 华为6730交换机恢复接口默认配置
  • 疏老师-python训练营-Day45Tensorboard使用介绍
  • elasticsearch冷热数据读写分离!
  • 数学建模-非线性规划模型
  • Linux编程1:进程和线程
  • 目标检测-动手学计算机视觉12
  • 爱情的本质及模拟推演
  • 机器翻译:Hugging Face库详解
  • 模型选择与调优
  • Java 并发新范式:用 Structured Concurrency 优雅收拾多线程烂摊子
  • Linux软件编程:进程和线程
  • 【软考中级网络工程师】知识点之入侵防御系统:筑牢网络安全防线
  • Linux中Samba服务配置与使用指南
  • 计算机毕设大数据选题推荐 基于spark+Hadoop+python的贵州茅台股票数据分析系统【源码+文档+调试】
  • 百川开源大模型Baichuan-M2的医疗能力登顶第一?
  • Flink CDC 实战:实时监听 MySQL Binlog 并同步到 Kafka
  • 《贵州棒球百科》体育赛事排名·棒球1号位
  • 面试题:如何用Flink实时计算QPS
  • 【120页PPT】人工智能与数字化转型的业财融合(附下载方式)
  • 计算机视觉第一课opencv(二)保姆级教
  • 解决SQL Server连接失败:Connection refused: connect
  • H.264、H.265 到 H.266:编码标准演进、RTSP支持与实时视频系统实战
  • 嵌入式学习(day26)frambuffer帧缓冲
  • Vue内置组件全解析:从入门到面试通关
  • 三种DuckDB电子表格插件的union all查询性能对比