Compartilhamento de tecnologia

A implementação subjacente do contêiner da lista C

2024-07-12

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

1. O que é lista?

Lista é uma lista duplamente encadeada em um contêiner C++. O nó principal não armazena dados. O próximo elemento do nó principal é o primeiro elemento que armazena dados. dados. (A estrutura é mostrada na figura abaixo)

A estrutura de cada nó na lista vinculada é dividida em parte de dados, ponteiro frontal e ponteiro traseiro (a seguir está o diagrama de estrutura e o código)

2. Listar implementação de código e análise de sintaxe

2.1 Defina a estrutura do nó

Os tipos de dados e ponteiros frontais e traseiros na lista vinculada são gerados por modelos e podem ser adaptados para tipos integrados e personalizados.A razão pela qual struct é usado para definir a classe aqui é que os tipos de variáveis ​​de membro padrão de struct são públicos e outras funções podem ser facilmente chamadas.Há também um construtor list_node T() aqui, que é uma variável anônima. Sua função não é usada apenas para armazenar dados. Além disso, se nenhum parâmetro for escrito ao chamar o construtor list_node, também haverá um valor padrão aqui.

2.2 Defina a estrutura da lista vinculada

Na lista, há duas variáveis ​​de membro: _node, um ponteiro para o tipo de nó, e _size, que calcula o número de nós.

  1. template<class T>
  2. class list
  3. {
  4. typedef list_node<T> Node;
  5. void empty_init()
  6. {
  7.     _head = new Node;
  8.     _head -> next = _head;
  9.     _head -> prev = _head;
  10.     _size = 0;
  11. }
  12. list()
  13. {
  14.     empty_init();
  15. }
  16.     private:
  17.         Node* _node;
  18.         size_t _size;
  19. }

2.3 Adicionar função de lista vinculada (inserir push_back)

Definimos a estrutura básica da lista e agora adicionaremos algumas funções básicas, como inserir dados na lista e usar iteradores para percorrer a lista.

Função push_back: primeiro construa um novo nó newnode, em seguida, armazene os dados X que precisam ser armazenados no newnode, encontre o nó final e insira o newnode no nó próximo ao nó final.

  1. template<class T>
  2. struct list_node
  3. {
  4. 	T _data;
  5. 	list_node<T>* _next;
  6. 	list_node<T>* _prev;
  7. 	list_node(const T& x=T())
  8. 		:_data(x)
  9. 		, _next(nullptr)
  10. 		, _prev(nullptr)
  11. 	{
  12.  
  13. 	}
  14. };
  15.  
  16. template<class T>
  17. class list
  18. {
  19. typedef list_node<T> Node;
  20. void empty_init()
  21. {
  22.     _head = new Node;
  23.     _head -> next = _head;
  24.     _head -> prev = _head;
  25.     _size = 0;
  26. }
  27. list()
  28. {
  29.     empty_init();
  30. }
  31. void push_back(const T& x)
  32. {
  33.     Node* newnode = new Node(x);
  34.     Node* tail = _head->prev;
  35.  
  36.     tail->_next = newnode;
  37.     newnode->prev = tail;
  38.  
  39.     newnode->_next = _head;
  40.     _head->prev = newnode;
  41.     
  42.     _size++; 
  43. }
  44.     private:
  45.         Node* _node;
  46.         size_t _size;
  47. }

2.4 Adicionar função de lista vinculada (sobrecarga de iterador e operador de iterador)

