yo!这里是STL::list类简单模拟实现

这篇具有很好参考价值的文章主要介绍了yo!这里是STL::list类简单模拟实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

前言

重要接口实现

框架

默认成员函数

迭代器(重点)

1.引言

2.list迭代器类实现 

3.list类中调用实现 

增删查改

后记


前言

        我们知道,stl中的vector对应数据结构中的顺序表,string类对应字符串,而今天要讲的list类对应带头双向链表,并不是对应单链表,带头双向链表的基本操作在数据结构课程中已经学过,所以今天即将要讲的常见接口并不是重点,重点是list的迭代器的实现。

        我们也知道,string、vector的迭代器就是原生指针,如果使用原生指针可以实现list的迭代器吗?答案是不行,因为list的数据并不是一块连续的存储空间,无法像指针那样取访问元素,但是为了保持所有容器迭代器的使用一致,我们如何实现list的迭代器才能像原生指针那样通过++、--去控制,这里就体现出了封装的重要性,快往下看看吧!

yo!这里是STL::list类简单模拟实现,c++,list,职场和发展,开发语言,后端,visual studio

重要接口实现

  • 框架

        通过下方代码可以看出,实现了一个节点类模板存储节点,一个链表类模板存储链表,

①使用类模板是因为存储元素可以自由指定,不是像以前一样通过typedef固定了每个链表的元素类型;

②节点类模板使用struct,而不使用class,是因为struct的默认权限是public,链表类模板可以自由访问其成员变量,而class默认权限是private,当然用class指定public权限也可以,

节点类模板中通过构造函数初始化元素,链表类模板成员是一个节点指针,可以在构造函数中申请一个节点充当头节点。

代码:

template <class T>
struct ListNode
{
	//构造函数用来创节点
	ListNode(const T& x = T())
		:_data(x)
		, _prev(nullptr)
		, _next(nullptr)
	{

	}

	T _data;
	ListNode<T>* _prev;
	ListNode<T>* _next;
};

template <class T>
class List
{
	typedef ListNode<T> Lnode;  //作用:下面写ListNode<T>较麻烦,typedef一下,使用Lnode较方便

public:

    //...

private:
	Lnode* _head;
};
  • 默认成员函数

        因为在所有构造函数前都需要先初始化成员变量(为头节点申请空间并将左右指针置空),所以封装了一个函数empty_init在每个构造函数前直接调用,

        所有默认成员函数的实现与string、vector中的如出一辙,不太理解的可以参考一下之前的文章,不是重点这里不再赘述。

代码:

	//创建并初始化头节点,放于构造函数的最前面
	void empty_init()
	{
		_head = new Lnode();
		_head->_next = _head->_prev = _head;
	}

    //构造函数
	List()
	{
		empty_init();
	}

	//普通拷贝构造函数
	List(const List& L)   //注意:类外必须是List<类型名>,类里可以是List,但建议List<T>
	{
		empty_init();
		auto it = L.begin();
		while (it != L.end())
		{
			push_back(*it);
			it++;
		}
	}

	void swap(List<T>& L)
	{
		std::swap(_head, L._head);
	}

	//传迭代器区间构造函数
	template <class InputIterator>  
	List(InputIterator first, InputIterator last)
	{
		empty_init();

		while (first != last)
		{
			push_back(*first);
			++first;
		}
	}

    //拷贝构造函数
	//现代写法
	List(const List<T>& L)
	{
		empty_init();
		List<T> tmp(L.begin(), L.end());
		swap(tmp);
	}

    //赋值运算符重载
	//现代写法
	List<T>& operator=(const List<T>& L)
	{
		List<T> tmp(L.begin(), L.end());
		swap(tmp);
		return *this;
	}
	//更狠的现代写法
	List<T>& operator=(List<T> L)   //直接传一个拷贝过来,相当于上面的tmp,函数结束自动释放
	{
		swap(L);
		return *this;
	}

    //清除除了头节点之外所有的节点
   	void clear()
	{
		auto it = begin();
		while (it != end())
		{
			it = erase(it);
		}
	}

    //析构函数
	~List()
	{
		clear();
		_head->_next = _head->_prev = nullptr;
		delete _head;
		_head = nullptr;
	}
  • 迭代器(重点)

1.引言

        还记得vector、string的迭代器实现吗?typedef T* iterator;   typedef const T* const_iterator;   ,只是原生指针对不对,然后typedef一下,就可以使用了,因为指针可以在一块连续的地址空间++或--访问元素,但是链表中的节点指针++、--访问元素可以吗,答案是不可以,但为了保持迭代器使用一致,就应该遇到链表的迭代器使用++、--也可以达到一样的效果,因此就想到了操作符重载,将++、--、*  重载成我们希望达到的效果,而实现操作符重载就必须将其封装成一个类。

        从引言中就可以看出list与之前学过的容器迭代器实现的不同之处,list迭代器是通过封装成类实现,但迭代器有两种(暂时先不提反向迭代器),一种普通迭代器,一种const迭代器,两种迭代器的实现应该大致内容都一样,小部分不一样(比如,const迭代器的解引用应该返回const不可类型的变量),那我们应该先写好普通迭代器的实现,再复制粘贴成const迭代器然后修修改改吗?漏!大漏特漏!接触过模板这个概念之后,应该可以想到这里用到模板。

