【C++】一文带你走进list的模拟实现

🌈欢迎来到C++专栏~~list模拟实现


  • (꒪ꇴ꒪(꒪ꇴ꒪ )🐣,我是Scort
  • 目前状态:大三非科班啃C++中
  • 🌍博客主页:张小姐的猫~江湖背景
  • 快上车🚘,握好方向盘跟我有一起打天下嘞!
  • 送给自己的一句鸡汤🤔:
  • 🔥真正的大师永远怀着一颗学徒的心
  • 作者水平很有限,如果发现错误,可在评论区指正,感谢🙏
  • 🎉🎉欢迎持续关注!
    在这里插入图片描述

请添加图片描述

select选择器

婚礼

list的模拟实现

引发异常原因分析

请添加图片描述

爬虫必备知识详解

上问我们得知:list带头双向循环链表,支持在任意位置O(1)的插入和删除

软件构建

一. list大框架

list_node节点

开源

namespace ljj
{
	template<class T>
	class list_node
	{
		T _data;
		list_node<T>* _next;
		list_node<T>* _prev;

		//构造
		list_node(const T& x = T())//全缺省 ~ 构造匿名对象
			:data(x)
			,_next(nullptr)
			,_prev(nullptr)
		{}
	};
	
	template<class T>
	class list
	{
		typedef list_node<T> Node;
	public:
		list()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
		}

	private:
		Node* _head;
	};

为了测试,我们迅速实现一个尾插吧,忘记的话可以画图(我画的有点丑)
在这里插入图片描述

蓝牙权限适配

		//尾插
		void push_back(const T& x)
		{
			Node* tail = _head->_prev;
			Node* newnode = new Node(x);

			//_head      tail     newnode
			tail->_next = newnode;
			newnode->_prev = tail;
			newnode->_next = _head;
			_head->_prev = newnode;
		}

二 .迭代器(狠重要)

🌍相比vector和string那些连续的物理空间,原生指针就是天生的迭代器,但对于list在空间上不连续的数据结构,解引用不能取到数据,++也不能到不了下一个节点

mysql 索引使用详解

为此,对于链表的迭代器,我们用自定义类型结点的指针进行封装,底层仍然是结点的指针。C++的自定义类型支持运算符重载,原本的运算符编程变成函数调用,这样就可以实现像内置类型一样使用运算符,这就是c++厉害的地方 up!

C/C++

构造迭代器,仅需要一个节点就可以构造了

ios解锁大师有用吗

	template<class T>
	struct __list_iterator
	{
		typedef ListNode<T> Node;
		typedef __list_iterator<T,Ref,Ptr> Self;
		Node* _node;//节点指针

		__list_iterator(Node* x)//提供一个节点构造
			: _node(x)
		{}
    };

迭代器的拷贝构造&赋值重载都不需要我们自己实现,因为我们要的就是浅拷贝,用编译器默认生成的即可

aasa文件

灵魂发问:迭代器需不需要析构函数,把节点释放掉?不要释放节点归链表管,迭代器是借助结点指针来访问修改链表的,不属于迭代器管,好比人家借东西给你用,你却把人家东西故意弄丢了,很可笑

FMC

🌍iterator & const_iterator

  • 我们在list中进行typedef,这样所有容器迭代器名字统一都是iterator
  • 我们知道const迭代器和普通迭代器的唯一区别就是:普通迭代器返回的是T&可读可写const迭代器返回的是const T&,可读不可写。我们当然可以再继续封装一个类(此处不能重载,因为返回值不同),__const_list_iterator类,但是会造成代码冗余,看了源码我们发现:传入模板参数解决了这个问题,这也是迭代器的精华

在这里插入图片描述

eNSP

🎨重载 *

*it 就是要取迭代器指向的数据,并且返回这个数据的引用,可以修改

vbs

//*it -> it.opeartor*()    可读可写
T& operator*()
{
	return _node->_data;
}

🎨重载 ->

如果T不是int等内置类型,而是自定义类型,我们访问其中的成员,需要重载->

启动模式

	struct pos
	{
		int _a1;
		int _a2;

		pos(int a1 = 0 , int a2 = 0)
			:_a1(a1)
			,_a2(a2)
		{}
	};

	void test_list2()
	{
		int x = 10;
		int* p1 = &x;

		cout << *p1 << endl;

		pos aa;
		pos* p2 = &aa;
		p2->_a1;
		p2->_a2;//找结构体成员

		list<pos> lt;
		lt.push_back(pos(10, 20));
		lt.push_back(pos(20, 50));

		list<pos>::iterator it = lt.begin();
		while (it != lt.end())
		{
		    //cout << *it << endl; // 错误示范,请勿模仿
            // 因为Date是自定义类型,需要重载<<来打印,但要就是不给你提供呢,下面这样是可以的,很别扭
			//cout << (*it)._a1 << ":" << (*it)._a2 << endl;
			cout << it->_a1 << ":" << it->_a2 << endl;
			++it;
		}
		cout<< endl;
	}
}