Diferente da lista de sequência, porque os nós da lista vinculada não são armazenados juntos em um espaço contínuo, o ++ e a desreferência do ponteiro não podem obter os dados diretamente, então aqui precisamos sobrecarregar * -&gt; ++ - etc. operador.

  1. template<class T>
  2. struct list_node
  3. {
  4. 	T _data;
  5. 	list_node<T>* _next;
  6. 	list_node<T>* _prev;
  7. 	list_node(const T& x=T())
  8. 		:_data(x)
  9. 		, _next(nullptr)
  10. 		, _prev(nullptr)
  11. 	{
  12.  
  13. 	}
  14. };
  15. template<class T>
  16. struct __list_iterator
  17. {
  18.     typedef list_node<T> Node;
  19.     typedef __list_iterator self;
  20.  
  21.     Node* _node;
  22.     __list_iterator(Node* node)
  23.         :_node(node)
  24.     {
  25.  
  26.     }
  27.     
  28.     T& operator *(Node * node)
  29.     {
  30.         return _node->_data;
  31.     }
  32.  
  33.     T* operator(Node * node)
  34.     {
  35.         return &_node->_data;
  36.     }
  37.     self& operator++()
  38.     {
  39.         _node = _node->next;
  40.         return *this;
  41.     }
  42.     
  43.     self& operator--()
  44.     {
  45.         _node = _node->prev;
  46.         return *this;
  47.     }
  48.  
  49.     bool operator!=(const self& s)
  50.     {
  51.         return _node != s._node;
  52.     }
  53. }
  54.  
  55. template<class T>
  56. class list
  57. {
  58. typedef list_node<T> Node;
  59. typedef __list_iterator<T> iterator;
  60.  
  61. iterator begin()
  62. {
  63.     return iterator(_head->next);
  64. }
  65.  
  66. iterator end()
  67. {
  68.     return iterator(_head);
  69. }
  70.  
  71. void empty_init()
  72. {
  73.     _head = new Node;
  74.     _head -> next = _head;
  75.     _head -> prev = _head;
  76.     _size = 0;
  77. }
  78.  
  79. list()
  80. {
  81.     empty_init();
  82. }
  83.  
  84. void push_back(const T& x)
  85. {
  86.     Node* newnode = new Node(x);
  87.     Node* tail = _head->prev;
  88.  
  89.     tail->_next = newnode;
  90.     newnode->prev = tail;
  91.  
  92.     newnode->_next = _head;
  93.     _head->prev = newnode;
  94.     
  95.     _size++; 
  96. }
  97.     private:
  98.         Node* _node;
  99.         size_t _size;
  100. }

Depois de concluir as operações acima, podemos depurar o programa assim. Embora List não seja um array, podemos acessar os elementos dentro de List de maneira semelhante.Embora os iteradores iterem cada elemento do contêiner da mesma maneira, os iteradores protegem os detalhes de implementação subjacentes e fornecem um método de acesso unificado.。

  1. test_list()
  2. {
  3.     list<int> lt;
  4.     lt.push_back(1);
  5.     lt.push_back(2);
  6.     lt.push_back(3);
  7.     list<int>::iterator it = lt.begin();
  8.  
  9.     while(it != lt.end())
  10.     {
  11.         cout << *it << " ";
  12.         ++it;
  13.     }
  14.     cout<< endl;
  15. }

2.5 Adicionar função de lista vinculada (atualizar inserção () e exclusão de borracha () da operação de inserção)

Primeiro, podemos escrever uma função insert(). Esta função pode ser reutilizada por outras funções, como push_back e push_front, e também pode inserir dados em qualquer local.

  1. iterator insert(iterator pos , const T& x)
  2. {
  3.     Node* newnode = new Node(x);
  4.     Node* cur = pos._node;
  5.     Node* prev = cur ->_prev;
  6.     
  7.     prev->_next = newnode;
  8.     newnode->_prev = prev;
  9.     newnode->_next = cur;
  10.     cur->_prev = newnode;
  11.  
  12.     return newnode; 
  13. }
  14.  
  15. iterator erase(iterator pos)
  16. {
  17.     Node* cur = pos._node;
  18.     Node* prev = cur->_prev;
  19.     Node* next = cur->_next;
  20.  
  21.     delete cur;
  22.     prev->_next = next;
  23.     next->_prev = prev;
  24.  
  25.     return next;
  26. }
  27.  
  28. void push_back(const T& x)
  29. {
  30.     insert(this.end(),x);
  31. }
  32.  
  33. void push_front(const T& x)
  34. {
  35.     insert(begin(),x);
  36. }
  37.  
  38. void pop_back()
  39. {
  40.     erase(--end());
  41. }
  42.  
  43. void pop_front()
  44. {
  45.     erase(begin());
  46. }

