1. Toy模板网首页
  2. > Toy博客

[C++]:12:模拟实现list

8月前 作者：随风飘扬@ 分类：Toy博客 阅读(31) 违法举报

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

一.看一看SGI的stl_list的源码：

1.基础结构+构造函数

1.节点结构：

[C++]:12:模拟实现list,c++,list,windows,模拟,算法,数据结构

1.SGI下的节点通过两个结构体实现。
2.基础的链表节点只包括前驱指针和后继指针。
3.链表节点去继承基础链表节点，新增节点数据。
4.优化掉指针类型带模板参数。

2.节点构造函数：

1.节点本身在这个地方是没有构造函数的。
2.观察下面的链表的结构和链表的构造函数可以观察出一点细节。

3.链表结构：

1._last_base类的构造通过_M_get_node方法进行节点的空间分配。
2.初始化一个基础的链表需要构造一个哨兵位的头节点。
3.开始的时候让哨兵位的头节点自己指向自己构造一个双向带头循环的一个结构。
4.list类继承_list_base类的时候里面多了许多的typedef

[C++]:12:模拟实现list,c++,list,windows,模拟,算法,数据结构
[C++]:12:模拟实现list,c++,list,windows,模拟,算法,数据结构

4.链表的构造函数：

1.通过上面的代码我们发现我们构造一个节点并没有通过节点的构造函数进行构造。
2.在list类型中提供一个方法去在插入新的节点的时候去调用。

[C++]:12:模拟实现list,c++,list,windows,模拟,算法,数据结构
[C++]:12:模拟实现list,c++,list,windows,模拟,算法,数据结构
[C++]:12:模拟实现list,c++,list,windows,模拟,算法,数据结构

2.析构

1.节点析构：

[C++]:12:模拟实现list,c++,list,windows,模拟,算法,数据结构

1.使用了内存池去回收节点的空间。

2.链表的析构：

[C++]:12:模拟实现list,c++,list,windows,模拟,算法,数据结构

3.迭代器

1.类比string或者vector他们的迭代器就是原生指针是比较方便的。
2.重写operator++ 和 operator*
3.对于节点来说结构不同于string和vector的。
4.参考SGI的源码发现对于内置类型是不可以实现运算符的重载。
5.实现一个迭代器的类型！

[C++]:12:模拟实现list,c++,list,windows,模拟,算法,数据结构

[C++]:12:模拟实现list,c++,list,windows,模拟,算法,数据结构

二.模拟实现list

1.基础结构+构造函数：

1.节点：

1.自己模拟实现就不这么复杂。
2.sgi通过内存池获取空间通过_creat_node get_node函数去对新增节点的创建。
3.节点自己把自己的数据在内部调整好的构造函数。
4.insert这样的函数去处理定义节点的问题。

//1.节点结构
	template<class T>
	struct ListNode {
		//1.节点的构造函数：
		ListNode(T x)
		{
			date = x;
		}
		//1.类+模板-->具体的类型。
		ListNode<T>* prev=nullptr;
		ListNode<T>* next=nullptr;
		T date;
	};

2.链表：

//3.链表结构
	template<class T>
	class list{
	public:
		//1.构造：双向带头循环链表的基本结构！
		list()
			:head(new ListNode<T>(T()))
		{
			head->prev = head;
			head->next = head;
		}
	private:
		ListNode<T>* head;
	};
}

3.实现迭代器+遍历数据：

1.内置类型没有办法进行运算符的重载。
2.迭代器本质就是节点的指针。
3.把一个节点指针类型包裹在一个自定义类型中。
4.在list和iterator_ListNode类中都对相应的类型进行了重定义。

