初夏小谈:模拟实现list以及list与vector的区别

list容器在底层使用双向链表实现的。数据存在每个节点中，并且每个结点还有两个空间分别存放两个指针用来找寻它的前后节点。

在C+11中还引入了forward_list它的底层是单链表实现的。在只实现尾插，头插头删时比list更加高效。

在list还会分配一些额外空间来保存结点的相关联信息。

list基本接口：

一、在list中构造有四种分别是：1.构造空list。2.构造N个值为data的list。3.拷贝构造函数。4.用区间来构造。

  1. list()
  2. list(size_type n, const value_type& val = value_type())
  3. list(const list& L)
  4. list(InputIterator first, InputIterator last)

二、list中常用容量操作有两种：1.判断list是否为空。2.计算list的有效数据个数。由于list是链表实现所以不需对容量操作。

  1. bool empty() const
  2. size_t size() const

三、元素访问操作：由于list是链表实现。不支持随机访问操作。两种操作：1.访问第一个元素。2.访问最后一个元素。

  1. reference front()
  2. const_reference front() const
  3. reference back()
  4. const_reference back() const

四、元素修改操作：1.头插。2.头删。3.尾插。4.尾删。5.在某位置插入。6.在某位置插入N个值为data的数据。7.在某个位置插入一块区间内的所有数据。8.删除某个位置上的元素。9.删除list中某块区域中的所有结点。10.交换两个数据。11.修改有效结点个数，倘若不够用data填充。12.清空所有数据。

  1. void push_front(const value_type& val)
  2. void pop_front()
  3. void push_back(const value_type& val)
  4. void pop_back()
  5. iterator insert(iterator position, const value_type& val)
  6. void insert(iterator position, size_type n,const value_type& val)
  7. void insert(iterator position, InputIterator first, InputerIterator last)
  8. iterator erase(iterator position)
  9. iterator erase(iterator first, iterator last)
  10. void swap(list& x)
  11. void resize(size_type n,value_type val = value_type())
  12. void clear()

五、迭代器操作：1.返回第一个元素的迭代器。2.返回最后一个元素的下一个位置的迭代器

  1. begin()
  2. end()
  3. rbegin()
  4. rend()

六、list中迭代器失效问题：

迭代器失效就是迭代器所指向的空间无效。就是迭代器所指向的结点被删除了。所以删除结点时会导致指向删除结点的迭代器失效，而其它迭代器不会失效。

在list中插入数据不会导致迭代器失效，是因为迭代器所指向的数据不会被搬移。这就是链表的好处。

七模拟实现list：

在实现普通类型的函数操作时和链表实现相似。但是在实现迭代器操作时，就不能像vector那样直接用原生态指针来模拟。因为在list中数据不连续。所以对原生态指针的操作必须封装来模拟实现。

#include<iostream>
#include<list>
using namespace std;


//list底层结构：带头节点的双向循环链表
//为什么带头节点
//1.头部插入和删除比较简单
//2.区分begin(),和end()

namespace ListS
{
	template<class T>
	struct ListNode
	{
		ListNode(const T& data = T())
			:Prev(nullptr)
			, Next(nullptr)
			, data(data)
		{}
		ListNode<T>* Prev;
		ListNode<T>* Next;
		T data;
	};

	//迭代器当成像指针一样的方式使用：指针具有的操作 迭代器都必须支持

	//operator*()
	//operator->()
	//operator++()
	//operator--()：视具体结构对待
	//operator!=()
	//operator==()


	template<class T, class Ref, class Ptr>                //三个参数分别是什么意思各自的作用？？？
	//template<class T, class Ref, class Ptr> 
	//T 元素类型
	//普通类型：
	//Ref代表T&   Ptr代表T*
	//const时
	//Ref代表const T&，  Ptr代表const T*
	//为了统一普通类型和const类型
	


	//1.实现这个迭代器类是因为它不是原生态指针，底层是双向链表，空间不一定连续。
	//2.在这个类中实现++，--，==，!=，*，->。操作（指针操作，迭代器都可以支持）
	//3.直接在list类中内嵌对应迭代器类型使用。为简单取别名
	//typedef ListIterator<> iterator

	struct ListIterator
	{
		typedef ListNode<T>* PNode;
		typedef ListIterator<T, Ref, Ptr> Self;
		typedef Ref Ref;
		typedef Ptr Ptr;
	public:
		ListIterator(PNode pNode = nullptr)
			:NodePtr(pNode)
		{}
		ListIterator(const Self& s)
			:NodePtr(s.NodePtr)
		{}

