当前位置： 首页 > article >正文

C++List模拟实现|细节|难点|易错点|全面解析|类型转换|

article 2025/3/30 17:58:38

目录

1.模拟代码全部

2.四大块代码理解

1.最底层：ListNode部分

2.第二层：ListIterator部分

3.第三层：ReserveListIterator部分

 4最终层：List

1.模拟代码全部

using namespace std;
template<class T>
struct ListNode
{
	T _Val;
	ListNode<T>* Prev;
	ListNode<T>* Next;
	ListNode(T Val=T())
	{
		Prev = nullptr;
		Next = nullptr;
		_Val = Val;
	}
};
template<class T, class Ref, class Ptr>
class ListIterator
{
public:
	typedef ListNode<T> Node;
	typedef ListIterator<T, Ref, Ptr> Self;
	typedef Ref Ref;
	typedef Ptr Ptr;
	ListIterator(Node* _NODE = nullptr) :_node(_NODE)
	{
	}
	Ptr operator->()
	{
		return &(operator*());
	}
	Ref operator*()
	{
		return _node->_Val;
	}
	Self& operator++()
	{
		_node = _node->Next;
		return *this;
	}
	Self operator++(int)
	{
		Node* Newnode = _node;
		_node = _node->Next;
		return Newnode;
	}
	Self& operator--()
	{
		_node = _node->Prev;
		return *this;
	}
	Self operator--(int)
	{
		Node* Newnode = _node;
		_node = _node->Prev;
		return Newnode;
	}
	bool operator==(const Self& I) const
	{
		if (I._node == _node)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	bool operator!=(const Self& I)const
	{
		if (I._node != _node)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	Node* _node;
};
template<class Iterator>
class ReserveListIterator
{
public:
	typedef typename Iterator::Ptr Ptr;
	typedef typename Iterator::Ref Ref;
	typedef ReserveListIterator<Iterator> Self;
	ReserveListIterator(Iterator it):_it(it)
	{}
	Ref operator*()
	{
		Iterator temp(_it);
		temp--;
		return *temp;
	}
	Ptr operator->()
	{
		return &(operator*());
	}
	Self operator++()
	{
		_it++;
		return *this;
	}
	Self operator++(int)
	{
		Iterator temp(_it);
		_it++;
		return *temp;
	}
	Self operator--()
	{
		_it--;
		return *this;
	}
	Self operator--(int)
	{
		Iterator temp(_it);
		_it--;
		return *temp;
	}
	bool operator == (const Self & I) const
	{
		if (I._it==_it)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	bool operator !=(const Self& I)const
	{
		if (I._it != _it)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	Iterator _it;
};
template<class T>
class List
{
	typedef ListNode<T> Node;
	typedef ListIterator<T, T&, T*> iterator;
	typedef ListIterator<T, const T&, const T*> const_iterator;
	typedef ReserveListIterator<iterator> reverse_iterator;
	typedef ReserveListIterator<const_iterator> const_reverse_iterator;
public:
	List()
	{
		creathead();
	}
	List(int n,const T& Value=T())
	{
		creathead();
		for (int i = 0; i < n; i++)
		{
			push_back(Value);
		}
	}
	template <class Iterator>
	List(Iterator first, Iterator last)
	{
		creathead();
		while (first != last)
		{
			push_back(*first);
			first++;
		}
	}
	List(const List<T>& l)
	{
		creathead();
		List<T>temp(l.begin(), l.end());
		this->swap(temp);
	}
	List<T>& operator=(List<T> l)
	{
		List<T>temp(l);
		this->swap(temp);
		return *this;
	}
	~List()
	{
		clear();
		delete _head;
		_head = nullptr;
	}
	iterator begin()
	{
		return _head->Next;
	}
	iterator end()
	{
		return _head;
	}
	const_iterator begin()const
	{
		return _head->Next;
	}
	const_iterator end()const
	{
		return _head;
	}
	reverse_iterator rbegin()
	{
		return reverse_iterator(begin());
	}
	reverse_iterator rend()
	{
		return reverse_iterator(end());
	}
	const_reverse_iterator rbegin()const
	{
		return const_reverse_iterator(begin());
	}
	const_reverse_iterator rend()const
	{
		return const_reverse_iterator(end());
	}
	size_t size()const
	{
		size_t num = 0;
		Node* CUR = _head->Next;
		while (CUR != _head)
		{
			num++;
			CUR = CUR->Next;
		}
		return num;
	}
	bool empty()const
	{
		if (begin() == end())
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	void resize(size_t newsize, const T& data = T())
	{
		if (newsize > size())
		{
			Node* it = end();
			it = it->Prev;
			for (size_t i = size(); i < newsize; i++)
			{
				Node* cur = new Node(data);
				cur->Next = it->Next;
				cur->Prev = it;
				it->Next = cur;
			}
		}
		else
		{
			Node* it = end();
			size_t len = size() - newsize;
			while (len--)
			{
				Node* cur = it;
				it = it->Prev;
				delete cur;
			}
			it->Next = _head;
			_head->Prev = it;
		}
	}
	T& front()
	{
		return *begin();
	}
	const T& front()const
	{
		return *begin();
	}
	T& back()
	{
		iterator it = end();
		it--;
		return *it;
	}
	const T& back()const
	{
		iterator it = end();
		it--;
		return *it;
	}
	void push_back(const T& val)
	{
		Node* Newnode = new Node(val);
		Node* cur = _head->Prev;
		cur->Next = Newnode;
		_head->Prev = Newnode;
		Newnode->Next = _head;
		Newnode->Prev = cur;
	}

	void pop_back()
	{
		Node* cur = _head->Prev->Prev;
		Node* popnode = _head->Prev;
		cur->Next = _head;
		_head->Prev = cur;
		delete popnode;
	}
	void push_front(const T& val)
	{
		Node* cur = _head->Next;
		Node* newnode = new Node(val);
		_head->Next = newnode;
		cur->Prev = newnode;
		newnode->Next = cur;
		newnode->Prev = _head;
	}
	void pop_front()
	{
		Node* cur = _head->Next->Next;
		Node* popnode = _head->Next;
		_head->Next = cur;
		cur->Prev = _head;
		delete popnode;
	}
	iterator insert(iterator pos, const T& val)
	{
		Node* pre = pos._node->Prev;
		Node* nect = pos._node;
		Node* newnode = new Node(val);
		newnode->Prev = pre;
		newnode->Next = nect;
		pre->Next = newnode;
		nect->Prev = newnode;
		return newnode;
	}
	iterator erase(iterator pos)
	{
		Node* cur = pos._node;
		Node* prev = cur->Prev;
		Node* next = cur->Next;
		delete cur;
		prev->Next = next;
		next->Prev = prev;
		return next;
	}
	void clear()
	{
		size_t sz = this->size();
		while (sz--)
		{
			Node* cur = _head->Next;
			Node* pop;
		}
	}
	void swap(List<T>& l)
	{
		Node* temp = l._head;
		l._head = _head;
		_head = temp;
	}
	void creathead()
	{
		_head = new Node(0);
		_head->Prev = _head;
		_head->Next = _head;
	}
private:
	Node* _head;
};

2.四大块代码理解

代码一共分为四块,我们分开来理解

1.最底层：ListNode部分

这里是最简单的部分，小伙伴们应该都看的懂吧

using namespace std;
template<class T>
struct ListNode
{
	T _Val;
	ListNode<T>* Prev;
	ListNode<T>* Next;
	ListNode(T Val=T())
	{
		Prev = nullptr;
		Next = nullptr;
		_Val = Val;
	}
};

 这里我们形象点记忆

其实应该不用赘述多了,基础好的同学看到这张图应该就差不多懂了。 

唯一要注意的是

T Val=T()

>>    T()表示对类型T进行值初始化,生成一个临时的右值

>>    如果T是内置类型(如int,double,char等),则T()会执行零初始化,即返回0,0.0或'\0'等默认值。

>>    如果T是类类型,则T()会调用默认构造函数(如果存在)

聪明的小伙伴已经理解清楚了

2.第二层：ListIterator部分

聪明的小伙伴应该看代码就能懂了

那么我在这下方陈述了一些难点和易错点 

template<class T, class Ref, class Ptr>
class ListIterator
{
public:
	typedef ListNode<T> Node;
	typedef ListIterator<T, Ref, Ptr> Self;
	typedef Ref Ref;
	typedef Ptr Ptr;
	ListIterator(Node* _NODE = nullptr) :_node(_NODE)
	{
	}
	Ref operator*()
	{
		return _node->_Val;
	}
	Self& operator++()
	{
		_node = _node->Next;
		return *this;
	}
	Self operator++(int)
	{
		Node* Newnode = _node;
		_node = _node->Next;
		return Newnode;
	}
	Self& operator--()
	{
		_node = _node->Prev;
		return *this;
	}
	Self operator--(int)
	{
		Node* Newnode = _node;
		_node = _node->Prev;
		return Newnode;
	}
	bool operator==(const Self& I) const
	{
		if (I._node == _node)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	bool operator!=(const Self& I)const
	{
		if (I._node != _node)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	Node* _node;
};

聪明的小伙伴应该看代码就能懂了

那么我在这陈述一下一些难点和易错点 

>>    typedef Ref Ref和typedef Ptr Ptr，简单来说，我们需要让编译器知道Listiterator里面有Ptr和 Ref，后面的反向迭代器ReserveListIterator来使用Listiterator的Ref和Ptr

>>    Ref：Ref在后面我们会通过T&来填充这块模板，也就是说Ref就是引用

>>    Ptr：Ptr在后面我们会通过T*来填充这块模板，也就是说Ptr就是指针

3.第三层：ReserveListIterator部分

聪明的小伙伴直接看代码

template<class Iterator>
class ReserveListIterator
{
public:
	typedef typename Iterator::Ptr Ptr;
	typedef typename Iterator::Ref Ref;
	typedef ReserveListIterator<Iterator> Self;
	ReserveListIterator(Iterator it):_it(it)
	{}
	Ref operator*()
	{
		Iterator temp(_it);
		temp--;
		return *temp;
	}
	Ptr operator->()
	{
		return &(operator*());
	}
	Self operator++()
	{
		_it++;
		return *this;
	}
	Self operator++(int)
	{
		Iterator temp(_it);
		_it++;
		return *temp;
	}
	Self operator--()
	{
		_it--;
		return *this;
	}
	Self operator--(int)
	{
		Iterator temp(_it);
		_it--;
		return *temp;
	}
	bool operator == (const Self & I) const
	{
		if (I._it==_it)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	bool operator !=(const Self& I)const
	{
		if (I._it != _it)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	Iterator _it;
};

 

>>    之前我们在ListIterator里重新定义了Ptr和Ref参数就是留在ReserveListIterator使用

 

这里要注意一定不要写成Iterator &，本人之前就因为这个错误导致费了1小时/(ㄒoㄒ)/~~ 

 4最终层：List

牛人已经看代码就懂了

template<class T>
class List
{
	typedef ListNode<T> Node;
	typedef ListIterator<T, T&, T*> iterator;
	typedef ListIterator<T, const T&, const T*> const_iterator;
	typedef ReserveListIterator<iterator> reverse_iterator;
	typedef ReserveListIterator<const_iterator> const_reverse_iterator;
public:
	List()
	{
		creathead();
	}
	List(int n,const T& Value=T())
	{
		creathead();
		for (int i = 0; i < n; i++)
		{
			push_back(Value);
		}
	}
	template <class Iterator>
	List(Iterator first, Iterator last)
	{
		creathead();
		while (first != last)
		{
			push_back(*first);
			first++;
		}
	}
	List(const List<T>& l)
	{
		creathead();
		List<T>temp(l.begin(), l.end());
		this->swap(temp);
	}
	List<T>& operator=(List<T> l)
	{
		List<T>temp(l);
		this->swap(temp);
		return *this;
	}
	~List()
	{
		clear();
		delete _head;
		_head = nullptr;
	}
	iterator begin()
	{
		return _head->Next;
	}
	iterator end()
	{
		return _head;
	}
	const_iterator begin()const
	{
		return _head->Next;
	}
	const_iterator end()const
	{
		return _head;
	}
	reverse_iterator rbegin()
	{
		return reverse_iterator(begin());
	}
	reverse_iterator rend()
	{
		return reverse_iterator(end());
	}
	const_reverse_iterator rbegin()const
	{
		return const_reverse_iterator(begin());
	}
	const_reverse_iterator rend()const
	{
		return const_reverse_iterator(end());
	}
	size_t size()const
	{
		size_t num = 0;
		Node* CUR = _head->Next;
		while (CUR != _head)
		{
			num++;
			CUR = CUR->Next;
		}
		return num;
	}
	bool empty()const
	{
		if (begin() == end())
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	void resize(size_t newsize, const T& data = T())
	{
		if (newsize > size())
		{
			Node* it = end();
			it = it->Prev;
			for (size_t i = size(); i < newsize; i++)
			{
				Node* cur = new Node(data);
				cur->Next = it->Next;
				cur->Prev = it;
				it->Next = cur;
			}
		}
		else
		{
			Node* it = end();
			size_t len = size() - newsize;
			while (len--)
			{
				Node* cur = it;
				it = it->Prev;
				delete cur;
			}
			it->Next = _head;
			_head->Prev = it;
		}
	}
	T& front()
	{
		return *begin();
	}
	const T& front()const
	{
		return *begin();
	}
	T& back()
	{
		iterator it = end();
		it--;
		return *it;
	}
	const T& back()const
	{
		iterator it = end();
		it--;
		return *it;
	}
	void push_back(const T& val)
	{
		Node* Newnode = new Node(val);
		Node* cur = _head->Prev;
		cur->Next = Newnode;
		_head->Prev = Newnode;
		Newnode->Next = _head;
		Newnode->Prev = cur;
	}

	void pop_back()
	{
		Node* cur = _head->Prev->Prev;
		Node* popnode = _head->Prev;
		cur->Next = _head;
		_head->Prev = cur;
		delete popnode;
	}
	void push_front(const T& val)
	{
		Node* cur = _head->Next;
		Node* newnode = new Node(val);
		_head->Next = newnode;
		cur->Prev = newnode;
		newnode->Next = cur;
		newnode->Prev = _head;
	}
	void pop_front()
	{
		Node* cur = _head->Next->Next;
		Node* popnode = _head->Next;
		_head->Next = cur;
		cur->Prev = _head;
		delete popnode;
	}
	iterator insert(iterator pos, const T& val)
	{
		Node* pre = pos._node->Prev;
		Node* nect = pos._node;
		Node* newnode = new Node(val);
		newnode->Prev = pre;
		newnode->Next = nect;
		pre->Next = newnode;
		nect->Prev = newnode;
		return newnode;
	}
	iterator erase(iterator pos)
	{
		Node* cur = pos._node;
		Node* prev = cur->Prev;
		Node* next = cur->Next;
		delete cur;
		prev->Next = next;
		next->Prev = prev;
		return next;
	}
	void clear()
	{
		size_t sz = this->size();
		while (sz--)
		{
			Node* cur = _head->Next;
			Node* pop;
		}
	}
	void swap(List<T>& l)
	{
		Node* temp = l._head;
		l._head = _head;
		_head = temp;
	}
	void creathead()
	{
		_head = new Node(0);
		_head->Prev = _head;
		_head->Next = _head;
	}
private:
	Node* _head;
};

 这里要注意一下转换顺序,listnode不能直接转换为reverse_iterator 

listnode转换为reverse_iterator需要两个个过程

 

 易错点难点就是以上那么多了，说多了只会妨碍小伙伴们，通过自己学习效率才是最高的。

3.测试代码 

#include"LList.h"
#include<iostream>
void ListPrint(List<int> it)
{
	auto i = it.begin();
	while(i!=it.end())
	{
		cout << *i << " ";
		i++;
	}
}
void TestBiteList1()
{
	int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
	List<int> l3(array, array + sizeof(array) / sizeof(array[0]));
	ListPrint(l3);
	ListIterator<int, int&, int*> it(l3.begin());

}
void TestBiteList2()
{
	List<int> l;
	l.push_back(1);
	l.push_back(2);
	l.push_back(3);
	ListPrint(l);

	l.pop_back();
	l.pop_back();
	ListPrint(l);

	l.pop_back();
	cout << l.size() << endl;

	l.push_front(1);
	l.push_front(2);
	l.push_front(3);
	ListPrint(l);

	l.pop_front();
	l.pop_front();
	ListPrint(l);

	l.pop_front();
	cout << l.size() << endl;
}
void TestBiteList3()
{
	int array[] = { 1, 2, 3, 4, 5 };
	List<int> l(array, array + sizeof(array) / sizeof(array[0]));
	auto pos = l.begin();
	l.insert(l.begin(), 0);
	ListPrint(l);
	++pos;
	l.insert(pos, 2);
	ListPrint(l);
	l.erase(l.begin());
	l.erase(pos);
	ListPrint(l);
	cout << *pos << endl;
	auto it = l.begin();
	while (it != l.end())
	{
		it = l.erase(it);
	}
	cout << l.size() << endl;
}
void TestBiteList4()
{
	int array[] = { 1, 2, 3, 4, 5 };
	List<int> l(array, array + sizeof(array) / sizeof(array[0]));

	auto rit = l.rbegin();
	while (rit != l.rend())
	{
		cout << *rit << " ";
		++rit;
	}
	cout << endl;

	const List<int> cl(l);
	auto crit = l.rbegin();
	while (crit != l.rend())
	{
		cout << *crit << " ";
		++crit;
	}
	cout << endl;
}
int main()
{
	TestBiteList1();
	TestBiteList2();
	TestBiteList3();
	TestBiteList4();
}


http://www.kler.cn/a/612209.html

相关文章：

  • ngx_http_index_t
  • Java 大视界 -- Java 大数据在智能政务公共服务资源优化配置中的应用（118）
  • 如何用 Postman 正确传递 Date 类型参数，避免服务器解析错误？
  • 什么是泛目录站群？怎么做好无极泛目录站群
  • Scala总结（一）
  • [计算机网络]网络I/O模型
  • Qt在模块依靠情况下资源文件名称和资源名称的使用限制
  • HTML 与 JavaScript 交互：学习进程中的新跨越（一）
  • 2025选择手机之我见
  • 抽象工厂设计模式及应用案例
  • 【MySQL】MySQL结构体系及核心组件功能是怎样的？
  • stm32week8
  • gogs私服搭建
  • 代码随想录算法训练营Day12 | Leetcode 226翻转二叉树、101对称二叉树、104二叉树的最大深度、111二叉树的最小深度
  • Eclipse IDE for ModusToolbox™ 3.4环境通过JLINK调试CYT4BB
  • 【408--复习笔记】数据结构
  • LeetCode19删除链表的倒数第N个结点
  • 单片机内存划分总览与介绍
  • 《Python实战进阶》No34：卷积神经网络（CNN）图像分类实战
  • 【C++】httplib：轻量级的 HTTP 服务器和客户端