• 【C++】STL——list模拟实现

    目录

    实现思路

    一、list的节点设计 

    二、list的初步框架 

    三、list的正向迭代器设计

    1.实现原理 

    2. 正向迭代器的结构

    四、list反向迭代器的设计

    1.实现原理

    2.反向迭代器的结构 

    1.反向迭代器的 ++ / -- 操作解析

    2.反向迭代器的 * / -> 操作解析

    五、list结构的完善 

    1.构造函数

    2.拷贝构造

    3.迭代器区间构造

    4.用n个val构造

    5.赋值重载

    6.析构函数

    7.迭代器的实现

    8.增删查改

    六、完整代码

    1.ListNode.h

    2.iterator.h

    3.reverse_iterator.h 

    4.list.h

    实现思路

            List是一个类模板，实际上是一个双向循环链表。在上一篇list基本使用的博客中，可以发现list支持了像vector一样的"下标访问"，也就是通过迭代器区间去访问链表的每个节点数据。本人在初学阶段也是比较好奇——list的迭代器（正向与反向）是如何实现的；本篇博客将以自己所掌握的知识，详细的介绍list是如何实现的。

    list实现结构：

            1.节点设计

            2.正向迭代器设计

            3.反向迭代器设计

            4.list各个接口完善（增删查改）

    一、list的节点设计 

    list本身和list的结点是两个不同的结构，需要分开设计。以下是list的节点结构： 

    1. /*ListNode.h*/
    2. namespace mlg
    3. {
    4. 	template<class T>
    5. 	struct ListNode
    6. 	{
    7. 		ListNode<T>* _prev; //节点的前指针
    8. 		ListNode<T>* _next; //节点的后指针
    9. 		T _data;            //节点的数据
    10.  
    11. 		ListNode(const T& data= T())//初始化列表进行初始化
    12. 			:_prev(nullptr)
    13. 			,_next(nullptr)
    14. 			,_data(data)
    15. 		{}
    16. 		
    17. 	};
    18. }

            首先，我们在自己的命名空间内模拟实现list（为了防止与库冲突），上面的代码就是list节点的结构。在这里是用并没有使用class，因为struct默认访问权限是public，又因为节点是需要经常访问的，所以使用struct更好。

            我们将这个类加上 template<class T> 后，就能够实现节点存储不同类型的数据，这也是C++模板的好处。

    二、list的初步框架 

            当我们设计好了list的结点以后，我们就需要对list的基本框架进行设计，list要能够去控制这些节点，它的成员变量就必须是这个节点类；以下是list的结构设计：

    1. /*List.h*/
    2. namespace mlg //命名空间保持一致
    3. {
    4. 	template<class T> //list是一个类模板，设计时需要这个
    5. 	class list
    6. 	{
    7. 		typedef ListNode<T> Node; //将其类型重命名方便书写，在后续的类型中会有比较多的typedef
    8. 	public：
    9.  
    10. 	    /*
    11.         成员函数包含了默认成员函数、迭代器和增删查改
    12.         */
    13.  
    14. 	private:
    15. 		Node* _head; //带头结点的双向循环链表
    16. 	};
    17. }

    在以上两个基本的框架搭建完毕以后，接下来重点主要是正向与反向迭代器

    三、list的正向迭代器设计

    1.实现原理 

            list的确是支持了迭代器，但是list不在能够像vector一样以普通的指针作为迭代器，因为其节点不保证在存储空间中连续。list的迭代器必须有能力指向list的节点，并有能力进行递增、递减、取值、成员存储等操作。如何具备这样的能力呢？那就是递增时指向下一个结点，递减时指向上一个节点，取值时取的是节点的数据值，成员取用时取用的是节点的成员；

    2. 正向迭代器的结构

    1. /*iterator.h*/
    2.  
    3. namespace mlg
    4. {
    5. 	template<class T,class Ref,class Ptr>
    6. 	struct __list_iterator
    7. 	{
    8. 		typedef ListNode<T> Node;
    9. 		typedef __list_iterator<T, Ref, Ptr> self;
    10. 		Node* _node;
    11.         
    12.         //迭代器构造函数
    13. 		__list_iterator(Node* x)
    14. 			:_node(x)
    15. 		{}
    16.  
    17.         //重载*号 —— 实现解引用操作
    18. 		Ref operator*()
    19. 		{
    20. 			return _node->_data;
    21. 		}
    22.  
    23.         //重载->操作符 —— 实现指针访问元素
    24. 		Ptr operator->()
    25. 		{
    26. 			return &_node->_data;
    27. 		}
    28.  
    29. 		//++it 重载前置++ —— 让链表能够像数组一样去++操作，访问元素
    30. 		self& operator++()
    31. 		{
    32. 			_node = _node->_next;//前置++返回的是++之后的值，直接让当前位置的结点指向下一个节点
    33. 			return *this;
    34. 		}
    35.  
    36. 		//it++ 重载后置++ —— （这里需要加上int作为一个站位符，与前置++区分）
    37. 		self operator++(int)
    38. 		{
    39. 			self tmp(*this);
    40. 			_node = _node->_next;//后置++返回的是++之前的值，需要保存当前节点，再指向下一个节点
    41. 			return tmp;
    42. 		}
    43.  
    44. 		//--it 重载前置-- —— 让链表能够像数组一样去--操作，访问元素
    45. 		self& operator--()
    46. 		{
    47. 			_node = _node->_prev;//前置--返回的是--之后的值，直接让当前位置的结点指向前一个节点
    48. 			return *this;
    49. 		}
    50.  
    51. 		//it-- 重载后置-- ——（这里需要加上int作为一个站位符，与前置--区分）
    52. 		self operator--(int)
    53. 		{
    54. 			self tmp(*this);
    55. 			_node = _node->_prev;//后置--返回的是--之前的值，需要保存当前节点，再指向下一个节点
    56. 			return tmp;
    57. 		}
    58.  
    59.         //重载==
    60. 		bool operator==(const self& it)const
    61. 		{
    62. 			return _node == it._node;
    63. 		}
    64.  
    65.         //重载!=
    66. 		bool operator!=(const self& it)const
    67. 		{
    68. 			return _node != it._node;
    69. 		}
    70. 	
    71. 	};
    72. }

    在上述代码中，有三个地方没有做解释：

    1. template<class T,class Ref,class Ptr>

    2. typedef __list_iterator<T, Ref, Ref>  self;

            它是迭代器类模板，里面包含了三个参数：T、Ref、Ptr；这三个参数表明传给iterator类的类型是不确定的，需要根据实际的情况，将这三个参数匹配到相应的地方。

    如：

            1. ++/--操作：返回的是一个对象，只要用到了对象，一般都是写成__list_iterator<T, Ref, Ref>，因为类名太长，就有了第2点的typedef __list_iterator<T, Ref, Ref>  self;

            2. operator* 操作：返回的是对象的数据的值，并且*号是具有读写操作的，我们应该返回的是这个数据类型的引用（T&）；

            3. operator->操作：返回的是对象的数据的地址，我们应该返回的是这个数据类型的地址（T*）；

    --------------------------------------------------------------------------------------------------------------------------

    3. typedef ListNode<T> Node;
        Node* _node;

            iterator类中的成员变量也是节点，我们刚刚已经解释了list迭代器的原理，它是通过重载++ / --,其内部实现上是节点中的_prev指针（找当前节点的前一个位置，相当于--操作）和_next指针（找当前节点的下一个位置，相当于++操作）的操作来实现的；

            所以，list正向迭代器的实现，本质上是用节点的两个指针的操作来代替了传统的++/--操作。再简单点说，其实就是函数调用（包括*/->）

    四、list反向迭代器的设计

    1.实现原理

            我们刚刚对list正向迭代器做了介绍以后，你是否会想，反向迭代器也是同样的原理呢？确实可以这样理解，但是中间还有一个过程，我们先通下面的图解了解一下双链表（list）中和数组（vector）中正向迭代器与反向迭代器的区别。

    vector迭代器的位置不需要多说，对于list的迭代器：begin( )是数据的起始位置，end( )是数据的结束位置，也就是头结点；反向迭代器不就是与之相反嘛。

    那如何才能通过反向迭代器控制链表的++/--等一系列操作呢？

            方法一：我们可以重新写一个，也通过节点的指针去控制（比较麻烦：如果我想用正向迭代器区获取某个节点的位置传个反向迭代器，就需要给反向迭代器增设正向迭代器的接口）

            方法二：反向迭代器通过正向迭代器去间接控制list节点，达到想要的效果（在SLT原码中是这样子实现的，其目的是能适应其他容器，其称之为迭代器适配器）

    2.反向迭代器的结构 

    1. /*reverse_iterator.h*/
    2. namespace mlg
    3. {
    4. 	template<class Iterator,class Ref,class Ptr>
    5. 	class __list_reverse_iterator
    6. 	{
    7. 		typedef __list_reverse_iterator<Iterator, Ref, Ptr> self;
    8. 	public:
    9.         //反向迭代器构造函数（通过正向迭代器去构出造反向迭代器）
    10. 		__list_reverse_iterator(Iterator it)
    11. 			:_it(it)
    12. 		{}
    13.  
    14.         //重载* 
    15. 		Ref operator*()
    16. 		{
    17. 			Iterator prev = _it; //获取正向迭代器end()的位置
    18. 			return *--prev;      //返回的是当前位置执行前置--操作后的解引用
    19. 		}
    20.  
    21.         //重载->
    22. 		Ptr operator->()
    23. 		{
    24. 			return &operator*(); //调用上面一个重载函数
    25. 		}
    26.  
    27. 		//++it
    28. 		self& operator++()
    29. 		{
    30. 			--_it;        //反向迭代器的前置++就是调用正向迭代器的前置--
    31. 			return *this; //
    32. 		}
    33.  
    34. 		//it++
    35. 		self operator++(int)
    36. 		{
    37. 			self tmp(*this); //后置++返回的是++之前的，所有先记录当前正向迭代器的位置
    38. 			_it--;           //反向迭代器的后置++就是调用正向迭代器的后置--
    39. 			return tmp;
    40. 		}
    41.  
    42. 		//--it
    43. 		self& operator--()
    44. 		{
    45. 			++_it;        //反向迭代器的前置--就是调用正向迭代器的前置++
    46. 			return *this;
    47. 		}
    48.  
    49. 		//it--
    50. 		self operator--(int)
    51. 		{
    52. 			self tmp(*this); //后置--返回的是--之前的，所有先记录当前正向迭代器的位置
    53. 			_it++;           //反向迭代器的后置--就是调用正向迭代器的后置++
    54. 			return tmp;
    55. 		}
    56.  
    57.         //重载!=
    58. 		bool operator!=(const self& rit)const
    59. 		{
    60. 			return _it != rit._it;
    61. 		}
    62.  
    63.         //重载==
    64. 		bool operator==(const self& rit)const
    65. 		{
    66. 			return _it == rit._it;
    67. 		}
    68.  
    69. 	private:
    70. 		Iterator _it;//成员变量是一个正向迭代器
    71. 	};
    72. }

    1.反向迭代器的 ++ / -- 操作解析

    1. //++it
    2. self& operator++()
    3. {
    4. 	--_it;           //调用正向迭代器的前置--
    5. 	return *this;
    6. }
    7.  
    8. //it++
    9. self operator++(int)
    10. {
    11. 	self tmp(*this);
    12. 	_it--;           //调用正向迭代器的后置--
    13. 	return tmp;
    14. }

      

    通过上图可以发现：

    1.反向迭代器++（前置/后置）：调用正向迭代器的--

    2.反向迭代器--（前置/后置）：调用正向迭代器的++

    2.反向迭代器的 * / -> 操作解析

    1. //重载* 
    2. Ref operator*()
    3. {
    4. 	Iterator prev = _it; //获取正向迭代器end()的位置
    5. 	return *--prev;      //返回的是当前位置执行前置--操作后的解引用
    6. }
    7.  
    8. //重载->
    9. Ptr operator->()
    10. {
    11. 	return &operator*(); //调用上面一个重载函数
    12. }

    对于->的重载，只要去复用就可以了。 

    五、list结构的完善 

            上面我们对节点结构、正向与反向迭代器结构实现原理及注意点一一做了介绍，最后一步也是最重要的一步，那就是将list结构完善起来，实现list的功能。

    1.构造函数

            list的成员变量是一个节点类，在构造头节点时，需要将这单个头节点构造成一个双向循环链表；

     

    1. //构造函数
    2. list()
    3. {
    4. 	_head = new Node;     //new一个节点出来
    5. 	_head->_prev = _head; 
    6. 	_head->_next = _head; //_prev 和 _next 同时指向了头结点，形成了双向循链表
    7. }

    2.拷贝构造

            拷贝构造是用一个已有对象去构造出另一个对象，首先将待构造对象进行初始化，然后利用迭代器区间去构造一个和lt1一样的临时的tmp对象，再进行数据的交换，达到深拷贝的目的。 

    1. //拷贝构造 --- 现代写法 lt2(lt1)
    2. list(const list<T>& lt)
    3. {
    4. 	_head = new Node;
    5. 	_head->_prev = _head;
    6. 	_head->_next = _head;
    7. 	list<T> tmp(lt.begin(), lt.end());
    8. 	std::swap(_head, tmp._head);
    9. }

    3.迭代器区间构造

    通过传过来的迭代器区间进行初始化 

    1. //迭代器区间构造
    2. template<class IputIterator>
    3. list(IputIterator first, IputIterator last)
    4. {
    5. 	_head = new Node;
    6. 	_head->_prev = _head;
    7. 	_head->_next = _head;
    8.  
    9. 	while (first != last)
    10. 	{
    11. 		push_back(*first);//尾插数据，会根据不同类型的迭代器进行调用
    12. 		++first;
    13. 	}
    14. }

    4.用n个val构造

            通过用n个val来对对象进行初始化，需要注意这里的T( )是一个匿名对象，作为val的缺省参数，因为我们并不知道传给val的是一个对象还是一个整形（或其他），给缺省参数的好处在于，对于自定义类型编译器会去调用自定义类型的构造函数来对val进行初始化，如果是内置类型，它也是有自己的构造函数

    1. //我们常常对内置类型的定义是这样的
    2. int i = 10;
    3.  
    4. //但其实也可以这样定义
    5. int i = int(10);
    1. //用n个val个构造      			   
    2. list(int n, const T& val = T())        			   
    3. {												   
    4. 	_head = new Node;
    5. 	_head->_prev = _head;
    6. 	_head->_next = _head;
    7. 	for (int i = 0; i < n; i++)
    8. 	{
    9. 		push_back(val);
    10. 	}
    11. }

    对于用n个val进行初始化和迭代器区间初始化，起初我是这样写的（为了和库一致） ，测试时却出现问题：非法的间接寻址

    1. //迭代器区间初始化
    2. template<class IputIterator>
    3. list(IputIterator first, IputIterator last){...}
    4.  
    5. //用n个val初始化
    6. list(size_t n, const T& val = T()) {...}   
    7.  
    8.  
    9. //测试日期类
    10. struct Date
    11. {
    12. 	int _year;
    13. 	int _month;
    14. 	int _day;
    15. 	Date(int year = 1, int month = 1, int day = 1)
    16. 		:_year(year)
    17. 		, _month(month)
    18. 		, _day(day)
    19. 	{}
    20. };
    21.  
    22. void test_list4()
    23. {
    24. 	list<Date> lt1(5, Date(2022, 6, 21));//1
    25. 	for (auto e : lt1)
    26. 	{
    27. 		cout << e._year << "/" << e._month << "/" << e._day << endl;
    28. 	}
    29. 	cout << endl;
    30.  
    31. 	list<int> lt2(5, 1);//2
    32. 	for (auto e : lt2)
    33. 	{
    34. 		cout << e << " ";
    35. 	}
    36. 	cout << endl;
    37. }

    5.赋值重载

    1. //赋值重载 --- 现代写法 lt2 = lt1
    2. list<T>& operator=(list<T> lt)
    3. {
    4. 	std::swap(_head, lt._head);
    5. 	return *this;
    6. }

    6.析构函数

    析构函数可以结合着erase函数看 

    1. ~list()
    2. {
    3. 	clear();
    4. 	delete _head;
    5. 	_head = nullptr;
    6. }
    7.  
    8. void clear()
    9. {
    10. 	iterator it = begin();
    11. 	while (it != end())
    12. 	{
    13. 		//写法1
    14. 		erase(it++); //it是一个正向迭代器，采用后置++传给erase
    15. 		//写法2
    16. 		iterator del = it++;
    17. 		delete del._node;
    18. 		//写法3
    19. 		iterator del = it++;
    20. 		erase(del);
    21. 	}
    22. 	_head->_prev = _head;
    23. 	_head->_next = _head;
    24. }

    7.迭代器的实现

    在list类中，我们typedef了正向与反向迭代器，解释一下其目的及作用

    //正向迭代器    

    1. typedef __list_iterator<T, T&, T*> iterator;
    2. typedef __list_iterator<T, const T&, const T*> const_iterator;

    //反向迭代器

    1. typedef __list_reverse_iterator<iterator, T&, T*> reverse_iterator;
    2. typedef __list_reverse_iterator<iterator, const T&, const T*>const_reverse_iterator;

            list是一个类模板，参数列表是T类型（未知类型）正向与反向迭代器分别都有三个参数，在list内重命名相当于内嵌定义，显示传参，我们对迭代器中需要返回值的地方不能进行类型的准确判断，通过这种显示传参，确定了迭代器三个参数的基本对于类型。

            对于正向迭代器，我们显示传参<T、T&、T*>如果是const迭代器，再重新typedef一个const迭代器；

            对于反向迭代器，我们是需要正向迭代器去构造，所有显示传参就可以给到<iterator, T&, T*>

    1. namespace mlg
    2. {
    3.     template<class T>
    4.     class list
    5.     {
    6. 	    typedef ListNode<T> Node;
    7.     public:
    8.         //正向迭代器
    9.         typedef __list_iterator<T, T&, T*> iterator;
    10.         typedef __list_iterator<T, const T&, const T*> const_iterator;
    11.         iterator begin()
    12.         {
    13.         	return iterator(_head->_next);//返回头节点的下一个结点
    14.         }
    15.  
    16.         iterator end()
    17.         {
    18.         	return iterator(_head);//返回头节点
    19.         }
    20.  
    21.         const_iterator begin()const
    22.         {
    23. 	        return const_iterator(_head->_next);//返回头节点的下一个结点
    24.         }
    25.  
    26.         const_iterator end()const
    27.         {
    28.         	return const_iterator(_head);//返回头节点
    29.         }
    30.  
    31.         //反向迭代器
    32.         typedef __list_reverse_iterator<iterator, T&, T*> reverse_iterator;
    33.         typedef __list_reverse_iterator<iterator, const T&, const T*>const_reverse_iterator;
    34.  
    35.         reverse_iterator rbegin()
    36.         {
    37.         	return reverse_iterator(end());   //返回正向迭代器的结束位置
    38.         	//return reverse_iterator(_head); //等价与正向迭代器的头节点
    39.  
    40.         }
    41.  
    42.         reverse_iterator rend()
    43.         {
    44.         	return reverse_iterator(begin());        //返回正向迭代器的起始位置
    45.         	//return reverse_iterator(_head->_next); //等价于正向迭代器头节点的下一个结点
    46.         }
    47.  
    48.         const_reverse_iterator rbegin()const
    49.         {
    50.         	return const_reverse_iterator(end());   //返回正向迭代器的结束位置
    51.         	//return const_reverse_iterator(_head); //等价与正向迭代器的头节点
    52.         }
    53.  
    54.         const_reverse_iterator rend()const
    55.         {
    56.         	return const_reverse_iterator(begin());        //返回正向迭代器的起始位置
    57.         	//return const_reverse_iterator(_head->_next); //等价于正向迭代器头节点的下一个结点
    58.         }
    59.     };
    60. }

    8.增删查改

    1. //头插
    2. void push_front(const T& x)
    3. {
    4. 	insert(begin(), x);
    5. }
    6.  
    7. //尾插
    8. void push_back(const T& x)
    9. {
    10. 	/*
    11. 	Node* tail = _head->_prev;
    12. 	Node* newnode = new Node(x);
    13. 	tail->_next = newnode;
    14. 	newnode->_prev = tail;
    15. 	newnode->_next = _head;
    16. 	_head->_prev = newnode;
    17. 	*/
    18. 	insert(end(), x);
    19. }
    20.  
    21. //头删
    22. void pop_front()
    23. {
    24. 	erase(begin());
    25. }
    26.  
    27. //尾删
    28. void pop_back()
    29. {
    30. 	erase(--end());
    31. }
    32.  
    33. //在pos位置插入元素x
    34. iterator insert(iterator pos, const T& x)
    35. {
    36. 	Node* cur = pos._node;    
    37. 	Node* prev = cur->_prev;     
    38. 	Node* newnode = new Node(x); 
    39. 	prev->_next = newnode;      
    40. 	newnode->_prev = prev;
    41. 	newnode->_next = cur;
    42. 	cur->_prev = newnode;
    43. 	return iterator(newnode);//在pos位置插入返回的是新插入的节点位置
    44. }
    45.  
    46. //在pos位置删除元素
    47. iterator erase(iterator pos)
    48. {
    49. 	assert(pos != end());
    50. 	Node* prev = pos._node->_prev;
    51. 	Node* next = pos._node->_next;
    52. 	delete pos._node;
    53. 	prev->_next = next;
    54. 	next->_prev = prev;
    55. 	return iterator(next);//返回的是删除pos位置节点的下一个节点
    56. }

    六、完整代码

    1.ListNode.h

    1. #pragma once
    2.  
    3. namespace mlg
    4. {
    5. 	template<class T>
    6. 	struct ListNode
    7. 	{
    8. 		ListNode<T>* _prev;
    9. 		ListNode<T>* _next;
    10. 		T _data;
    11.  
    12. 		ListNode(const T& data= T())
    13. 			:_prev(nullptr)
    14. 			,_next(nullptr)
    15. 			,_data(data)
    16. 		{}
    17. 		
    18. 	};
    19. }

    2.iterator.h

    1. #pragma once
    2.  
    3. namespace mlg
    4. {
    5. 	template<class T,class Ref,class Ptr>
    6. 	struct __list_iterator
    7. 	{
    8. 		typedef ListNode<T> Node;
    9.  
    10. 		typedef __list_iterator<T, Ref, Ptr> self;
    11.  
    12. 		typedef Ref reference;
    13. 		typedef Ptr pointer;
    14.  
    15. 		Node* _node;
    16.  
    17. 		__list_iterator(Node* x)
    18. 			:_node(x)
    19. 		{}
    20.  
    21. 		Ref operator*()
    22. 		{
    23. 			return _node->_data;
    24. 		}
    25.  
    26. 		Ptr operator->()
    27. 		{
    28. 			return &_node->_data;
    29. 		}
    30.  
    31. 		//++it
    32. 		self& operator++()
    33. 		{
    34. 			_node = _node->_next;
    35. 			return *this;
    36. 		}
    37. 		//it++
    38. 		self operator++(int)
    39. 		{
    40. 			self tmp(*this);
    41. 			_node = _node->_next;
    42. 			return tmp;
    43. 		}
    44. 		//--it
    45. 		self& operator--()
    46. 		{
    47. 			_node = _node->_prev;
    48. 			return *this;
    49. 		}
    50. 		//it--
    51. 		self operator--(int)
    52. 		{
    53. 			self tmp(*this);
    54. 			_node = _node->_prev;
    55. 			return tmp;
    56. 		}
    57.  
    58. 		bool operator==(const self& it)const
    59. 		{
    60. 			return _node == it._node;
    61. 		}
    62.  
    63. 		bool operator!=(const self& it)const
    64. 		{
    65. 			return _node != it._node;
    66. 		}
    67. 	
    68. 	};
    69. }

    3.reverse_iterator.h 

    1. #pragma once
    2.  
    3. namespace mlg
    4. {
    5.     template<class Iterator,class Ref,class Ptr>
    6. 	class __list_reverse_iterator
    7. 	{
    8. 		typedef __list_reverse_iterator<Iterator, Ref, Ptr> self;
    9. 	public:
    10. 		__list_reverse_iterator(Iterator it)
    11. 			:_it(it)
    12. 		{}
    13.  
    14. 		Ref operator*()
    15. 		{
    16. 			Iterator prev = _it;
    17. 			return *--prev;
    18. 		}
    19.  
    20. 		Ptr operator->() {return &operator*();}
    21.  
    22. 		//++it
    23. 		self& operator++()
    24. 		{
    25. 			--_it;
    26. 			return *this;
    27. 		}
    28. 		//it++
    29. 		self operator++(int)
    30. 		{
    31. 			self tmp(*this);
    32. 			_it--;
    33. 			return tmp;
    34. 		}
    35. 		//--it
    36. 		self& operator--()
    37. 		{
    38. 			++_it;
    39. 			return *this;
    40. 		}
    41. 		//it--
    42. 		self operator--(int)
    43. 		{
    44. 			self tmp(*this);
    45. 			_it++;
    46. 			return tmp;
    47. 		}
    48.  
    49. 		bool operator!=(const self& rit)const {return _it != rit._it;}
    50. 		bool operator==(const self& rit)const {return _it == rit._it;}
    51.  
    52. 	private:
    53. 		Iterator _it;
    54. 	};
    55. }

    4.list.h

    1. #pragma once
    2. #include "ListNode.h"
    3. #include "iterator.h"
    4. #include "reverse_iterator.h"
    5.  
    6. namespace mlg
    7. {
    8. 	template<class T>
    9. 	class list
    10. 	{
    11. 		typedef ListNode<T> Node;
    12. 	public:
    13. 		//正向迭代器
    14. 		typedef __list_iterator<T, T&, T*> iterator;
    15. 		typedef __list_iterator<T, const T&, const T*> const_iterator;
    16.  
    17. 		iterator begin() {return iterator(_head->_next);}
    18. 		iterator end() {return iterator(_head);}
    19. 		const_iterator begin()const {return const_iterator(_head->_next);}
    20. 		const_iterator end()const {return const_iterator(_head);}
    21.  
    22. 		//反向迭代器
    23. 		typedef __list_reverse_iterator<iterator, T&, T*> reverse_iterator;
    24. 		typedef __list_reverse_iterator<iterator, const T&, const T*> const_reverse_iterator;
    25.  
    26. 		reverse_iterator rbegin() {return reverse_iterator(end());}
    27. 		reverse_iterator rend() {return reverse_iterator(begin());}
    28. 		const_reverse_iterator rbegin()const {return const_reverse_iterator(end());}
    29. 		const_reverse_iterator rend()const {return const_reverse_iterator(begin());}
    30.  
    31. 		//构造函数
    32. 		list()
    33. 		{
    34. 			_head = new Node;     //new一个节点出来
    35. 			_head->_prev = _head; 
    36. 			_head->_next = _head; //_prev 和 _next 同时指向了头结点，形成了双向循链表
    37. 		}
    38.  
    39. 		//用n个val个构造      			   
    40. 		list(int n, const T& val = T())        			   
    41. 		{												  
    42. 			_head = new Node;
    43. 			_head->_prev = _head;
    44. 			_head->_next = _head;
    45. 			for (int i = 0; i < n; i++)
    46. 			{
    47. 				push_back(val);
    48. 			}
    49. 		}
    50.  
    51. 		//迭代器区间构造
    52. 		template<class IputIterator>
    53. 		list(IputIterator first, IputIterator last)
    54. 		{
    55. 			_head = new Node;
    56. 			_head->_prev = _head;
    57. 			_head->_next = _head;
    58. 			while (first != last)
    59. 			{
    60. 				push_back(*first);
    61. 				++first;
    62. 			}
    63. 		}
    64.  
    65. 		//拷贝构造 --- 现代写法 lt2(lt1)
    66. 		list(const list<T>& lt)
    67. 		{
    68. 			_head = new Node;
    69. 			_head->_prev = _head;
    70. 			_head->_next = _head;
    71. 			list<T> tmp(lt.begin(), lt.end());
    72. 			std::swap(_head, tmp._head);
    73. 		}
    74.  
    75. 		//赋值重载 --- 现代写法 lt2 = lt1
    76. 		list<T>& operator=(list<T> lt)
    77. 		{
    78. 			std::swap(_head, lt._head);
    79. 			return *this;
    80. 		}
    81. 		~list()
    82. 		{
    83. 			clear();
    84. 			delete _head;
    85. 			_head = nullptr;
    86. 		}
    87.  
    88. 		void clear()
    89. 		{
    90. 			iterator it = begin();
    91. 			while (it != end())
    92. 			{
    93. 				erase(it++);
    94. 			}
    95. 			_head->_prev = _head;
    96. 			_head->_next = _head;
    97. 		}
    98.  
    99. 		void push_front(const T& x){ insert(begin(), x); }
    100.  
    101. 		void push_back(const T& x) { insert(end(), x);}
    102.  
    103. 		void pop_front() {erase(begin());}
    104.  
    105. 		void pop_back(){erase(--end());}
    106.  
    107. 		//在pos位置插入元素x
    108. 		iterator insert(iterator pos, const T& x)
    109. 		{
    110. 			Node* cur = pos._node;
    111. 			Node* prev = cur->_prev;
    112. 			Node* newnode = new Node(x);
    113. 			prev->_next = newnode;
    114. 			newnode->_prev = prev;
    115. 			newnode->_next = cur;
    116. 			cur->_prev = newnode;
    117. 			return iterator(newnode);
    118. 		}
    119.  
    120. 		//在pos位置删除元素
    121. 		iterator erase(iterator pos)
    122. 		{
    123. 			assert(pos != end());
    124. 			Node* prev = pos._node->_prev;
    125. 			Node* next = pos._node->_next;
    126. 			delete pos._node;
    127. 			prev->_next = next;
    128. 			next->_prev = prev;
    129. 			return iterator(next);
    130. 		}
    131.  
    132. 	private:
    133. 		Node* _head;
    134. 	};
    135.  
    136. 	void print_list(const list<int>& lt)
    137. 	{
    138. 		list<int>::const_iterator it = lt.begin();
    139. 		while (it != lt.end())
    140. 		{
    141. 			cout << *it << " ";
    142. 			++it;
    143. 		}
    144. 		cout << endl;
    145. 	}
    146.  
    147. 	void test_list5()
    148. 	{
    149. 		list<int> lt;
    150. 		lt.push_back(1);
    151. 		lt.push_back(2);
    152. 		lt.push_back(3);
    153. 		lt.push_back(4);
    154. 		list<int>::reverse_iterator rit = lt.rbegin();
    155. 		while (rit != lt.rend())
    156. 		{
    157. 			cout << *rit << " ";
    158. 			++rit;
    159. 		}
    160. 		cout << endl;
    161. 	}
    162. }

             以上是对list模拟实现的全部结束，大家可以在.c文件下进行测试。如果存在任何问题，或者有不同的见解，大家可以直接在评论区提出来

  • 相关阅读:
    iis站点https绑定
    Docker实战：Docker安装nginx并配置SSL
    e^x的导数
    BiSeNet v2
    java 项目管理工具gradle
    网络流量监控与DNS流量分析
    Python3：@property属性装饰器
    MegEngine Inference 卷积优化之 Im2col 和 winograd 优化
    微信小程序之后台首页交互
    基于Java的医院预约挂号系统设计与实现(源码+lw+部署文档+讲解等)
  • 原文地址：https://blog.csdn.net/sjsjnsjnn/article/details/125451866