1.迭代器实现：
template<class T>
	struct itreator_ListNode {
		//2.提供迭代器的方法：
		typedef itreator_ListNode<T> self;
		typedef ListNode<T> Node;
		Node* _node;

		itreator_ListNode(Node* x)
			:_node(x)
		{}

		//1.运算符重载：
		bool operator!=(self x)
		{
			return this->_node != x._node;
		}
		bool operator==(self x)
		{
			return this->_node == x._node;
		}
		//2.运算符重载++ --
		self& operator++()
		{
			this->_node = this->_node->next;
			return *this;
		}
		self operator++(int)
		{
			self ret = *this;
			this->_node = this->_node->next;
			return ret;
		}
		self& operator--()
		{
			this->_node = this->_node->prev;
			return *this;
		}
		self operator--(int)
		{
			self ret = *this;
			this->_node = this->_node->prev;
			return ret;
		}

		T& operator*()
		{
			return this->_node->date;
		}
	};

	template<class T>
	class list{
	public:
		//1.构造：双向带头循环链表的基本结构！
		list()
			:head(new ListNode<T>(T()))
		{
			head->prev = head;
			head->next = head;
		}

		//2.提供迭代器的方法：
		typedef itreator_ListNode<T> iterator;
		typedef ListNode<T> Node;

		//2-1:迭代器应该满足左闭右开

		//List_Node<T>* 类型到iterator类型是通过单参数的构造函数支持的！
		iterator begin() { return head->next; }
		iterator end() {return head;}

		
		void push_back(T x)
		{
			//1.产生一个节点：
			ListNode<T>* newnode = new ListNode<T>(x);
			//2.进行节点的连接：
			ListNode<T>* prev = head->prev;
			prev->next = newnode;
			newnode->prev = prev;
			head->prev = newnode;
			newnode->next = head;
		}


	private:
		Node* head;
	};
3.数据遍历(可读可写)

[C++]:12:模拟实现list,c++,list,windows,模拟,算法,数据结构

4.数据遍历（只读）

1.提供const迭代器。
2.注意：const迭代器并不是迭代器本身是const类型，如果迭代器本身是const类型不能实现operator++ 或者operator–。
3.有两个方法去实现const迭代器！

方法一：定义一个新的类：

//提供一个新的类
	template<class T>
	struct iterator_const_ListNode {
		//2.提供迭代器的方法：
		typedef iterator_const_ListNode<T> self;
		typedef ListNode<T> Node;
		Node* _node;

		iterator_const_ListNode(Node* x)
			:_node(x)
		{}

		//1.运算符重载：
		bool operator!=(self x)
		{
			return this->_node != x._node;
		}
		bool operator==(self x)
		{
			return this->_node == x._node;
		}
		//2.运算符重载++ --
		self& operator++()
		{
			this->_node = this->_node->next;
			return *this;
		}
		self operator++(int)
		{
			self ret = *this;
			this->_node = this->_node->next;
			return ret;
		}
		self& operator--()
		{
			this->_node = this->_node->prev;
			return *this;
		}
		self operator--(int)
		{
			self ret = *this;
			this->_node = this->_node->prev;
			return ret;
		}

		const T& operator*()
		{
			return this->_node->date;
		}

		/*self& operator=(self x)
		{
			this = x;
		}*/
	};

[C++]:12:模拟实现list,c++,list,windows,模拟,算法,数据结构
[C++]:12:模拟实现list,c++,list,windows,模拟,算法,数据结构
[C++]:12:模拟实现list,c++,list,windows,模拟,算法,数据结构

方法二：使用模板参数表示不同类型（泛型编程）

1.我们通过上面多去实现一个iterator_const_ListNode去实现const迭代器。
2.问题：代码冗余。
3.实现const迭代器就是实现一个const T& operator*返回类型的不同！

//2.节点封装-支持正向迭代器
	template<class T , class Ref>
	struct iterator_ListNode {
		//2.提供迭代器的方法：
		typedef iterator_ListNode<T,Ref> self;
		typedef ListNode<T> Node;
		Node* _node;

		iterator_ListNode(Node* x)
			:_node(x)
		{}

		//1.运算符重载：
		bool operator!=(self x)
		{
			return this->_node != x._node;
		}
		bool operator==(self x)
		{
			return this->_node == x._node;
		}
		//2.运算符重载++ --
		self& operator++()
		{
			this->_node = this->_node->next;
			return *this;
		}
		self operator++(int)
		{
			self ret = *this;
			this->_node = this->_node->next;
			return ret;
		}
		self& operator--()
		{
			this->_node = this->_node->prev;
			return *this;
		}
		self operator--(int)
		{
			self ret = *this;
			this->_node = this->_node->prev;
			return ret;
		}

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

		/*self& operator=(self x)
		{
			this = x;
		}*/
	};