2.6 Adicionar função de lista vinculada (função limpar e destruidor)

Como o valor de retorno da função apagar é a próxima posição dos dados excluídos, não escrever ++ aqui terá o efeito de ++.

  1. ~list()
  2. {
  3.     clear();
  4.     delete _head;
  5.     _head = nullpre;
  6. }
  7.  
  8. void clear()
  9. {
  10.     iterator it = begin();
  11.     while(it != end())
  12.     {
  13.         it = erase(*it);
  14.     }
  15. }

2.7 Adicionar função de lista vinculada (construção de cópia e sobrecarga de atribuição)

(1) Copiar estrutura

  1. list( list<int> lt )
  2. {
  3.     empty_init();
  4.     for(auto e : lt)
  5.     {
  6.         this.push_back(e);
  7.     }
  8. }

(2) Sobrecarga de tarefas

  1. 		void swap(list<T>& lt)
  2. 		{
  3. 			std::swap(_head, lt._head);
  4. 			std::swap(_size, lt._size);
  5. 		}
  6. 		list<int>& operator=(list<int> lt)
  7. 		{
  8. 			swap(lt);
  9. 			return *this;
  10. 		}

2.8 Iteradores do tipo const

Para iteradores do tipo const, precisamos entender,Iteradores do tipo const não podem modificar os dados apontados pelo iterador, mas o próprio iterador não pode ser modificado.O próprio iterador precisa completar ++, -- e outras operações para realizar operações de travessia, portanto, ao escrever um iterador do tipo const, eu apenas faço modificações const na função que o iterador retorna ao conteúdo apontado, e as outras funções permanecem inalterado.

  1. template<class T>
  2. struct __list_const_iterator
  3. {
  4. 	typedef list_node<T> Node;
  5. 	typedef __list_const_iterator<T> self;
  6. 	Node* _node;
  7. 	__list_const_iterator(Node* node)
  8. 		:_node(node)
  9. 	{
  10.  
  11. 	}
  12. 	
  13. 	const T& operator *()
  14. 	{
  15. 		return _node->_data;
  16. 	}
  17. 	const T* operator->()
  18. 	{
  19. 		return &_node->_data;
  20. 	}
  21. };

