Partage de technologie

L'implémentation sous-jacente du conteneur de liste C

2024-07-12

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

1. Qu'est-ce qu'une liste ?

List est une liste à double titre dans un conteneur C++. Le nœud principal ne stocke pas les données. L'élément suivant du nœud principal est le premier élément qui stocke les données. L'élément précédent du nœud principal est connecté au dernier élément qui stocke les données. données. (La structure est illustrée dans la figure ci-dessous)

La structure de chaque nœud de la liste chaînée est divisée en partie données, pointeur avant et pointeur arrière (ce qui suit est le diagramme de structure et le code)

2. Répertorier l'implémentation du code et l'analyse syntaxique

2.1 Définir la structure du nœud

Les types de données et les pointeurs avant et arrière dans la liste chaînée sont générés par des modèles et peuvent être adaptés aux types intégrés et aux types personnalisés.La raison pour laquelle struct est utilisé pour définir la classe ici est que les types de variables membres par défaut de struct sont publics et que d'autres fonctions peuvent être facilement appelées.Il y a aussi ici un constructeur list_node T(), qui est une variable anonyme. Sa fonction n'est pas seulement utilisée pour stocker des données. De plus, si aucun paramètre n'est écrit lors de l'appel du constructeur list_node, il y aura également une valeur par défaut ici.

2.2 Définir la structure de la liste chaînée

Dans la liste, il y a deux variables membres : _node, un pointeur vers le type de nœud, et _size, qui calcule le nombre de nœuds.

  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 Ajouter une fonction de liste chaînée (insérer push_back)

Nous avons défini la structure de base de la liste et nous allons maintenant ajouter quelques fonctions de base, telles que l'insertion de données dans la liste et l'utilisation d'itérateurs pour parcourir la liste.

Fonction Push_back : construisez d'abord un nouveau nœud newnode, puis stockez les données X qui doivent être stockées dans le nouveau nœud, recherchez le nœud de queue et insérez le nouveau nœud dans le nœud à côté du nœud de queue.

  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 Ajouter une fonction de liste chaînée (surcharge d'itérateur et d'opérateur d'itérateur)

Différent de la liste de séquences, car les nœuds de la liste chaînée ne sont pas stockés ensemble dans un espace continu, le ++ et le déréférencement du pointeur ne peuvent pas obtenir directement les données, nous devons donc ici surcharger * -&gt; ++ -- etc. . etc. opérateur.

  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. }

Après avoir terminé les opérations ci-dessus, nous pouvons déboguer le programme comme ceci. Bien que List ne soit pas un tableau, nous pouvons accéder aux éléments à l'intérieur de List de la même manière.Bien que les itérateurs parcourent chaque élément du conteneur de la même manière, ils protègent les détails d'implémentation sous-jacents et fournissent une méthode d'accès unifiée.。

  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 Ajouter une fonction de liste chaînée (mettre à niveau la suppression de insert() et Eraser() de l'opération d'insertion)

Tout d'abord, nous pouvons écrire une fonction insert(). Cette fonction peut être réutilisée par d'autres fonctions telles que push_back et push_front, et peut également insérer des données à n'importe quel endroit.

  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 Ajouter une fonction de liste chaînée (fonction d'effacement et destructeur)

Étant donné que la valeur de retour de la fonction d'effacement est la position suivante des données supprimées, donc ne pas écrire ++ ici aura l'effet 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 Ajouter une fonction de liste chaînée (construction de copie et surcharge d'affectation)

(1) Copier la structure

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

(2) Surcharge d'affectation

  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 Itérateurs de type const

Pour les itérateurs de type const, nous devons comprendre :Les itérateurs de type const ne peuvent pas modifier les données pointées par l'itérateur, mais l'itérateur lui-même ne peut pas être modifié.L'itérateur lui-même doit effectuer ++, -- et d'autres opérations pour effectuer des opérations de parcours, donc lors de l'écriture d'un itérateur de type const, j'apporte uniquement des modifications const à la fonction que l'itérateur renvoie au contenu pointé, et les autres fonctions restent inchangé.

  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. Code complet

  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. }

Profil personnel

Il se consacre à la recherche technologique depuis plus de 30 ans et maîtrise divers langages tels que java, linux, javascript, php, css, etc. Il a apporté de nombreuses contributions dans le domaine de l'open source. station de documentation pour les développeurs pour partager certains problèmes de développement technologique pour référence future.

mes coordonnées

Mail