2.list迭代器类实现 

1)框架 

        见下方代码, 实现list的迭代器这个__list_iterator类模板,参数列表中的T、Ref、Ptr分别是数据类型、此类型的引用、此类型的指针(比如,T是int,Ref就是int&,Ptr就是int*)(为什么需要指针参数在操作符->重载处有说明),填入的参数不同就是不同的类,这里list的迭代器需要两个类,一个普通迭代器的类,一个const迭代器的类,在list类实现中去定义即可。

        针对list迭代器类模板的实现,成员变量是节点的指针,而构造函数则是传入一个节点指针可初始化一个list迭代器,不需要自己提供析构函数。

代码:

template <class T, class Ref, class Ptr>
struct __list_iterator
{
    //注意:这两个typedef只是因为ListNode<T>、__list_iterator<T, Ref, Ptr>很麻烦写,所以简化一下,也方便理解
	typedef ListNode<T> Lnode;
	typedef __list_iterator<T, Ref, Ptr> iterator;

    //构造函数
    __list_iterator(Lnode* p)
		:_node(p)
	{

	}

    //...

	Lnode* _node;   //链表中的迭代器表示节点的指针
};

2) 关系运算符重载

        判断两个迭代器相不相等即判断作为成员变量的结点指针是不是同一个指针变量,很容易理解,加上const是无论普通list对象还是const list对象都可以调用。

代码:

    bool operator==(const iterator& it) const
	{
		return _node == it._node;
	}
	bool operator!=(const iterator& it) const
	{
		return !(*this == it);
	}

 3)运算符++、--重载

        针对list类,迭代器的++就是访问下一个节点的迭代器,--是访问上一个节点的迭代器,再注意好前置与后置的实现即可,不是很难。

代码:

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

4)操作符*重载

        list类中的迭代器解引用就是访问此节点的数据,并且返回引用类型,即可操作其中的值,普通迭代器的Ref是普通引用类型,即可读可写,const迭代器的Ref是const引用类型,只可读不可写。

        注意:不需要将此成员函数设置成const类型,就像本作者初学时所疑惑的,如果Ref是const T&,不应该对应const成员函数(Ref operator*() const)吗?其实不然,list类的迭代器使用了类模板,参数不同就是不同的类,直接将两种迭代器分开了,如果是普通迭代器,Ref就会传进来T&,调用解引用重载时返回引用,可读可写,如果是const迭代器,Ref就会传进来const T&,调用解引用重载时返回const引用,只可读不可写。

代码:

	Ref operator*()
	{
		return _node->_data;
	}
	

 5)操作符->重载

        正常情况下,操作符->可以解引用结构体指针再取其成员,那对于底层是节点指针的list迭代器,->就是对迭代器解引用再取其成员,所以针对_data如果是个自定义类型,那么->就可以取其成员,比如,_data是个自定义类型POS,有两个成员,一个x,一个y,那么it->x,it->y表示迭代器取的POS中的x、y,如下图测试,

        仔细观察->操作符重载的实现,it->x应该写成it->->x才是对的,因为it->返回自定义类型指针,再->x返回其成员,这里其实编译器做了处理,省略了一个->,提高了可读性。

        这里的Ptr就是数据类型的指针变量,将其地址返回,与引用形式一样,需要从类模板参数列表输入。

代码:

    Ptr operator->()
	{
		return &(_node->_data);
	}

 测试:

yo!这里是STL::list类简单模拟实现,c++,list,职场和发展,开发语言,后端,visual studio

3.list类中调用实现 

        在实现完__list_iterator这个list类迭代器类模板之后,通过在list类中输入不同的模板参数定义不同的类,这里需要普通迭代器类和const迭代器类,如下代码,begin()是返回首元节点的迭代器,而end()是返回最后一个元素节点的下一个位置迭代器,即头节点迭代器。

 代码:

    typedef __list_iterator<T, T&, T*> iterator;  //普通迭代器类
	typedef __list_iterator<T, const T&, const T*> const_iterator;   //const迭代器类

	iterator begin()
	{
		return iterator(_head->_next);
	}
	iterator end()
	{
		return iterator(_head);
	}
	const_iterator begin() const
	{
		return const_iterator(_head->_next);
	}
	const_iterator end() const
	{
		return const_iterator(_head);
	}
  • 增删查改

        在理解了list的迭代器实现之后,对list的增删改查想必是游刃有余,这里实现一下基本的插入删除操作,结合之前在数据结构中的知识,insert、erase的实现应该可以很快写出,值得注意的是,insert返回新插入节点的迭代器,erase返回所删节点的下一位置的迭代器,而尾插、尾删、头插、头删直接复用即可。