3. Código completo

  1. #pragma once
  2. #include<iostream>
  3. using namespace std;
  4. namespace hjy
  5. {
  6. 	template<class T>
  7. 	struct list_node
  8. 	{
  9. 		T _data;
  10. 		list_node<T>* _next;
  11. 		list_node<T>* _prev;
  12. 		list_node(const T& x=T())
  13. 			:_data(x)
  14. 			, _next(nullptr)
  15. 			, _prev(nullptr)
  16. 		{
  17.  
  18. 		}
  19. 	};
  20. 	template<class T,class Ref,class Ptr>
  21. 	struct __list_iterator
  22. 	{ 
  23. 		typedef list_node<T> Node;
  24. 		typedef __list_iterator<T,Ref,Ptr> self;
  25. 		Node* _node;
  26. 		__list_iterator(Node* node)
  27. 			:_node(node)
  28. 		{
  29.  
  30. 		}
  31. 		self& operator ++()
  32. 		{
  33. 			_node = _node->_next;
  34. 			return *this;
  35. 		}
  36. 		self& operator --()
  37. 		{
  38. 			_node = _node->_prev;
  39. 			return *this;
  40. 		}
  41. 		self operator ++(int)
  42. 		{
  43. 			self tmp(*this);
  44. 			_node = _node->_next;
  45. 			return tmp;
  46. 		}
  47. 		self operator --(int)
  48. 		{
  49. 			self tmp(*this);
  50. 			_node = _node->_prev;
  51. 			return tmp;
  52. 		}
  53. 		Ref operator *()
  54. 		{
  55. 			return _node->_data;
  56. 		}
  57. 		Ptr operator->()
  58. 		{
  59. 			return &_node->_data;
  60. 		}
  61. 		bool operator!=(const self& s)
  62. 		{
  63. 			return _node != s._node;
  64. 		}
  65. 	};
  66. 	/*template<class T>
  67. 	struct __list_const_iterator
  68. 	{
  69. 		typedef list_node<T> Node;
  70. 		typedef __list_const_iterator<T> self;
  71. 		Node* _node;
  72. 		__list_const_iterator(Node* node)
  73. 			:_node(node)
  74. 		{
  76. 		}
  77. 		self& operator ++()
  78. 		{
  79. 			_node = _node->_next;
  80. 			return *this;
  81. 		}
  82. 		self& operator --()
  83. 		{
  84. 			_node = _node->_prev;
  85. 			return *this;
  86. 		}
  87. 		self operator ++(int)
  88. 		{
  89. 			self tmp(*this);
  90. 			_node = _node->_next;
  91. 			return tmp;
  92. 		}
  93. 		self operator --(int)
  94. 		{
  95. 			self tmp(*this);
  96. 			_node = _node->_prev;
  97. 			return tmp;
  98. 		}
  99. 		const T& operator *()
  100. 		{
  101. 			return _node->_data;
  102. 		}
  103. 		const T* operator->()
  104. 		{
  105. 			return &_node->_data;
  106. 		}
  107. 		bool operator!=(const self& s)
  108. 		{
  109. 			return _node != s._node;
  110. 		}
  111. 	};*/
  112. 	template<class T>
  113. 	class list
  114. 	{
  115. 		typedef list_node<T>  Node;
  116. 	public:
  117. 		typedef __list_iterator<T,T&,T*> iterator;
  118. 		typedef __list_iterator<T, const T&, const T*> const_iterator;
  119. 		//typedef __list_const_iterator<T> const_iterator;
  120.  
  121. 		const_iterator begin()const
  122. 		{
  123. 			return const_iterator(_head->_next);
  124. 		}
  125. 		const_iterator end()const
  126. 		{
  127. 			return const_iterator(_head);
  128. 		}
  129.  
  130. 		iterator begin()
  131. 		{
  132. 			return _head->_next;
  133. 		}
  134. 		iterator end()
  135. 		{
  136. 			return _head;
  137. 		}
  138. 		void empty_init()
  139. 		{
  140. 			_head = new Node;
  141. 			_head->_next = _head;
  142. 			_head->_prev = _head;
  143. 			_size = 0;
  144. 		}
  145. 		list()
  146. 		{
  147. 			empty_init();
  148. 		}
  149. 		//list<int>& operator=(const list<int>& lt) 传统写法
  150. 		//{
  151. 		//	if (this != &lt)
  152. 		//		clear();
  153. 		//	for (auto e : lt)
  154. 		//	{
  155. 		//		push_back(e);
  156. 		//	}
  157. 		//	return *this;
  158. 		//}
  159. 		void swap(list<T>& lt)
  160. 		{
  161. 			std::swap(_head, lt._head);
  162. 			std::swap(_size, lt._size);
  163. 		}
  164. 		list<int>& operator=(list<int> lt)
  165. 		{
  166. 			swap(lt);
  167. 			return *this;
  168. 		}
  169. 		~list()
  170. 		{
  171. 			clear();
  172. 			delete _head;
  173. 			_head = nullptr;
  174. 		}
  175. 		//list(const list<T>& lt)//没有const迭代器所以这样写不行
  176. 		//{
  177. 		//	empty_init();
  178. 		//	for (auto e : lt)
  179. 		//	{
  180. 		//		push_back(e);
  181. 		//	}
  182. 		//}
  183. 		list( list<T>& lt)
  184. 		{
  185. 			empty_init();
  186. 			for (auto e : lt)
  187. 			{
  188. 				push_back(e);
  189. 			}
  190. 		}
  191. 		void push_back(const T& x)
  192. 		{
  193. 			insert(end(), x);
  194. 		}
  195. 		void push_front(const T& x)
  196. 		{
  197. 			insert(begin(), x);
  198. 		}
  199. 		void pop_front()
  200. 		{
  201. 			erase(begin());
  202. 		}
  203. 		void pop_back()
  204. 		{
  205. 			erase(end()--);
  206. 		}
  207. 		void clear()
  208. 		{
  209. 			iterator it = begin();
  210. 			while (it != end())
  211. 			{
  212. 				it = erase(it);
  213. 			}
  214. 		}
  215. 		iterator insert(iterator pos, const T& val)
  216. 		{
  217. 			Node* cur = pos._node;
  218. 			Node* newnode = new Node(val);
  219. 			Node* prev = cur->_prev;
  220. 			prev->_next = newnode;
  221. 			newnode->_prev = prev;
  222. 			newnode->_next = cur;
  223. 			cur->_prev = newnode;
  224. 			++_size;
  225. 			return iterator(newnode);
  226. 		}
  227. 		iterator erase(iterator pos)
  228. 		{
  229. 			Node* cur = pos._node;
  230. 			Node* prev = cur->_prev;
  231. 			Node* next = cur->_next;
  232. 			delete cur;
  233. 			prev->_next = next;
  234. 			next->_prev = prev;
  235. 			--_size;
  236. 			return iterator(next);
  237. 		}
  238. 		size_t size()
  239. 		{
  240. 			return _size;
  241. 		}
  242. 	private:
  243. 		Node* _head;
  244. 		size_t _size;
  245. 	};
  246. 	void test_list1()
  247. 	{
  248. 		list<int>lt;
  249. 		lt.push_back(1);
  250. 		lt.push_back(2);
  251. 		lt.push_back(3);
  252. 		lt.push_back(4);
  253. 		lt.push_back(5);
  254. 		for (auto e : lt)
  255. 			cout << e << " ";
  256. 		cout << endl;
  257.  
  258. 		list<int>lt1 = lt;
  259. 		for (auto e : lt1)
  260. 			cout << e << " ";
  261. 		cout << endl;
  262.  
  263. 	}
  264. 	/*void print_list(const list<int>& lt)
  265. 	{
  266. 		list<int>::const_iterator it = lt.begin();
  267. 		while (it != lt.end())
  268. 		{
  269. 			cout << *it << " ";
  270. 			++it;
  271. 		}
  272. 		cout << endl;
  273. 		for (auto e : lt)
  274. 		{
  275. 			cout << e << " ";
  276. 		}
  277. 		cout << endl;
  278. 	}*/
  279. 	template<typename T>
  280. 	void print_list(const list<T>& lt)
  281. 	{
  282. 		typename list<T>::const_iterator it = lt.begin();
  283. 		while (it != lt.end())
  284. 		{
  285. 			cout << *it << " ";
  286. 			++it;
  287. 		}
  288. 		cout << endl;
  289. 	}
  290. 	void test_list2()
  291. 	{
  292. 		list<string>lt;
  293. 		lt.push_back("111");
  294. 		lt.push_back("111");
  295. 		lt.push_back("111");
  296. 		print_list(lt);
  297. 	}
  298. }

Perfil pessoal

Ele se dedica à pesquisa de tecnologia há mais de 30 anos e é proficiente em diversas linguagens como java, linux, javascript, php, css, etc. estação de documentação do desenvolvedor para compartilhar alguns problemas no desenvolvimento de tecnologia para referência futura.

minhas informações de contato

Correspondência