		Ref operator*()
		{
			return NodePtr->data;
		}

		Ptr operator->()
		{
			return &(operator*());
		}

		Self& operator++()
		{
			NodePtr = NodePtr->Next;
			return *this;
		}

		Self operator++(int)
		{
			Self temp(*this);
			NodePtr = NodePtr->Next;
			return temp;
		}

		Self& operator--()
		{
			NodePtr = NodePtr->Prev;
			return *this;
		}

		Self operator--(int)
		{
			Self temp(*this);
			NodePtr = NodePtr->Prev;
			return temp;
		}

		bool operator!=(const Self& s)
		{
			return NodePtr != s.NodePtr;
		}
		bool operator==(const Self& s)
		{
			return NodePtr == s.NodePtr;
		}
	//private:
		PNode NodePtr;
	};

	//反向迭代器
	//对正向迭代器的封装，迭代器适配器
	template<class Iterator>
	class ReverseIterator
	{
		//typedef ListIterator<T, T&, T*> iterator;
		typedef ReverseIterator<Iterator> Self;

		//typename : 告诉编译器Ref是Iterator类型中的内嵌类型，而不是静态的成员变量
		typename typedef Iterator::Ref Ref;
		typename typedef Iterator::Ptr Ptr;
	public:
		//构造函数
		ReverseIterator(Iterator it)
			:_it(it)
		{}

		//拷贝构造函数
		ReverseIterator(const Self& rit)
			:_it(rit._it)
		{}

		//重载各种反向迭代器操作
		Ref operator*()
		{
			Iterator& temp(_it);
			--temp;
			return *temp;
		}
		Ptr operator->()
		{
			return &(operator*());
		}
		Self& operator++()
		{
			--_it;
			return *this;
		}

		Self& operator++(int)
		{
			Self temp(*this);
			--_it;
			return temp;
		}

		Self& operator--()
		{
			++_it;
			return *this;
		}

		Self& operator--(int)
		{
			Self temp(*this);
			++_it;
			return temp;
		}

		bool operator!=(const Self& s)
		{
			return _it != s._it;
		}

		bool operator==(const Self& s)
		{
			return _it == s._it;
		}

	public:
		Iterator _it;
	};

	template<class T>
	class list
	{
		typedef ListNode<T> Node;
	public:
		typedef ListIterator<T, T&, T*> iterator;
		typedef ListIterator<T, const T&, const T*> const_iterator;
		typedef ReverseIterator<iterator> reverse_iterator;
	public:
		//**********************************************************************
		//1.链表创建操作

		list()
		{
			CreatHeadNode();
		}

		list(size_t n, const T& data = T())
		{
			CreatHeadNode();
			//Node* ptr = HeadPtr;
			for (size_t i = 0; i < n; ++i)
			{
				push_back(data);
			}
		}

		list(T* first, T* last)
		{
			CreatHeadNode();
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}

		//拷贝构造
		list(list<T>& L)
		{
			CreatHeadNode();
			for (const auto& e : L)
			{
				push_back(e);
			}
		}

		//运算符重载
		list<T>& operator=(const list<T>& L)
		{
			if (HeadPtr != &l)
			{
				for (const auto& e : L)
				{
					push_back(e);
				}
			}
		}

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

		//**********************************************************************
		//2.容量操作

		//1.有效结点的个数
		size_t size()const
		{
			size_t count = 0;
			Node* ptr = HeadPtr->Next;
			while (ptr != HeadPtr)
			{
				count++;
				ptr = ptr->Next;
			}
			return count;
		}

		//2.判断是否为空
		bool empty()const
		{
			return HeadPtr == HeadPtr->Next;
		}

		//3.设置有效链表的长度
		void resize(size_t NewSize, const T& data =T())
		{
			size_t OldSize = size();
			if (NewSize > OldSize)
			{
				for (size_t i = OldSize; i < NewSize; i++)
				{
					push_back(data);
				}
			}
			else
			{
				for (size_t i = OldSize; i > NewSize; i--)
				{
					pop_back();
				}
			}
		}

		//**********************************************************************
		//3.元素访问操作

		//1.访问首元素
		T& front()
		{
			return HeadPtr->Next->data;
		}
		//1.1
		const T& front()const
		{
			return HeadPtr->Next->data;
		}
		
		//2.访问尾元素
		T& back()
		{
			return HeadPtr->Prev->data;
		}
		//2.1
		const T& back()const
		{
			return HeadPtr->Prev->data;
		}