//2.提供迭代器的方法：

		typedef iterator_ListNode<T,T&> iterator;
		typedef iterator_ListNode<T,const T&> const_iterator;
		typedef ListNode<T> Node;

		//2-1:迭代器应该满足左闭右开

		//List_Node<T>* 类型到iterator类型是通过单参数的构造函数支持的！
		iterator begin() { return head->next; }
		iterator end() {return head;}

		const_iterator cbegin() { return head->next; }
		const_iterator cend() { return head; }

3.拷贝构造+赋值

//1.拷贝构造：
		list(list& copy)
			:head(new ListNode<T>(T()))
		{
			head->prev = head;
			head->next = head;

			//循环copy调用push_back
			for (auto num : copy)
			{
				push_back(num);
			}
		}

//赋值相关+交换函数
		void swap(list& tmp)
		{
			Node* head = this->head;
			this->head = tmp.head;
			tmp.head = head;
		}

		list operator=(list tmp)
		{
			swap(tmp);
			return *this;
		}

2.增

1.insert

[C++]:12:模拟实现list,c++,list,windows,模拟,算法,数据结构

1.模拟实现第一个insert函数提供迭代器和插入的节点数据：

//为什么不可以iterator&类型返回
		//Node* 类型到iterator类型通过单参数的构造函数支持的：发生隐式类型转换！
		//Node* 类型到iterator&类型没有被支持的！
		iterator insert(iterator pos , T x = T())
		{
			//1.产生一个节点：
			Node* newnode = new ListNode<T>(x);
			//2.连接！
			Node* next = pos._node->next;
			pos._node->next = newnode;
			newnode->prev = pos._node;
			newnode->next = next;
			next->prev = newnode;

			return newnode;
		}

2.push_front && push_back

	void push_back(T x = T())
		{
			insert(head->prev, x);
		}
	void push_front(T x = T())
		{
			insert(head, x);
		}

3.删

1.erase

[C++]:12:模拟实现list,c++,list,windows,模拟,算法,数据结构

//2.删除考虑返回一下下一个位置的迭代器：
		iterator erase(iterator pos)
		{
			Node* prev = pos._node->prev;
			Node* next = pos._node->next;

			prev->next = next;
			next->prev = prev;

			//1.使用默认生成的析构函数
			delete pos._node;
			return next;
		}

2.pop_front && pop_back

void pop_back()
		{
			erase(head->prev);
		}

		void pop_front()
		{
			erase(head->next);
		}

4.查

1.find

iterator find(T x)
		{
			iterator cur = begin();
			while (cur != end())
			{
				if (cur._node->date == x)
					return cur;
				cur = cur._node->next;
				//单参数构造函数支持的隐式类型转换！
			}
			return nullptr;
		}

5.改：

2.amend

//修改数据：
		void amend(iterator pos,T x)
		{
			pos._node->date = x;
		}

6.析构函数：

[C++]:12:模拟实现list,c++,list,windows,模拟,算法,数据结构

1.clear 和 ~list

1.清除所有的节点数据会保留头节点。
2.使用clear后的状态应该满足只有一个哨兵位的头节点并且前驱指向自己后继指向自己。

//4.遍历链表清理节点：
		void clear()
		{
			Node* cur = head->next;
			while (cur != head)
			{
				Node* next = cur->next;
				delete cur;
				cur = next;
			}
			head->next = head;
			head->prev = head;
		}

		//析构：
		~list()
		{
			clear();
			delete head;
		}

7.容量相关的函数：

1.size()

//容量相关：
		size_t size()
		{
			assert(head != nullptr);
			int count = 0;
			if (empty())
				return 0;
			else
			{
				iterator cur = begin();
				while (cur != end())
				{
					count++;
					cur = cur._node->next;
					//单参数构造函数支持的隐式类型转换！
				}
				return count;
			}
		}

2.empty()

bool empty()
		{
			assert(head != nullptr);
			if (head->next == head)
				return true;
			return false;
		}

8.实现operator->的意义：

[C++]:12:模拟实现list,c++,list,windows,模拟,算法,数据结构

主要思路：
1.实现了一个自定义类型AB。
2.push_back多个匿名AB类型的对象到链表l1中。
3.通过迭代器遍历链表数据。
4.因为我们没有去重载AB类型的operator流插入，所以不可以正常的打印数据。