代码:

	iterator insert(iterator pos, const T& x)
	{
		Lnode* newNode = new Lnode(x);
		pos._node->_prev->_next = newNode;
		newNode->_prev = pos._node->_prev;
		newNode->_next = pos._node;
		pos._node->_prev = newNode;

		return iterator(newNode);  //返回插入位置的迭代器
	}
    
    //尾插
	void push_back(const T& x)
	{
		insert(end(), x);
	}

    //头插
	void push_front(const T& x)
	{
		insert(begin(), x);
	}

	iterator erase(iterator pos)
	{
		assert(pos != end());
		Lnode* tmp = pos._node->_next;
		pos._node->_prev->_next = pos._node->_next;
		pos._node->_next->_prev = pos._node->_prev;
		delete pos._node;
		return iterator(tmp);
	}

    //尾删
	void pop_back()
	{
		erase(--end());
	}

    //头删
	void pop_front()
	{
		erase(begin());
	}

后记

        在list类的实现中,默认成员函数、操作符重载以及增删查改已不再是重点,重点是掌握迭代器的实现,因为与string、vector中的迭代器实现不同,也没有那么简单,上面总结的很清楚,不懂的可以私我或者写在评论区,加油,拜拜!文章来源地址https://www.toymoban.com/news/detail-649276.html


到了这里,关于yo!这里是STL::list类简单模拟实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • stl中的list模拟实现

    首先我们要清楚list是一个带头双向循环的链表。 在下面代码中我们用到了 模板 ,并且用的是 struct 没有用 class ,这是因为我们使用struct时相当于 这一个类是公开的 ,当然我们也可以使用class但是得使用友元函数比较麻烦。 我们可以查看stl的源码进行查看,如下: 我们可以

    2024年02月02日
    浏览(43)
  • C++ STL->list模拟实现

    list list文档 list是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代。 list的底层是双向链表结构,双向链表中每个元素存储在互不相关的独立节点中,在节点中通过指针指向 其前一个元素和后一个元素。 list与forward_list非常相似:最主

    2024年02月20日
    浏览(44)
  • C++_STL——list模拟实现

    list作为一个容器组件,有着其重要的价值,其实在底层这是一个 带头双向循环的链表数据结构 ,可以在任意位置进行插入和删除的序列式容器,并且该容器可以前后进行遍历。 那么同样作为序列式容器,list和vector相比又有哪些优缺点呢? 优点 :对于在任意位置进行插入、

    2024年02月16日
    浏览(38)
  • C++STL的list模拟实现

    要实现STL的list, 首先我们还得看一下list的源码。 我们看到这么一个东西,我们知道C++兼容C,可以用struct来创建一个类。但是我们习惯用class。 那什么时候会用struct呢? 这个类所有成员都想开放出去,比如结点的指针,它一般开放出来。所以我们用struct.。 继续看源码比较重

    2024年02月04日
    浏览(43)
  • 【C++】STL---list的模拟实现

    上次模拟实现了一个vector容器,那么我们这次来实现一个list(链表)容器,链表在实际的开发中并不常见。但是也是一种很重要的数据结构,下面给大家介绍一下链表(list) 和 vector(顺序表)的区别。 list 和 vector 一样,是一个存储容器。不同的是vector在内存中是连续存储的,而

    2024年01月22日
    浏览(53)
  • C++ ——STL容器【list】模拟实现

    代码仓库: list模拟实现 list源码 数据结构——双向链表 源码的list是双向带头循环链表,所以我们定义两个节点,一个指向下一个,一个指向前一个 list类包含一个 _head 头节点,然后为了方便查出当前有多少个节点,还能多定义一个 _size 源码的迭代器设置了三个模板参数:

    2024年02月15日
    浏览(46)
  • [ C++ ] STL---list的模拟实现

    目录 结点类的模拟实现 迭代器类的模拟实现 构造函数 前置++与后置++ 前置- -与后置 - - == 与 !=运算符重载 * 运算符重载 - 运算符重载 普通迭代器总体实现代码 list类的实现 list类的成员变量 构造函数 迭代器 insert() erase() push_front/push_back/pop_front/pop_back front/back clear() empty()

    2024年04月09日
    浏览(60)
  • C++ [STL之list模拟实现]

    本文已收录至《C++语言》专栏! 作者:ARMCSKGT list的底层与vector和string不同,实现也有所差别,特别是在迭代器的设计上,本节将为大家介绍list简单实现,并揭开list迭代器的底层! 本文介绍list部分简单接口,以list迭代器的介绍为主! list底层是一个带头双向循环链表,在节

    2024年02月09日
    浏览(39)
  • 【STL】“list“容器从使用到模拟实现

    🎉博客主页:小智_x0___0x_ 🎉欢迎关注:👍点赞🙌收藏✍️留言 🎉系列专栏:C++初阶 🎉代码仓库:小智的代码仓库 list是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代。 list的底层是 双向链表结构 ,双向链表中每个元素存储在

    2024年02月16日
    浏览(87)
  • C++ STL学习之【list的模拟实现】

    ✨个人主页: 北 海 🎉所属专栏: C++修行之路 🎊每篇一句: 图片来源 A year from now you may wish you had started today. 明年今日,你会希望此时此刻的自己已经开始行动了。 STL 中的 list 是一个双向带头循环链表,作为链表的终极形态,各项操作性能都很优秀,尤其是 list 中迭代器

    2024年02月04日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包