		//***************************************************************
		//4.元素修改操作

		//1.尾插
		void push_back(const T& data)
		{
			insert(end(), data);
		}

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

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

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

		//5.任意位置插入
		iterator insert(iterator position, const T& data)
		{
			Node* pos = position.NodePtr;
			Node* NewNode = new Node(data);

			NewNode->Next = pos;
			NewNode->Prev = pos->Prev;

			pos->Prev->Next = NewNode;
			pos->Prev = NewNode;

			return iterator(NewNode);
		}

		//6.任意位置删除
		iterator erase(iterator position)
		{
			Node* DelNode = position.NodePtr;
			if (DelNode == HeadPtr)
			{
				return iterator(HeadPtr);
			}
			Node* pRet = DelNode->Next;

			DelNode->Next->Prev = DelNode->Prev;
			DelNode->Prev->Next = DelNode->Next;
			delete DelNode;

			return iterator(pRet);
		}

		//7.清空list
		void clear()
		{
			Node* ptr = HeadPtr->Next;
			while (ptr != HeadPtr)
			{
				HeadPtr->Next = ptr->Next;
				delete ptr;
				ptr = HeadPtr->Next;
			}

			HeadPtr->Next = HeadPtr;
			HeadPtr->Prev = HeadPtr;
		}

		//***********************************************************************
		//5.迭代器操作
		
		//1.
		iterator begin()
		{
			return iterator(HeadPtr->Next);
		}

		iterator end()
		{
			return iterator(HeadPtr);
		}

		const const_iterator cbegin()const
		{
			return const_iterator(HeadPtr->Next);
		}

		const const_iterator cend()const
		{
			return const_iterator(HeadPtr);
		}

		reverse_iterator rbegin()
		{
			return reverse_iterator(iterator(HeadPtr));
		}

		reverse_iterator rend()
		{
			return reverse_iterator(iterator(HeadPtr->Next));
		}

	private:
		void CreatHeadNode()
		{
			HeadPtr = new Node;
			HeadPtr->Next = HeadPtr;
			HeadPtr->Prev = HeadPtr;
		}
	private:
		Node* HeadPtr;
	};
}

template<class T>
void PrintList(ListS::list<T>& L)
{
	auto it = L.begin();
	while (it != L.end())
	{
		cout << *it << "--->";
		++it;
	}
	cout << "NULL" << endl;
}

int main()
{
	int array[] = { 1,2,3,4,5 };
	ListS::list<int> L(array, array + sizeof(array) / sizeof(array[0]));
	L.push_back(6);
	L.push_front(0);
	PrintList(L);

	//ListS::list<int>::reverse_iterator it = L.rbegin();

	auto it = L.rbegin();//

	while (it != L.rend())
	{
		cout << *it << "--->";
		//++it;
	}
	cout << "NULL" << endl;

	cout << L.front() << endl;
	cout << L.back() << endl;
	cout << L.size() << endl;

	L.pop_front();
	L.pop_back();
	PrintList(L);

	L.resize(10, 6);
	PrintList(L);

	L.resize(5);
	PrintList(L);

	L.clear();
	cout << L.size() << endl;
	system("pause");
	return 0;
}

运行：

 八、list与vector区别：

  1. vector是动态顺序表实现，是一块连续的空间，而list是带头结点的双向循环链表。
  2. vector可以随机访问元素，list不支持
  3. vector的插入元素效率低，因为可能需要扩容和搬移数据。而list任意位置插入删除都只需要更改要插入的数据指向和它前后结点的指向。
  4. vector底层不易造成内存碎片，空间和缓存利用率高。list每次都要开辟结点，内存容易碎片化，利用率低。
  5. vector迭代器是原生态指针。list迭代器是对原生态指针的一层封装。
  6. vector的插入和删除都可以造成迭代器失效，list删除数据可以造成迭代器失效插入不会导致迭代器失效。

                                                                                                                                                         珍&源码

全部评论

相关推荐