迭代器it是去模仿指针的行为。在list中,如果节点中是int这样的内置类型,解引用(本质调用函数)访问数据即可;而像这里一个结构体的指针,我们固然可以(*it)拿到日期类对象.访问成员,但我们更希望能->访问成员,因此我们还需要重载->

备忘录微信小程序

		//  ->    
 		T* operator->()
		{
			return &(operator*());//调用了operator*() -> &(_node->data)
		}

在这里插入图片描述

vscode

这里本来应该是it->->_year,但是这样写运算符可读性太差了,所以编译器进行了优化,省略了一个->,对于cosnt对象,就是返回const指针,也就是添加了ptr参数的原因

无线投屏

在这里插入图片描述

str和repr原理

🎨++ / – 和 == / !=

此处比较简单,直接上代码了

单点登录

        //  ++it  返回值还是迭代器   日期类++返回的是日期类
		iterator& operator++()
		{
			_node = _node->_next;
			return *this;
		}

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

		//--it
		iterator& operator--()
		{
			_node = _node->_prev;
			return *this;
		}

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

🌍反向迭代器(迭代器适配器)

反向迭代器就是对正向迭代器的封装,这样它可以是任意容器的反向迭代器。

sed命令使用

  • 二者的不同之处:++调的是正向迭代器的–;–调的是正向迭代器的++
  • 源码中为了对称的设计,使正向迭代器&反向迭代器的开始和结束保持对称,解引用*取前一个位置(我的开始就是你的结束

在这里插入图片描述在这里插入图片描述
为啥要这样子对称设计呢?直接解引用当前位置(哨兵位)的值,可能是随机值,出错

扩展性

对于vector的反向迭代器,如果是我们预想的那样(解引用取的是当前位置),会有越界访问问题

机器学习

在这里插入图片描述

干货

为了获取数据类型T,我们还需要增加两个类模板参数RefPtr,同时也可以区分普通参数与const参数。源码中不带这两个参数,是通过迭代器萃取技术实现的(难难难)

os

namespace ljj
{
	//复用, 迭代器适配器  给list就出list的反向迭代
	template<class Iterator, class Ref, class Ptr>
	struct __reverse_iterator
	{
		Iterator _cur;
		typedef __reverse_iterator<Iterator, Ref, Ptr> RIterator;

		__reverse_iterator(iterator it)
			:_cur(it)
		{}

		RIterator operator++()
		{
			--_cur;
			return *this;
		}

		RIterator operator++(int)
		{
			RIterator(tmp);
			--_cur;
			return tmp;
		}

		RIterator operator--()
		{
			++_cur;
			return *this;
		}

		RIterator operator--(int)
		{
			RIterator(tmp);
			++_cur;
			return tmp;
		}

		Ref operator*()
		{
			Iterator tmp = _cur;
			return *(--tmp);//解引用上一个位置
		}

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

		bool operator!=(const RIterator& it)
		{
			return _cur != it._cur;
		}

		bool operator==(const RIterator& it)
		{
			return _cur == it._cur;
		}
	};
}

反向迭代器:迭代器适配器,可以适配支持符合的反向迭代器

在这里插入图片描述

三. 增删查改

⚡insert & erase

💦insert

  • 插入的位置是pos的上一个
  • 返回值newnode位置的迭代器
  • list的insert会导致迭代器失效吗?我们知道vector中迭代器失效的原因:扩容导致的野指针;pos意义改变,显然这里都不符合,所以不会发生
		iterator insert(iterator pos, const T& x)
		{
			Node* cur = pos._node;
			Node* prev = cur->_prev;

			Node* newnode = new Node(x);

			//prev   newnode   cur
			prev->_next = newnode;
			newnode->_prev = prev;
			newnode->_next = cur;
			cur->_prev = newnode;

			return iterator(newnode);//构造迭代器返回
		}

在这里插入图片描述

💦erase

  • 注意哨兵位的头结点不能删
  • 返回值是删除位置的下一个数据的迭代器
  • erase后迭代器必定失效,节点都被干掉了,pos你说指向哪里?
		//删除
		iterator erase(iterator pos)
		{
			assert(pos != ens());//哨兵位头结点不能删
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* next = cur->_next;
			//prev   cur   next

			prev->_next = next;
			next->_prev = prev;
			delete cur;

			return iterator(next);
		}

⚡push_back & push_front

注意插入位置
在这里插入图片描述

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

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

⚡pop_back & pop_front

也是要注意删除的位置

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

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

四. list的默认成员函数

🌈构造

✨无参构造

    list()
    {
        _head = new Node;
        _head->_prev = _head;
        _head->_next = _head;
    }

✨迭代器区间构造

	//迭代器区间构造
	template <class InputIterator>  
	list(InputIterator first, InputIterator last)
	{
		while (first != last)
		{
			push_back(*first);//前提是已经构造了头结点
			++first;
		}
	}

所以我们干脆实现一个empty_init来初始化,

	void empty_init()
	{
	    //创建并初始化哨兵位的头结点
		_head = new Node;
		_head->_next = _head;
		_head->_prev = _head;
	}

注意必须给一个头,否则_head是一个随机值,换给tmp后出作用域调用析构函数,clear时获取begin()要解引用 _head-> _next会崩溃

🌈~析构 & clear

🌍claer
查阅文档发现库中还提供了一个clear的函数
在这里插入图片描述

注意要给给it ,因为erase后此结点失效,返回下一个节点的迭代器

	//clear 不清理头结点
	void clear()
	{
		iterator it = begin();
		while (it != end())
		{
			it = erase(it);//注意要给给it ,因为erase后此结点失效,返回下一个节点的迭代器
		}
	}

🌍析构函数

因此析构可以直接复用clear,但头结点也要一并释放

	//析构  全部都清理,生命周期到了
	~list()
	{
		clear();
		delete _head;
		_head = nullptr;
	}

🌈拷贝构造

此处的浅拷贝会导致:

  • 二者修改的都是同一个链表的数据
  • 析构两次会崩溃的问题

在这里插入图片描述

所以我们要实现深拷贝—— ps:(this)的哨兵位不释放,已经换给lt2,tmp出作用域要释放

传统写法:利用范围for🍬尾插——

	list(const list<T>& lt)
	{
		 empty_init();
	     for(auto e : lt)
	     {
	     	push_back(e);
	     }
	}

现代写法

	//lt2(lt1)
	list(const list<T>& lt)
	{
		empty_init();
		list<T> tmp = (lt.begin(), lt.end());
		swap(tmp);
	}

也实现了swap函数

	void swap(list<T>& x)//这里的不是list<T>也可以,因为在这个类里面
	{
		std::swap(_head, x._head);
	}

🌈赋值重载

传统写法:

     //lt1 = lt3
    list<T>& operator=(const list<T>& lt)
    {
        if (this != &lt)
        {
            clear(); //清理lt1
            for (auto e : lt)
            {
                push_back(e);
            }
        }
        return *this;
    }

在这里插入图片描述

现代写法:(压榨思路)

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

🌈小细节

我们可以看见文档里面的list没有加类型

  • 在类的外面必须要有模板参数:list<T> , 类名不是类型,带模板参数才是类型
  • 类里面:可以用类名代表类型真心不建议

在这里插入图片描述

五. list & vector 区别和联系

【面试题】 list & vector的区别和联系

vector list
底层结构 动态顺序表,一段连续空间 带头结点的双向循环链表
随机访问 支持随机访问,访问某个元素效率O(1) 不支持随机访问,访问某个元素效率O(N)
插入删除 任意位置插入和删除效率低,需要搬移元素,时间复杂度为O(N),插入时有可能需要增容,增容(代价大):开辟新空间,拷贝元素,释放旧空间,导致效率更低, 任意位置插入和删除效率高,不需要搬移元素,时间复杂度为O(1)
空间利用率 底层为连续物理空间,不容易造成内存碎片,空间利用率高,缓存利用率高 底层节点动态开辟,小节点容易造成内存碎片,空间利用率低,缓存利用率低
迭代器 原生态指针 对原生态指针(节点指针)进行封装 重载*、++等操作符,让它像指针一样
迭代器失效 在插入元素时,要给所有的迭代器重新赋值,因为插入元素有可能会导致重新扩容,致使原来迭代器失效,删除时,当前迭代器需要重新赋值否则会失效 插入元素不会导致迭代器失效,删除元素时,只会导致当前迭代器失效,其他迭代器不受影响
使用场景 需要高效存储,支持随机访问,不关心插入删除效率 大量插入和删除操作,不关心随机访问

附源码

list.h

#pragma once
#include<iostream>

using namespace std;

namespace ljj
{
	template<class T>
	class list_node
	{
	public:
		friend class list<T>;

		T _data;
		list_node<T>* _next;
		list_node<T>* _prev;

		//构造
		list_node(const T& x = T())//全缺省 ~ 构造匿名对象
			:_data(x)
			,_next(nullptr)
			,_prev(nullptr)
		{}
	};
	 

	//  typedef __list_iterator<T, T&, T*>
	//  typedef __list_iterator<T, cosnt T&, const T*>


	template<class T, class Ref, class Ptr>//模板参数泛型化
	struct __list_iterator
	{
		typedef list_node<T> Node;
		typedef __list_iterator<T,Ref,Ptr> iterator;



		typedef bidirectional_iterator_tag iterator_category;
		typedef T value_type;
		typedef Ptr pointer;
		typedef Ref reference;
		typedef size_t size_type;
		typedef ptrdiff_t difference_type;

		Node* _node;//节点指针

		__list_iterator(Node* node)//提供一个节点构造
			:_node(node)
		{}

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

		bool operator==(const iterator& it) const
		{
			return _node == it._node;
		}
		
		//*it -> it.opeartor*()    可读可写
		//const T& operator*()    不能重载,因为返回值不同
		//T& operator*()
		Ref operator*()
		{
			return _node->_data;
		}

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

		//  ++it  返回值还是迭代器   日期类++返回的是日期类
		iterator& operator++()
		{
			_node = _node->_next;
			return *this;
		}

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

		//--it
		iterator& operator--()
		{
			_node = _node->_prev;
			return *this;
		}

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

	template<class T>
	class list
	{
		typedef list_node<T> Node;
	public:
		typedef __list_iterator<T, T&, T*> iterator;
		typedef __list_iterator<T, const T&, const T*> const_iterator;


		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()
		{
			//_head = new Node;
			//_head->_next = _head;
			//_head->_prev = _head;

			empty_init();
		}

		//拷贝构造
		//lt2(lt1)
		list(const list<T>& lt)
		{
			empty_init();
			list<T> tmp = (lt.begin(), lt.end());
			swap(tmp);
		}

		//赋值重载
		//lt1 = lt3
		list<T>& operator= (list<T> lt)
		{
			swap(tmp);
			return *this;
		}

		void swap(list<T>& x)//这里的不是list<T>也可以,因为在这个类里面
		{
			std::swap(_head, x._head);
		}

		void empty_init()
		{
			//创建并初始化哨兵位的头结点
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
		}

		//迭代器区间构造
		template <class InputIterator>
		list(InputIterator first, InputIterator last)
		{
			empty_init();
			while (first != last)
			{
				push_back(*first);//前提是已经构造了头结点
				++first;
			}
		}
		
		//析构  全部都清理,生命周期到了
		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
		}

		//clear 不清理头结点
		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);//注意要给给it ,因为erase后此结点失效,返回下一个节点的迭代器
			}
		}

		


		//尾插
		void push_back(const T& x)
		{
			//Node* tail = _head->_prev;
			//Node* newnode = new Node(x);

			_head      tail     newnode
			//tail->_next = newnode;
			//newnode->_prev = tail;
			//newnode->_next = _head;
			//_head->_prev = newnode;

			//复用insert
			insert(end(), x);
		}

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

		//插入
		iterator insert(iterator pos, const T& x)
		{
			Node* cur = pos._node;//迭代器是struct,就能访问其成员
			Node* prev = cur->_prev;

			Node* newnode = new Node(x);

			//prev   newnode   cur
			prev->_next = newnode;
			newnode->_prev = prev;
			newnode->_next = cur;
			cur->_prev = newnode;

			return iterator(newnode);//构造迭代器返回
		}


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

		//头删
		void pop_front()
		{
			erase(begin());
		}
		
		//删除
		iterator erase(iterator pos)
		{
			assert(pos != end());//哨兵位头结点不能删
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* next = cur->_next;
			//prev   cur   next

			prev->_next = next;
			next->_prev = prev;
			delete cur;

			return iterator(next);
		}

	private:
		Node* _head;
	};

	void test_list1()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);
		lt.push_back(5);

		//只能迭代器遍历
		list<int>::iterator it = lt.begin();
		while (it != lt.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;

		it = lt.begin();
		while (it != lt.end())
		{
			*it *= 2;
			++it;
		}
		cout << endl;
	}


	struct pos
	{
		int _a1;
		int _a2;

		pos(int a1 = 0 , int a2 = 0)
			:_a1(a1)
			,_a2(a2)
		{}
	};

	void test_list2()
	{
		int x = 10;
		int* p1 = &x;

		cout << *p1 << endl;


		pos aa;
		pos* p2 = &aa;
		p2->_a1;
		p2->_a2;//找结构体成员

		list<pos> lt;
		lt.push_back(pos(10, 20));
		lt.push_back(pos(20, 50));

		list<pos>::iterator it = lt.begin();
		while (it != lt.end())
		{
			//cout << (*it)._a1 << ":" << (*it)._a2 << endl;
			cout << it->_a1 << ":" << it->_a2 << endl;

			++it;
		}
		cout<< endl;
	}


	void test_list3()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);
		lt.push_back(5);

		list<int> copy = lt;
		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;
	}
}

📢写在最后

不上课被辅导员抓去谈话了
在这里插入图片描述

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注