• 【STL】：list的模拟实现

    朋友们、伙计们，我们又见面了，本期来给大家解读一下有关list的模拟实现，如果看完之后对你有一定的启发，那么请留下你的三连，祝大家心想事成！

    C 语 言 专 栏：C语言：从入门到精通

    数据结构专栏：数据结构

    个  人  主  页 ：stackY、

    C + + 专 栏   ：C++

    Linux 专 栏  ：Linux

    目录

    1. 基本构造

    2. 正向迭代器

    2.1 非const迭代器

    2.2 const迭代器

    2.3 正向迭代器的改进优化

    3. 修改相关接口

    3.1 insert、erase

    3.2 尾插、头插、尾删、头删、清理

    4. 拷贝构造、赋值重载、析构

    5. 完整代码

    1. 基本构造

    list的底层其实是一个带头双向循环的链表，所以在模拟实现之前可以看一下库里面怎么实现的：

    1. namespace ywh
    2. {
    3. 	//链表结构
    4. 	template<class T>
    5. 	struct list_node
    6. 	{
    7. 		T _data;                 //节点中的数据
    8. 		list_node* _prev;    //指向前一个节点的指针
    9. 		list_node* _next;    //指向后一个节点的指针
    10.  
    11.         //构造
    12. 		list_node(const T& x = T())
    13. 			:_data(x)
    14. 			, _prev(nullptr)
    15. 			, _next(nullptr)
    16. 		{}
    17.  
    18. 	};
    19.  
    20. 	//list结构
    21. 	template<class T>
    22. 	class list
    23. 	{
    24. 	public:
    25. 		typedef list_node Node;
    26. 	public:
    27. 		
    28. 		//空初始化
    29. 		void empty_init()
    30. 		{
    31. 			_head = new Node;
    32. 			_head->_prev = _head;
    33. 			_head->_next = _next;
    34. 		}
    35. 		//构造
    36. 		list()
    37. 		{
    38. 			empty_init();
    39. 		}
    40.  
    41. 	private:
    42. 		Node* _head;  //链表的头节点
    43. 		size_t _size; //节点个数
    44. 	};
    45. }

    2. 正向迭代器

    在使用list的阶段的迭代器使用方法和之前的string、vector一样，但是了解过链表的结构都知道，链表要访问下一个节点就是使用节点中的next指针指向下一个节点，需要访问里面的数据需要找到里面的data，++和解引用并不能访问链表的节点，那么迭代器的使用在底层肯定是封装加运算符重载。

    在实现迭代器的时候也需要采用封装和运算符重载，运算符重载需要用到++、--、!=、==、*、->等运算符。迭代器分为const迭代器和非const迭代器，首先先来看看非const迭代器：

    2.1 非const迭代器

    迭代器的实现一般使用struct来进行封装：

    1. namespace ljm
    2. {
    3. 	//链表结构
    4. 	template<class T>
    5. 	struct list_node
    6. 	{
    7. 		T _data;                 //节点中的数据
    8. 		list_node* _prev;    //指向前一个节点的指针
    9. 		list_node* _next;    //指向后一个节点的指针
    10.  
    11. 		//构造
    12. 		list_node(const T& x = T())
    13. 			:_data(x)
    14. 			, _prev(nullptr)
    15. 			, _next(nullptr)
    16. 		{}
    17.  
    18. 	};
    19.  
    20. 	//非const正向迭代器
    21. 	template<class T>
    22. 	struct __list_iterator
    23. 	{
    24. 		typedef list_node Node;
    25. 		typedef __list_iterator self;
    26. 		Node* _node;
    27. 		//迭代器构造
    28. 		__list_iterator(Node* node)
    29. 			:_node(node)
    30. 		{}
    31. 		
    32. 		//前置
    33. 		//operator++
    34. 		self& operator++()
    35. 		{
    36. 			return _node->_next;
    37. 		}
    38. 		//operator--
    39. 		self& operator--()
    40. 		{
    41. 			return _node->_prev;
    42. 		}
    43.  
    44. 		//后置
    45. 		self operator++(int)
    46. 		{
    47. 			self* tmp(_node);
    48. 			_node = _node->_next;
    49. 			return tmp;
    50. 		}
    51. 		//operator--
    52. 		self operator--(int)
    53. 		{
    54. 			self* tmp(_node);
    55. 			_node = _node->_prev;
    56. 			return tmp;
    57. 		}
    58.  
    59. 		//operator*
    60. 		T& operator*()
    61. 		{
    62. 			return _node->_data;
    63. 		}
    64. 		//operator->
    65. 		T* operator->()
    66. 		{
    67. 			return &_node->_data;
    68. 		}
    69. 		//operator!=
    70. 		bool operator!=(const self& s)
    71. 		{
    72. 			return _node != s._node;
    73. 		}
    74. 		//operator==
    75. 		bool operator==(const self& s)
    76. 		{
    77. 			return _node == s._node;
    78. 		}
    79. 	};
    80.  
    81. 	//list结构
    82. 	template<class T>
    83. 	class list
    84. 	{
    85. 	public:
    86. 		typedef list_node Node;
    87. 	public:
    88. 		
    89. 		//空初始化
    90. 		void empty_init()
    91. 		{
    92. 			_head = new Node;
    93. 			_head->_prev = _head;
    94. 			_head->_next = _head;
    95. 		}
    96. 		//构造
    97. 		list()
    98. 		{
    99. 			empty_init();
    100. 		}
    101.         ///正向迭代器
    102. 		iterator begin()
    103. 		{
    104. 			return iterator(_head->_next); //使用匿名对象进行构造
    105. 		}
    106. 		iterator end()
    107. 		{
    108. 			return iterator(_head);
    109. 		}
    110.  
    111. 	private:
    112. 		Node* _head;  //链表的头节点
    113. 		size_t _size; //节点个数
    114. 	};
    115. }

    2.2 const迭代器

    迭代器中涉及到修改的就是*和->，const迭代器的作用是指向的内容不能修改，本身不能修改，所以需要重新进行封装：

    1. namespace ljm
    2. {
    3. 	//链表结构
    4. 	template<class T>
    5. 	struct list_node
    6. 	{
    7. 		T _data;                 //节点中的数据
    8. 		list_node* _prev;    //指向前一个节点的指针
    9. 		list_node* _next;    //指向后一个节点的指针
    10.  
    11. 		//构造
    12. 		list_node(const T& x = T())
    13. 			:_data(x)
    14. 			, _prev(nullptr)
    15. 			, _next(nullptr)
    16. 		{}
    17.  
    18. 	};
    19.  
    20. 	//非const正向迭代器
    21. 	//...
    22.  
    23. 	//const正向迭代器
    24. 	template<class T>
    25. 	struct __list_const_iterator
    26. 	{
    27. 		typedef list_node Node;
    28. 		typedef __list_const_iterator self;
    29. 		Node* _node;
    30. 		//迭代器构造
    31. 		__list_const_iterator(Node* node)
    32. 			:_node(node)
    33. 		{}
    34.  
    35. 		//前置
    36. 		//operator++
    37. 		self& operator++()
    38. 		{
    39. 			_node = _node->_next;
    40.             return *this;
    41. 		}
    42. 		//operator--
    43. 		self& operator--()
    44. 		{
    45. 			_node = _node->_prev;
    46.             return *this;
    47. 		}
    48.  
    49. 		//后置
    50. 		self operator++(int)
    51. 		{
    52. 			self* tmp(_node);
    53. 			_node = _node->_next;
    54. 			return tmp;
    55. 		}
    56. 		//operator--
    57. 		self operator--(int)
    58. 		{
    59. 			self* tmp(_node);
    60. 			_node = _node->_prev;
    61. 			return tmp;
    62. 		}
    63.  
    64. 		//operator*
    65. 		const T& operator*()
    66. 		{
    67. 			return _node->_data;
    68. 		}
    69. 		//operator->
    70. 		const T* operator->()
    71. 		{
    72. 			return &_node->_data;
    73. 		}
    74. 		//operator!=
    75. 		bool operator!=(const self& s)
    76. 		{
    77. 			return _node != s._node;
    78. 		}
    79. 		//operator==
    80. 		bool operator==(const self& s)
    81. 		{
    82. 			return _node == s._node;
    83. 		}
    84. 	};
    85.  
    86. 	//list结构
    87. 	template<class T>
    88. 	class list
    89. 	{
    90. 	public:
    91. 		typedef list_node Node;
    92. 		typedef __list_iterator iterator;
    93. 		typedef __list_const_iterator const_iterator;
    94. 	public:
    95. 		基本构造///
    96. 		//空初始化
    97. 		void empty_init()
    98. 		{
    99. 			_head = new Node;
    100. 			_head->_prev = _head;
    101. 			_head->_next = _head;
    102. 		}
    103. 		//构造
    104. 		list()
    105. 		{
    106. 			empty_init();
    107. 		}
    108. 		///正向迭代器
    109. 		iterator begin()
    110. 		{
    111. 			return iterator(_head->_next); //使用匿名对象进行构造
    112. 		}
    113. 		iterator end()
    114. 		{
    115. 			return iterator(_head);
    116. 		}
    117. 		const_iterator begin() const
    118. 		{
    119. 			return const_iterator(_head->_next);
    120. 		}
    121. 		const_iterator end() const
    122. 		{
    123. 			return const_iterator(_head);
    124. 		}
    125.  
    126. 	private:
    127. 		Node* _head;  //链表的头节点
    128. 		size_t _size; //节点个数
    129. 	};
    130. }

    2.3 正向迭代器的改进优化

    上面的这两种写法不难看出有很多代码都是重复出现的，使得代码非常冗余，那么怎么将这些冗余的代码进行合并呢？

    我们可以看一下库里面如何实现：

    采用泛型编程，使用模板，将这一转化的工作交给编译器，而我们只需传递const参数和非const参数即可：

    1. namespace ywh
    2. {
    3. 	//链表结构
    4. 	template<class T>
    5. 	struct list_node
    6. 	{
    7. 		T _data;                 //节点中的数据
    8. 		list_node* _prev;    //指向前一个节点的指针
    9. 		list_node* _next;    //指向后一个节点的指针
    10.  
    11. 		//构造
    12. 		list_node(const T& x = T())
    13. 			:_data(x)
    14. 			, _prev(nullptr)
    15. 			, _next(nullptr)
    16. 		{}
    17.  
    18. 	};
    19.  
    20. 	//非const正向迭代器
    21. 	//   类型模板参数   传递引用      传递指针
    22. 	template<class T, class Ref, class Ptr>
    23. 	struct __list_iterator
    24. 	{
    25. 		typedef list_node Node;
    26. 		typedef __list_iterator self;
    27. 		Node* _node;
    28. 		//迭代器构造
    29. 		__list_iterator(Node* node)
    30. 			:_node(node)
    31. 		{}
    32. 		
    33. 		//前置
    34. 		//operator++
    35. 		self& operator++()
    36. 		{
    37. 			_node = _node->_next;
    38.             return *this;
    39. 		}
    40. 		//operator--
    41. 		self& operator--()
    42. 		{
    43. 			_node = _node->_prev;
    44.             return *this;
    45. 		}
    46.  
    47. 		//后置
    48. 		self operator++(int)
    49. 		{
    50. 			self* tmp(_node);
    51. 			_node = _node->_next;
    52. 			return tmp;
    53. 		}
    54. 		//operator--
    55. 		self operator--(int)
    56. 		{
    57. 			self* tmp(_node);
    58. 			_node = _node->_prev;
    59. 			return tmp;
    60. 		}
    61.  
    62. 		//operator*
    63. 		Ref operator*()
    64. 		{
    65. 			return _node->_data;
    66. 		}
    67. 		//operator->
    68. 		Ptr operator->()
    69. 		{
    70. 			return &_node->_data;
    71. 		}
    72. 		//operator!=
    73. 		bool operator!=(const self& s)
    74. 		{
    75. 			return _node != s._node;
    76. 		}
    77. 		//operator==
    78. 		bool operator==(const self& s)
    79. 		{
    80. 			return _node == s._node;
    81. 		}
    82. 	};
    83.  
    84. 	//list结构
    85. 	template<class T>
    86. 	class list
    87. 	{
    88. 	public:
    89. 		typedef list_node Node;
    90. 		typedef __list_iterator iterator;   //非const迭代器
    91. 		typedef __list_iteratorconst T&, const T*> const_iterator;  //const迭代器
    92. 	public:
    93. 		基本构造///
    94. 		//空初始化
    95. 		void empty_init()
    96. 		{
    97. 			_head = new Node;
    98. 			_head->_prev = _head;
    99. 			_head->_next = _head;
    100. 		}
    101. 		//构造
    102. 		list()
    103. 		{
    104. 			empty_init();
    105. 		}
    106. 		///正向迭代器
    107. 		iterator begin()
    108. 		{
    109. 			return iterator(_head->_next); //使用匿名对象进行构造
    110. 		}
    111. 		iterator end()
    112. 		{
    113. 			return iterator(_head);
    114. 		}
    115. 		const_iterator begin() const
    116. 		{
    117. 			return const_iterator(_head->_next);
    118. 		}
    119. 		const_iterator end() const
    120. 		{
    121. 			return const_iterator(_head);
    122. 		}
    123.  
    124. 	private:
    125. 		Node* _head;  //链表的头节点
    126. 		size_t _size; //节点个数
    127. 	};
    128. }

    3. 修改相关接口

    3.1 insert、erase

    在pos位置进行插入删除比较简单，需要进行链接新节点，改变节点中指针的指向即可，库里面对于插入和删除都带有返回值，那么我们在实现的时候也加上返回值：

    1. ///修改相关接口
    2. 		//在pos位置插入节点
    3. 		iterator insert(iterator pos, const T& x)
    4. 		{
    5. 			//创建新新节点
    6. 			Node* newnode = new Node(x);
    7. 			//链接节点
    8. 			Node* cur = pos._node;
    9. 			Node* prev = cur->_prev;
    10. 			prev->_next = newnode;
    11. 			newnode->_prev = prev;
    12. 			newnode->_next = cur;
    13. 			cur->_prev = newnode;
    14. 			//更新节点个数
    15. 			++_size;
    16. 			//返回新节点的位置
    17. 			return iterator(newnode);
    18. 		}
    19. 		//删掉pos位置的节点
    20. 		iterator erase(iterator pos)
    21. 		{
    22. 			//保存相对位置
    23. 			Node* cur = pos._node;
    24. 			Node* prev = cur->_prev;
    25. 			Node* next = cur->_next;
    26. 			//链接节点
    27. 			delete cur;
    28. 			prev->_next = next;
    29. 			next->_prev = prev;
    30. 			//更新节点个数
    31. 			--_size;
    32. 			//返回pos的下一个位置
    33. 			return iterator(next);
    34. 		}

    在进行insert之后可以看到迭代器是不会失效的，但是在erase之后pos位置会被释放，因此erase之后迭代器会失效，在使用前先更新迭代器。

    3.2 尾插、头插、尾删、头删、清理

    当实现了insert和erase之后，实现这些接口直接复用即可：

    1.         //尾插
    2. 		void push_back(const T& x)
    3. 		{
    4. 			insert(end(), x);
    5. 		}
    6. 		//头插
    7. 		void push_front(const T& x)
    8. 		{
    9. 			insert(begin(), x);
    10. 		}
    11. 		//尾删
    12. 		void pop_back()
    13. 		{
    14. 			erase(--end());
    15. 		}
    16. 		//头删
    17. 		void pop_front()
    18. 		{
    19. 			erase(begin());
    20. 		}
    21. 		//清理
    22. 		void clear()
    23. 		{
    24. 			iterator it = begin();
    25. 			while (it != end())
    26. 			{
    27. 				it = erase(it);
    28. 			}
    29. 		}

    4. 拷贝构造、赋值重载、析构

    在这里我们都是采用现代写法：

     拷贝构造直接使用迭代器依次遍历进行尾插。

    1. //拷贝构造
    2. 		list(const list& lt)
    3. 		{
    4. 			//先创建空节点
    5. 			empty_init();
    6. 			//依次尾插即可
    7. 			for (auto e : lt)
    8. 			{
    9. 				push_back(e);
    10. 			}
    11. 		}
    12. 		//operator=
    13. 		void swap(list& lt)
    14. 		{
    15. 			std::swap(_head, lt._head);
    16. 			std::swap(_size, lt._size);
    17. 		}
    18. 		list& operator=(list lt)
    19. 		{
    20. 			swap(lt);
    21. 			return *this;
    22. 		}
    23. 		//析构
    24. 		~list()
    25. 		{
    26. 			clear();
    27. 			delete _head;
    28. 			_head = nullptr;
    29. 			_size = 0;
    30. 		}

    5. 完整代码

     头文件：List.h

    1. #pragma once
    2.  
    3. namespace ywh
    4. {
    5. 	//链表结构
    6. 	template<class T>
    7. 	struct list_node
    8. 	{
    9. 		T _data;                 //节点中的数据
    10. 		list_node* _prev;    //指向前一个节点的指针
    11. 		list_node* _next;    //指向后一个节点的指针
    12.  
    13. 		//构造
    14. 		list_node(const T& x = T())
    15. 			:_data(x)
    16. 			, _prev(nullptr)
    17. 			, _next(nullptr)
    18. 		{}
    19.  
    20. 	};
    21.  
    22. 	//非const正向迭代器
    23. 	//   类型模板参数   传递引用      传递指针
    24. 	template<class T, class Ref, class Ptr>
    25. 	struct __list_iterator
    26. 	{
    27. 		typedef list_node Node;
    28. 		typedef __list_iterator self;
    29. 		Node* _node;
    30. 		//迭代器构造
    31. 		__list_iterator(Node* node)
    32. 			:_node(node)
    33. 		{}
    34. 		
    35. 		//前置
    36. 		//operator++
    37. 		self& operator++()
    38. 		{
    39. 			_node = _node->_next;
    40. 			return *this;
    41. 		}
    42. 		//operator--
    43. 		self& operator--()
    44. 		{
    45. 			_node = _node->_prev;
    46. 			return *this;
    47. 		}
    48.  
    49. 		//后置
    50. 		self operator++(int)
    51. 		{
    52. 			self* tmp(_node);
    53. 			_node = _node->_next;
    54. 			return tmp;
    55. 		}
    56. 		//operator--
    57. 		self operator--(int)
    58. 		{
    59. 			self* tmp(_node);
    60. 			_node = _node->_prev;
    61. 			return tmp;
    62. 		}
    63.  
    64. 		//operator*
    65. 		Ref operator*()
    66. 		{
    67. 			return _node->_data;
    68. 		}
    69. 		//operator->
    70. 		Ptr operator->()
    71. 		{
    72. 			return &_node->_data;
    73. 		}
    74. 		//operator!=
    75. 		bool operator!=(const self& s)
    76. 		{
    77. 			return _node != s._node;
    78. 		}
    79. 		//operator==
    80. 		bool operator==(const self& s)
    81. 		{
    82. 			return _node == s._node;
    83. 		}
    84. 	};
    85.  
    86. 	//list结构
    87. 	template<class T>
    88. 	class list
    89. 	{
    90. 	public:
    91. 		typedef list_node Node;
    92. 		typedef __list_iterator iterator;   //非const迭代器
    93. 		typedef __list_iteratorconst T&, const T*> const_iterator;  //const迭代器
    94. 	public:
    95. 		基本构造///
    96. 		//空初始化
    97. 		void empty_init()
    98. 		{
    99. 			_head = new Node;
    100. 			_head->_prev = _head;
    101. 			_head->_next = _head;
    102. 		}
    103. 		//构造
    104. 		list()
    105. 		{
    106. 			empty_init();
    107. 		}
    108. 		//拷贝构造
    109. 		list(const list& lt)
    110. 		{
    111. 			//先创建空节点
    112. 			empty_init();
    113. 			//依次尾插即可
    114. 			for (auto e : lt)
    115. 			{
    116. 				push_back(e);
    117. 			}
    118. 		}
    119. 		//operator=
    120. 		void swap(list& lt)
    121. 		{
    122. 			std::swap(_head, lt._head);
    123. 			std::swap(_size, lt._size);
    124. 		}
    125. 		list& operator=(list lt)
    126. 		{
    127. 			swap(lt);
    128. 			return *this;
    129. 		}
    130. 		//析构
    131. 		~list()
    132. 		{
    133. 			clear();
    134. 			delete _head;
    135. 			_head = nullptr;
    136. 			_size = 0;
    137. 		}
    138. 		///正向迭代器
    139. 		iterator begin()
    140. 		{
    141. 			return iterator(_head->_next); //使用匿名对象进行构造
    142. 		}
    143. 		iterator end()
    144. 		{
    145. 			return iterator(_head);
    146. 		}
    147. 		const_iterator begin() const
    148. 		{
    149. 			return const_iterator(_head->_next);
    150. 		}
    151. 		const_iterator end() const
    152. 		{
    153. 			return const_iterator(_head);
    154. 		}
    155. 		///修改相关接口
    156. 		//在pos位置插入节点
    157. 		iterator insert(iterator pos, const T& x)
    158. 		{
    159. 			//创建新新节点
    160. 			Node* newnode = new Node(x);
    161. 			//链接节点
    162. 			Node* cur = pos._node;
    163. 			Node* prev = cur->_prev;
    164. 			prev->_next = newnode;
    165. 			newnode->_prev = prev;
    166. 			newnode->_next = cur;
    167. 			cur->_prev = newnode;
    168. 			//更新节点个数
    169. 			++_size;
    170. 			//返回新节点的位置
    171. 			return iterator(newnode);
    172. 		}
    173. 		//删掉pos位置的节点
    174. 		iterator erase(iterator pos)
    175. 		{
    176. 			//保存相对位置
    177. 			Node* cur = pos._node;
    178. 			Node* prev = cur->_prev;
    179. 			Node* next = cur->_next;
    180. 			//链接节点
    181. 			delete cur;
    182. 			prev->_next = next;
    183. 			next->_prev = prev;
    184. 			//更新节点个数
    185. 			--_size;
    186. 			//返回pos的下一个位置
    187. 			return iterator(next);
    188. 		}
    189. 		//尾插
    190. 		void push_back(const T& x)
    191. 		{
    192. 			insert(end(), x);
    193. 		}
    194. 		//头插
    195. 		void push_front(const T& x)
    196. 		{
    197. 			insert(begin(), x);
    198. 		}
    199. 		//尾删
    200. 		void pop_back()
    201. 		{
    202. 			erase(--end());
    203. 		}
    204. 		//头删
    205. 		void pop_front()
    206. 		{
    207. 			erase(begin());
    208. 		}
    209. 		//清理
    210. 		void clear()
    211. 		{
    212. 			iterator it = begin();
    213. 			while (it != end())
    214. 			{
    215. 				it = erase(it);
    216. 			}
    217. 		}
    218. 		//节点个数
    219. 		size_t size()
    220. 		{
    221. 			return _size;
    222. 		}
    223. 	private:
    224. 		Node* _head;  //链表的头节点
    225. 		size_t _size; //节点个数
    226. 	};
    227. }

    朋友们、伙计们，美好的时光总是短暂的，我们本期的的分享就到此结束，欲知后事如何，请听下回分解~，最后看完别忘了留下你们弥足珍贵的三连喔，感谢大家的支持！  

  • 相关阅读:
    史上最全面试题版！看完吊打面试官！七夕来袭！是时候展现专属于程序员的浪漫了 10万字+
    Kernel: 宏：__KERNEL__
    从传统到智能 | 拓世法宝AI智能直播一体机为商家注入活力
    二叉树的顺序结构及实现
    Vue - 快速入门，这一套就够了！（Vue core + 案例 + 效果演示）
    C++-Cmake指令：find_library【该命令用于查找库（动态库或者静态库），当构建依赖于第三方库/系统库，可以使用该命令来查找并使用库】
    合伙保密协议
    小白学习spring第四天
    Centos7的系统管理(systemctl、系统运行级别、关机)
    Tomcat安装步骤及详细配置教程（2022最新版）
  • 原文地址：https://blog.csdn.net/Yikefore/article/details/134090437