• list模拟实现（15）

    目录

    1、简单框架

    1、list.h

    2、test.cpp

    2、list迭代器实现

    1、list.h

    2、test.cpp

    3、思考

    1、迭代器中的拷贝构造和赋值重载是否需要自己实现？析构呢？

    2、体会类型的力量

    3、const迭代器实现

    1、list.h

    2、test.cpp

    4、重载迭代器的operator->

    5、insert和erase接口实现

    1、insert模拟实现

    2、erase模拟实现

    6、vector与list对比

    1、vector

    2、list

    7、list拷贝构造、赋值重载问题

    1、clear模拟实现

    2、析构函数

    3、深拷贝

    1、传统写法

    2、现代写法

    8、迭代器区间和n个val初始化的构造函数冲突

    1、问题

    2、解决方法

    9、反向迭代器模拟实现

    1、简单框架

    list的底层是一个双向带头循环链表

    1、list.h

    1. #pragma once
    2. #include
    3. using namespace std;
    4.  
    5. namespace tutu
    6. {
    7. 	template<class T>
    8. 	struct listNode
    9. 	{
    10. 		listNode* _next;
    11. 		listNode* _prev;
    12. 		T _data;
    13.  
    14. 		listNode(const T& data=T())
    15. 			:_next(nullptr)
    16. 			,_prev(nullptr)
    17. 			,_data(data)
    18. 		{}
    19. 	};
    20.  
    21. 	template<class T>
    22. 	class list
    23. 	{
    24. 		typedef listNode Node;
    25. 	public:
    26. 		list()
    27. 			:_head(new Node)
    28. 		{
    29. 			_head->_next = _head;
    30. 			_head->_prev = _head;
    31. 		}
    32.  
    33. 		void push_back(const T& x)
    34. 		{
    35. 			Node* newnode = new Node(x);
    36. 			Node* tail = _head->_prev;
    37. 			tail->_next = newnode;
    38. 			newnode->_prev = tail;
    39. 			newnode->_next = _head;
    40. 			_head->_prev = newnode;
    41. 		}
    42. 	private:
    43. 		Node* _head;
    44. 	};
    45.  
    46. 	void test1()
    47. 	{
    48. 		list<int> l1;
    49. 		l1.push_back(1);
    50. 		l1.push_back(2);
    51. 		l1.push_back(3);
    52. 		l1.push_back(4);
    53.  
    54. 	}
    55. }

    2、test.cpp

    1. #include"list.h"
    2.  
    3. int main()
    4. {
    5. 	tutu::test1();
    6. 	return 0;
    7. }

    2、list迭代器实现

    迭代器是像指针一样的类型，模仿指针的行为，解引用能取数据，++能到下一个位置。

    在string和vector中，迭代器就是原生指针，因为他们底层是连续的物理空间；但是list底层物理空间不是连续的，如果还用原生指针，解引用是一个节点，++到不了下一个位置，但是C++提供了类，自定义类型可以对运算符进行重载，所以list底层迭代器的实现就是对节点指针进行封装，重载operator++、operator!=和operator*。

    1、list.h

    1. #pragma once
    2. #include
    3. using namespace std;
    4.  
    5. namespace tutu
    6. {
    7. 	template<class T>
    8. 	struct listNode
    9. 	{
    10. 		listNode* _next;
    11. 		listNode* _prev;
    12. 		T _data;
    13.  
    14. 		listNode(const T& data=T())
    15. 			:_next(nullptr)
    16. 			,_prev(nullptr)
    17. 			,_data(data)
    18. 		{}
    19. 	};
    20.  
    21. 	template<class T>
    22. 	struct __list_iterator
    23. 	{
    24. 		typedef listNode Node;
    25. 		Node* _node;
    26.  
    27. 		__list_iterator(Node* node)
    28. 			:_node(node)
    29. 		{}
    30.  
    31. 		//++it
    32. 		__list_iterator& operator++()
    33. 		{
    34. 			_node = _node->_next;
    35. 			return *this;
    36. 		}
    37.  
    38. 		//it++
    39. 		__list_iterator operator++(int)
    40. 		{
    41. 			__list_iterator tmp(*this);
    42. 			_node = _node->_next;
    43. 			return tmp;
    44. 		}
    45.  
    46. 		//--it
    47. 		__list_iterator& operator--()
    48. 		{
    49. 			_node = _node->_prev;
    50. 			return *this;
    51. 		}
    52.  
    53. 		//it--
    54. 		__list_iterator operator--(int)
    55. 		{
    56. 			__list_iterator tmp(*this);
    57. 			_node = _node->_prev;
    58. 			return tmp;
    59. 		}
    60.  
    61. 		T& operator*()
    62. 		{
    63. 			return _node->_data;
    64. 		}
    65.  
    66. 		bool operator!=(const __list_iterator& it) const
    67. 		{
    68. 			return _node != it._node;
    69. 		}
    70.  
    71. 		bool operator==(const __list_iterator& it) const
    72. 		{
    73. 			return _node == it._node;
    74. 		}
    75.  
    76. 	};
    77.  
    78. 	template<class T>
    79. 	class list
    80. 	{
    81. 		typedef listNode Node;
    82. 	public:
    83. 		typedef __list_iterator iterator;
    84.  
    85. 		iterator begin()
    86. 		{
    87. 			return iterator(_head->_next);
    88. 		}
    89.  
    90. 		iterator end()
    91. 		{
    92. 			return iterator(_head);
    93. 		}
    94.  
    95. 		list()
    96. 			:_head(new Node)
    97. 		{
    98. 			_head->_next = _head;
    99. 			_head->_prev = _head;
    100. 		}
    101.  
    102. 		void push_back(const T& x)
    103. 		{
    104. 			Node* newnode = new Node(x);
    105. 			Node* tail = _head->_prev;
    106. 			tail->_next = newnode;
    107. 			newnode->_prev = tail;
    108. 			newnode->_next = _head;
    109. 			_head->_prev = newnode;
    110. 		}
    111. 	private:
    112. 		Node* _head;
    113. 	};
    114.  
    115. 	void test1()
    116. 	{
    117. 		list<int> l1;
    118. 		l1.push_back(1);
    119. 		l1.push_back(2);
    120. 		l1.push_back(3);
    121. 		l1.push_back(4);
    122. 		l1.push_back(5);
    123.  
    124. 		list<int>::iterator it = l1.begin();
    125. 		while (it != l1.end())
    126. 		{
    127. 			cout << *it << " ";
    128. 			++it;
    129. 		}
    130. 		cout << endl;
    131. 	}
    132. }

    2、test.cpp

    1. #include"list.h"
    2.  
    3. int main()
    4. {
    5. 	tutu::test1();
    6. 	return 0;
    7. }

    3、思考

    1、迭代器中的拷贝构造和赋值重载是否需要自己实现？析构呢？

    答：都不需要。这里就是需要浅拷贝，默认生成的即可。迭代器中虽然有一个节点指针的成员，但是这个成员不归迭代器管，迭代器的意义就是访问和修改容器的。迭代器是借助节点的指针访问修改链表，节点是属于链表的，不属于迭代器，所以不归它管释放。

    2、体会类型的力量

    Node*原生指针和一个迭代器对象，它们占用的空间是一样大的，在32位机器上都是4个byte，并且值存的也一样，但是对他们使用运算符的意义和结果是不一样的。

    3、const迭代器实现

    普通对象调普通迭代器，const对象调const迭代器，目前我们只实现了普通迭代器，const迭代器还需要再写一份，传统的写法是再写一份const版本的迭代器，但是这样会造成代码冗余，这里推荐高手写法，即stl底层实现写法。

    比较一下普通迭代器和const迭代器的区别，普通迭代器可读可写，const迭代器只能读不能写，体现到代码层面上就是operator*，一个是返回引用，一个是返回const引用，所以这里用了一个模板参数解决这个问题。

    1、list.h

    1. #pragma once
    2. #include
    3. using namespace std;
    4.  
    5. namespace tutu
    6. {
    7. 	template<class T>
    8. 	struct listNode
    9. 	{
    10. 		listNode* _next;
    11. 		listNode* _prev;
    12. 		T _data;
    13.  
    14. 		listNode(const T& data=T())
    15. 			:_next(nullptr)
    16. 			,_prev(nullptr)
    17. 			,_data(data)
    18. 		{}
    19. 	};
    20.  
    21. 	template<class T,class Ref>
    22. 	struct __list_iterator
    23. 	{
    24. 		//因为增加了一个模板参数，所以下面的类型都要改，所以增加一个typedef
    25. 		typedef __list_iterator self;
    26. 		typedef listNode Node;
    27. 		Node* _node;
    28.  
    29. 		__list_iterator(Node* node)
    30. 			:_node(node)
    31. 		{}
    32.  
    33. 		//++it
    34. 		self& operator++()
    35. 		{
    36. 			_node = _node->_next;
    37. 			return *this;
    38. 		}
    39.  
    40. 		//it++
    41. 		self operator++(int)
    42. 		{
    43. 			__list_iterator tmp(*this);
    44. 			_node = _node->_next;
    45. 			return tmp;
    46. 		}
    47.  
    48. 		//--it
    49. 		self& operator--()
    50. 		{
    51. 			_node = _node->_prev;
    52. 			return *this;
    53. 		}
    54.  
    55. 		//it--
    56. 		self operator--(int)
    57. 		{
    58. 			self tmp(*this);
    59. 			_node = _node->_prev;
    60. 			return tmp;
    61. 		}
    62.  
    63. 		Ref operator*()
    64. 		{
    65. 			return _node->_data;
    66. 		}
    67.  
    68. 		bool operator!=(const self& it) const
    69. 		{
    70. 			return _node != it._node;
    71. 		}
    72.  
    73. 		bool operator==(const self& it) const
    74. 		{
    75. 			return _node == it._node;
    76. 		}
    77.  
    78. 	};
    79.  
    80. 	template<class T>
    81. 	class list
    82. 	{
    83. 		typedef listNode Node;
    84. 	public:
    85. 		typedef __list_iterator iterator;
    86. 		typedef __list_iteratorconst T&> const_iterator;
    87.  
    88. 		const_iterator begin() const
    89. 		{
    90. 			return const_iterator(_head->_next);
    91. 		}
    92.  
    93. 		const_iterator end() const
    94. 		{
    95. 			return const_iterator(_head);
    96. 		}
    97.  
    98. 		iterator begin()
    99. 		{
    100. 			return iterator(_head->_next);
    101. 		}
    102.  
    103. 		iterator end()
    104. 		{
    105. 			return iterator(_head);
    106. 		}
    107.  
    108. 		list()
    109. 			:_head(new Node)
    110. 		{
    111. 			_head->_next = _head;
    112. 			_head->_prev = _head;
    113. 		}
    114.  
    115. 		void push_back(const T& x)
    116. 		{
    117. 			Node* newnode = new Node(x);
    118. 			Node* tail = _head->_prev;
    119. 			tail->_next = newnode;
    120. 			newnode->_prev = tail;
    121. 			newnode->_next = _head;
    122. 			_head->_prev = newnode;
    123. 		}
    124. 	private:
    125. 		Node* _head;
    126. 	};
    127.  
    128.  
    129. 	void Print_list(const list<int>& lt)
    130. 	{
    131. 		list<int>::const_iterator it = lt.begin();
    132. 		while (it != lt.end())
    133. 		{
    134. 			cout << *it << " ";
    135. 			++it;
    136. 		}
    137. 		cout << endl;
    138. 	}
    139.  
    140. 	void test1()
    141. 	{
    142. 		list<int> l1;
    143. 		l1.push_back(1);
    144. 		l1.push_back(2);
    145. 		l1.push_back(3);
    146. 		l1.push_back(4);
    147. 		l1.push_back(5);
    148.  
    149. 		Print_list(l1);
    150.  
    151. 	}
    152. }

    2、test.cpp

    1. #include"list.h"
    2.  
    3. int main()
    4. {
    5. 	tutu::test1();
    6. 	return 0;
    7. }

    4、重载迭代器的operator->

    前面都是对list举例，链表中放整形，如果是放一个自定义类型，那么cout<<*it 时就会出问题，例如：list，解引用是一个Date类，需要对流提取进行重载，如果不想重载可以如图：

    迭代器是像指针一样的类型，所以可以对operator->进行重载，可以得到如下代码：

    在__list_iterator中，对operator->进行重载，如：

    1. T* operator->()
    2. {
    3. 	return &_node->_data;
    4. }

    注意：

    然后对于operator->的返回值和operator*有着相同的问题，普通迭代器返回Date*，const迭代器返回const Date*，所以上述不能给T*，这里建议新增模板参数Ptr，传参时，普通迭代器传T*，const迭代器传const T*，如：

    1. #pragma once
    2. #include
    3. using namespace std;
    4.  
    5. namespace tutu
    6. {
    7. 	template<class T>
    8. 	struct listNode
    9. 	{
    10. 		listNode* _next;
    11. 		listNode* _prev;
    12. 		T _data;
    13.  
    14. 		listNode(const T& data=T())
    15. 			:_next(nullptr)
    16. 			,_prev(nullptr)
    17. 			,_data(data)
    18. 		{}
    19. 	};
    20.  
    21. 	template<class T,class Ref,class Ptr>
    22. 	struct __list_iterator
    23. 	{
    24. 		//因为增加了一个模板参数，所以下面的类型都要改，所以增加一个typedef
    25. 		typedef __list_iterator self;
    26. 		typedef listNode Node;
    27. 		Node* _node;
    28.  
    29. 		__list_iterator(Node* node)
    30. 			:_node(node)
    31. 		{}
    32.  
    33. 		//++it
    34. 		self& operator++()
    35. 		{
    36. 			_node = _node->_next;
    37. 			return *this;
    38. 		}
    39.  
    40. 		//it++
    41. 		self operator++(int)
    42. 		{
    43. 			__list_iterator tmp(*this);
    44. 			_node = _node->_next;
    45. 			return tmp;
    46. 		}
    47.  
    48. 		//--it
    49. 		self& operator--()
    50. 		{
    51. 			_node = _node->_prev;
    52. 			return *this;
    53. 		}
    54.  
    55. 		//it--
    56. 		self operator--(int)
    57. 		{
    58. 			self tmp(*this);
    59. 			_node = _node->_prev;
    60. 			return tmp;
    61. 		}
    62.  
    63. 		Ref operator*()
    64. 		{
    65. 			return _node->_data;
    66. 		}
    67.  
    68. 		Ptr operator->()
    69. 		{
    70. 			return &_node->_data;
    71. 		}
    72.  
    73. 		bool operator!=(const self& it) const
    74. 		{
    75. 			return _node != it._node;
    76. 		}
    77.  
    78. 		bool operator==(const self& it) const
    79. 		{
    80. 			return _node == it._node;
    81. 		}
    82.  
    83. 	};
    84.  
    85. 	template<class T>
    86. 	class list
    87. 	{
    88. 		typedef listNode Node;
    89. 	public:
    90. 		typedef __list_iterator iterator;
    91. 		typedef __list_iteratorconst T&,const T*> const_iterator;
    92.  
    93. 		const_iterator begin() const
    94. 		{
    95. 			return const_iterator(_head->_next);
    96. 		}
    97.  
    98. 		const_iterator end() const
    99. 		{
    100. 			return const_iterator(_head);
    101. 		}
    102.  
    103. 		iterator begin()
    104. 		{
    105. 			return iterator(_head->_next);
    106. 		}
    107.  
    108. 		iterator end()
    109. 		{
    110. 			return iterator(_head);
    111. 		}
    112.  
    113. 		list()
    114. 			:_head(new Node)
    115. 		{
    116. 			_head->_next = _head;
    117. 			_head->_prev = _head;
    118. 		}
    119.  
    120. 		void push_back(const T& x)
    121. 		{
    122. 			Node* newnode = new Node(x);
    123. 			Node* tail = _head->_prev;
    124. 			tail->_next = newnode;
    125. 			newnode->_prev = tail;
    126. 			newnode->_next = _head;
    127. 			_head->_prev = newnode;
    128. 		}
    129. 	private:
    130. 		Node* _head;
    131. 	};
    132.  
    133. 	struct Date
    134. 	{
    135. 		int _year;
    136. 		int _month;
    137. 		int _day;
    138.  
    139. 		Date(int year = 1,int month = 1,int day=1)
    140. 			:_year(year)
    141. 			,_month(month)
    142. 			,_day(day)
    143. 		{}
    144. 	};
    145.  
    146. 	void Print_list2(const list& lt)
    147. 	{
    148. 		list::const_iterator it = lt.begin();
    149. 		while (it != lt.end())
    150. 		{
    151. 			cout << it->_year << "/" << it->_month << "/" << it->_day << endl;
    152. 			++it;
    153. 		}
    154. 		cout << endl;
    155. 	}
    156.  
    157. 	void test2()
    158. 	{
    159. 		list l1;
    160. 		l1.push_back(Date(2022, 11, 23));
    161. 		l1.push_back(Date(2022, 11, 24));
    162. 		l1.push_back(Date(2022, 11, 25));
    163. 		l1.push_back(Date(2022, 11, 26));
    164.  
    165. 		Print_list2(l1);
    166. 	}
    167. }

    5、insert和erase接口实现

    1、insert模拟实现

    有了insert，push_back和push_front可以复用：

    2、erase模拟实现

    有了erase，pop_back和pop_front就可以复用：

    6、vector与list对比

    1、vector

    vector是连续的物理空间，是优势，也是劣势。

    优势：支持高效的随机访问。

    劣势：1、空间不够要增容，增容代价比较大  2、可能存在一定的空间浪费，按需申请，会导致频繁增容，所以都会扩2倍左右  3、头部或中部插入删除需要挪动数据，效率低下

    2、list

    list很好解决了vector以上的问题

    1、按需申请释放空间  2、list任意位置支持O(1)插入删除

    小结：vector和list是互补的两个数据结构。

    7、list拷贝构造、赋值重载问题

    1、clear模拟实现

    2、析构函数

    3、深拷贝

    1、传统写法

    2、现代写法

    1、支持迭代器区间初始化的构造函数

    2、拷贝构造

    3、赋值重载

    8、迭代器区间和n个val初始化的构造函数冲突

    1、问题

    n个val初始化的构造函数：

    目前我们的代码中，已经写了支持一段迭代器区间初始化和n个val初始化的构造函数，但是当写以下代码时，编译器会报错：

    这就是经典的，迭代器区间初始化和n个val初始化的构造函数的冲突问题：

    小结：1、整形的字面常量默认为int类型的，浮点数的字面常量默认为double类型。  2、编译器匹配的原则：只会找更匹配的。

    2、解决方法

    法一：将size_t  n改为int  n

    法二：提供一个int  n的重载版本

    9、反向迭代器模拟实现

    反向迭代器跟正向迭代器的区别就是++、--的方向是反的，所以反向迭代器封装正向迭代器即可，控制重载++、--的方向。

    list库里的底层rbegin、rend跟begin、end是对称的。所以operator*取前一个位置，主要就是为了让反向迭代器开始和结束跟正向迭代器对称。

    因为反向迭代器是对正向迭代器的一个封装，所以可以做成模板，iterator是哪个容器的迭代器，reverse_iterator就可以适配出那个容器的反向迭代器，这是复用的体现。

    reverse_iterator.h

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

    在list.h中包一下上述头文件，再增加两行typedef，就可以实现反向迭代器

    我们这里有三个模板参数，而库里只有一个，这里是做了简化，因为库里的比较麻烦。

    注意：

    1、一个类里面要取它里面的东西，只能取它的成员变量和内嵌类型，模板参数可通过typedef取到。 

    2、要取模板参数中的内嵌类型，编译器这里肯定是通不过的，因为编译器编译到这里还没有实例化，凡是要取一个模板参数里的内嵌类型（内部类或typedef的），加个typename是告诉编译器，它是一个类型，先让它通过，等实例化时，再去找它里面的类型。

    3、如果上述按照库中实现，定义一个模板参数，在__list_iterator定义了内嵌类型，但是vector、string就不能直接套，它们底层是原生指针，不是自定义类型，所以还是三个模板参数比较好。vector的迭代器是原生指针，无法取内部类型，那么上面的实现就完了，stl源代码中是使用了一个叫迭代器萃取的技术解决的。

  • 相关阅读:
    深入探讨医保购药APP的技术架构与设计思路
    安装Vue Devtools调试工具插件
    记一次使用nacos2踩到的坑
    Python 配置pyqt5开发环境
    Scala词频统计
    vue2实现可拖拽甘特图（结合element-ui的gantt图）
    C++ 指向数组的指针
    用git上传github加强
    健身戴什么耳机，盘点几款健身佩戴的耳机推荐
    《实现领域驱动设计》- 领域服务
  • 原文地址：https://blog.csdn.net/qq_44463986/article/details/128005725