1.简单解决问题的方法：

[C++]:12:模拟实现list,c++,list,windows,模拟,算法,数据结构

2.实现operator->

1.我们知道->结构体指针类型的对象去访问成员变量的一个方法。
2.实现operator->要比对一个类型去实现operator<< operator>>方便。
3.通过->访问AA数据考虑const还是非const的？
4.给模板再加上一个参数去确定operator->返回值类型。

template<class T , class Ref , class arrows>
	struct iterator_ListNode {
		//2.提供迭代器的方法：
		typedef iterator_ListNode<T,Ref,arrows> self;
		typedef ListNode<T> Node;
		Node* _node;

		iterator_ListNode(Node* x)
			:_node(x)
		{}

		//1.运算符重载：
		bool operator!=(self x)
		{
			return this->_node != x._node;
		}
		bool operator==(self x)
		{
			return this->_node == x._node;
		}
		//2.运算符重载++ --
		self& operator++()
		{
			this->_node = this->_node->next;
			return *this;
		}
		self operator++(int)
		{
			self ret = *this;
			this->_node = this->_node->next;
			return ret;
		}
		self& operator--()
		{
			this->_node = this->_node->prev;
			return *this;
		}
		self operator--(int)
		{
			self ret = *this;
			this->_node = this->_node->prev;
			return ret;
		}

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

		arrows operator->()
		{
			return &(this->_node->date);
		}

		/*self& operator=(self x)
		{
			this = x;
		}*/
	};

//2.提供迭代器的方法：
		typedef iterator_ListNode<T,T&, T* > iterator;
		typedef iterator_ListNode<T,const T&,const T*> const_iterator;
		typedef ListNode<T> Node;

		//2-1:迭代器应该满足左闭右开

		//List_Node<T>* 类型到iterator类型是通过单参数的构造函数支持的！
		iterator begin() { return head->next; }
		iterator end() {return head;}

		const_iterator cbegin() { return head->next; }
		const_iterator cend() { return head; }

[C++]:12:模拟实现list,c++,list,windows,模拟,算法,数据结构
[C++]:12:模拟实现list,c++,list,windows,模拟,算法,数据结构

3.一个问题：

[C++]:12:模拟实现list,c++,list,windows,模拟,算法,数据结构

1.在这个地方去访问数据的时候应该是两个箭头。
2.第一个箭头是重载的operator->的箭头。
3.第二个箭头是返回T或者constT 去访问数据的箭头。
4.为什么只通过一个箭头就访问到数据了呢？

[C++]:12:模拟实现list,c++,list,windows,模拟,算法,数据结构

1.按照我们之前的理解方法二是没有任何问题我们想要去掉operator按照之前的理解应该转化成方法三。
2.方法三为什么是错误的呢？
3.因为我们需要提供可读性所以我们让编译器去做了操作优化成了方法一的这样的语法。
4.总结：理论上应该优化为方法三但是为了可读性所以优化为了方法一：编译器承担了一切。文章来源地址https://www.toymoban.com/news/detail-814378.html