05-01 00:04
电子科技大学 嵌入式工程师
嵌入式秋招总结第五弹之实习注意事项
咨询我实习的同学越来越多，相信大家都已经找到了实习，不过大家似乎都在疑惑实习如果是干打杂的活怎么办？实习优缺点吗？如何快速上手实习？去年我也是怀着类似忐忑的心情去实习的，但大家都在实习，所以尽管有疑虑但依然会选择去实习。那么我们先回答第一个问题，如何看待实习，实习真的有价值吗？首先，实习的重要性毋庸置疑，特别是暑期实习，因为现在很多公司对暑期实习生特别看重，一般公司秋招都会优先考虑暑期实习生，所以如果你想去某个公司，那你应该尽量先去投递它的暑期实习岗位。而且，实习的项目也会让你秋招投递其他公司更有作用，当然作用有多大，这与你的岗位，你的项目内容都会有关系，在如今越来越卷的情况下，公司的titl...
投递美的集团等公司6个岗位 > 牛客激励计划 牛客创作赏金赛
点赞 评论 收藏
分享
04-27 10:38
蚌埠坦克学院 嵌入式软件开发
嵌入式图形库是学LVGL好还是学QT好？
在嵌入式图形界面的世界里，Qt&nbsp;和&nbsp;LVGL&nbsp;是两座绕不开的大山。但很多同学在学习时，常常会问：“我到底该学Qt，还是学LVGL呢？”“哪个更适合嵌入式项目？未来发展哪个更好？”今天这篇文章，我们就来一次全面对比，帮你找到**最适合你的学习方向！**🧭一、基本介绍：Qt&nbsp;vs&nbsp;LVGL定位跨平台GUI框架（桌面、移动端、嵌入式）轻量级嵌入式GUI库（超低资源消耗）体积大小硬件要求高（需要Linux环境，至少几十MB内存）低（KB级内存也能跑）渲染机制支持OpenGL、Vulkan等高级图形加速纯软件绘制或简单硬件加速开发语言C++（也支持QML脚本）C语言界面风格现代、高度可定制、丰富控件简...
嵌入式面试八股文全集
点赞 评论 收藏
分享
03-10 14:19
已编辑
重庆邮电大学 前端工程师
春招投递情况
千分之一也是让我遇上了
球Offer上岸👑：测试也难求一面 逆天
点赞 评论 收藏
分享
04-25 18:13
五邑大学 Java
大二下，急招实习，各位大佬请给点建议。
无面如何呢：用心包装一下自己的实习
点赞 评论 收藏
分享
昨天 10:30
南阳理工学院 Java
暑期后端实习总结
笨人BG中九+水硕，技术栈广而不深，尤其是java技术栈几乎是二月底才开始接触认真学的，微服务没学、消息队列没学。从三月底开始投，投了三十多家都是后端或大模型开发，陆陆续续面了二十场左右面试，最后拿下三个offer：滴滴、美团、云智。虽然没能去最想去的鹅，但也挺满意的。准备路线：一月底开始刷leetcode，基本就是刷了一遍代码随想录、hot100，面试150刷了一部分，后面就在刷面经里的题目了。项目是二月才开始准备的，做了一个后端项目和一个RAG项目，这部分实在太薄弱了，现在看来准备时间太少了，理解也不够深入。八股也是二月中旬开始看的，把小林coding看完再结合面经，个人感觉差不多...
投递美团等公司6个岗位 >
点赞 评论 收藏
分享
评论
点赞
收藏
分享

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 机械人与华为的爱恨情仇 #
103781次浏览 923人参与
# 24届硬件人与华为的爱恨情仇 #
118426次浏览 962人参与
# 你最满意的offer薪资是哪家公司？ #
16234次浏览 119人参与
# 硬件兄弟们 甩出你的华为奖状 #
93610次浏览 670人参与
# 运营面经 #
99246次浏览 1202人参与
# 来聊聊机械薪资天花板是哪家 #
110587次浏览 721人参与
# 机械人怎么评价今年的华为 #
188870次浏览 1502人参与
# 找工作，行业重要还是岗位重要？ #
13377次浏览 245人参与
# 机械专业只有考研才有出路吗 #
93658次浏览 850人参与
# 金融财会交流会 #
99265次浏览 361人参与
# 摸鱼被leader发现了怎么办 #
41845次浏览 316人参与
# 潍柴工作体验 #
17794次浏览 17人参与
# 国企还是互联网，你怎么选？ #
124377次浏览 961人参与
# 外包能不能当跳板？ #
23269次浏览 192人参与
# 机械人还在等华为开奖吗？ #
212461次浏览 1088人参与
# 盲审过后你想做什么？ #
14071次浏览 121人参与
# 五一之后，实习真的很难找吗？ #
50668次浏览 355人参与
# 你觉得通信/硬件有必要实习吗？ #
93066次浏览 892人参与
# 国企/银行/研究所公司爆料 #
121998次浏览 742人参与
# Offer比较，求稳定还是求发展 #
39788次浏览 226人参与
牛客网
牛客企业服务