到了这里，关于[C++]:12:模拟实现list的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

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

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 数据结构之List（双向链表）的实现

    方法名 参数 功能 返回 find const T val, int n, listNode * p 区间查找 从p往前数n个节点 指针或NULL const T val, listNode * p 区间查找 从p往前到首节点 const T val 查找 Size void 链表规模 size empty void 判空 bool first void 返回首节点 首节点指针 clear void 清空链表 void insertAsFirst const T val 作为首节

    2024年02月16日
    浏览(36)
  • 【数据结构与算法】【12】前缀表达式、中缀表达式、后缀表达式

    【数据结构与算法】【12】前缀表达式、中缀表达式、后缀表达式

    什么是前缀表达式、中缀表达式、后缀表达式 前缀表达式、中缀表达式、后缀表达式，是通过树来存储和计算表达式的三种不同方式 以如下公式为例 ( a + ( b − c ) ) ∗ d ( a+(b-c) )*d ( a + ( b − c ) ) ∗ d 通过树来存储该公式，可以表示为 那么问题就来了，树只是一种抽象的数据

    2024年02月08日
    浏览(38)
  • 【数据结构】“栈”的模拟实现

    【数据结构】“栈”的模拟实现

    💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤 📃 个人主页 ：阿然成长日记 👈点击可跳转 📆 个人专栏： 🔹数据结构与算法🔹C语言进阶 🚩 不能则学，不知则问，耻于问人，决无长进 🍭 🍯 🍎 🍏 🍊 🍋 🍒 🍇 🍉 🍓 🍑 🍈 🍌 🍐 🍍 栈 ：一种特殊的线性

    2024年02月12日
    浏览(33)
  • 【数据结构】顺序队列模拟实现

    【数据结构】顺序队列模拟实现

    💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤 📃 个人主页 ：阿然成长日记 👈点击可跳转 📆 个人专栏： 🔹数据结构与算法🔹C语言进阶 🚩 不能则学，不知则问，耻于问人，决无长进 🍭 🍯 🍎 🍏 🍊 🍋 🍒 🍇 🍉 🍓 🍑 🍈 🍌 🍐 🍍 一、队列的基本概念

    2024年02月10日
    浏览(30)
  • 【数据结构】 List与顺序表及接口的实现

    【数据结构】 List与顺序表及接口的实现

    在集合框架中， List是一个接口，继承自Collection。 Collection也是一个接口，该接口中规范了后序容器中常用的一些方法，具体如下所示： Iterable也是一个接口，表示实现该接口的类是可以逐个元素进行遍历的，具体如下： List 的官方文档 站在数据结构的角度来看， List就是一

    2024年02月12日
    浏览(31)
  • 一起学数据结构(12)——归并排序的实现

    一起学数据结构(12)——归并排序的实现

    归并排序的大概原理如下图所示：         从图中可以看出，归并排序的整体思路就是把已给数组不断分成左右两个区间，当这个区间中的数据数量到达一定数值时，便返回去进行排序，整体的结构类似二叉树的结构，因此，对于归并排序同样可以利用递归进行实现。    

    2024年02月08日
    浏览(32)
  • 【数据结构】_4.List接口实现类LinkedList与链表

    【数据结构】_4.List接口实现类LinkedList与链表

    目录 1.链表的结构与特点 1.1 链表的结构： 1.2 链表的特点： 2. 不带头单链表的模拟实现 3. 单链表OJ 3.1 题目1：移除链表元素:  3.2 题目2：反转一个单链表 3.3 题目3：返回链表的中间结点 3.4 题目4：链表的倒数第k个结点 3.5 题目5：合并两个有序链表 3.6 题目6：链表的回文结构

    2024年02月15日
    浏览(35)
  • 【LeetCode】数据结构题解（12）[用栈实现队列]

    【LeetCode】数据结构题解（12）[用栈实现队列]

    所属专栏：玩转数据结构题型❤️ 🚀 博主首页：初阳785❤️ 🚀 代码托管：chuyang785❤️ 🚀 感谢大家的支持，您的点赞和关注是对我最大的支持！！！❤️ 🚀 博主也会更加的努力，创作出更优质的博文！！❤️ 🚀 关注我，关注我，关注我，重要的事情说三遍！！！！！

    2024年02月13日
    浏览(30)
  • 模拟实现链式二叉树及其结构学习——【数据结构】

    模拟实现链式二叉树及其结构学习——【数据结构】

    W...Y的主页 😊 代码仓库分享 💕 之前我们实现了用顺序表完成二叉树(也就是堆)，顺序二叉树的实际作用就是解决堆排序以及Topk问题。 今天我们要学习的内容是链式二叉树，并且实现链式二叉树，这篇博客与递归息息相关！ 目录 链式存储 二叉树链式结构的实现 链式二叉

    2024年02月07日
    浏览(29)

  • 数据结构 模拟实现ArrayList顺序表

    目录 一、顺序表中的接口 二、顺序表中的方法实现 （1）display方法 （2）add方法 1、不指定下标位置插入 2、指定下标位置插入 （3）contains方法 （4）indexOf方法 （5）get方法 （6）set方法 （7）remove方法 （8）size方法 （9）clear方法 三、最终代码 代码如下： 以上的方法就是我们

    2024年02月04日
    浏览(37)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包