技術共有

C リスト コンテナの基礎となる実装

2024-07-12

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

1. リストとは何ですか?

リストは、C++ コンテナーの先頭の二重リンク リストです。ヘッド ノードはデータを格納しません。ヘッド ノードの前の要素は、データを格納する最後の要素に接続されます。データ。 (構造は下図に示します)

リンクリストの各ノードの構造はデータ部、フロントポインタ、バックポインタに分かれます（以下は構造図とコードです）

2. リストコードの実装と構文解析

2.1 ノードの構造を定義する

リンクされたリスト内のデータのタイプと前方および後方ポインターはテンプレートによって生成され、組み込みタイプおよびカスタム・タイプに適合させることができます。ここでクラスの定義に struct を使用する理由は、struct のデフォルトのメンバー変数の型が public であり、他の関数を簡単に呼び出すことができるためです。ここには、匿名変数である list_node コンストラクター T() もあります。さらに、list_node コンストラクターを呼び出すときにパラメーターが書き込まれない場合、その関数はここにデフォルト値も存在します。

2.2 リンクリストの構造を定義する

リストには 2 つのメンバー変数があります。_node (ノード タイプへのポインター) と _size (ノードの数を計算する) です。

  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 リンクリスト機能の追加（push_backの挿入）

リストの基本構造を定義しました。次に、リストへのデータの挿入やリストの走査にイテレータを使用するなど、いくつかの基本的な関数を追加します。

Push_back 関数: まず新しいノード newnode を構築し、次に newnode に格納する必要があるデータ X を格納し、末尾ノードを見つけて末尾ノードの隣のノードに newnode を挿入します。

  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 リンクリスト関数の追加（反復子および反復演算子のオーバーロード）

シーケンスリストとは異なり、リンクリストのノードは連続した空間にまとめて格納されていないため、++やポインタの逆参照では直接データを取得することができないため、ここでは* -&gt; ++ --などをオーバーロードする必要があります。などの演算子。

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

上記の操作が完了したら、次のようにプログラムをデバッグできます。List は配列ではありませんが、同様の方法で List 内の要素にアクセスできます。イテレータはコンテナの各要素を同じ方法で繰り返しますが、イテレータは基礎となる実装の詳細を保護し、統一されたアクセス方法を提供します。。

  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 リンクリスト機能の追加（挿入操作のinsert()とeraser()の削除をアップグレード）

まず、insert() 関数を作成します。この関数は、push_back や Push_front などの他の関数で再利用でき、任意の場所にデータを挿入することもできます。

  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 リンクリスト機能の追加（clear関数とデストラクタ）

Erase 関数の戻り値は削除されたデータの次の位置になるため、ここに ++ を書かないと ++ の効果が生じます。

  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 リンクリスト機能の追加（コピー構築と代入のオーバーロード）

(1) コピー構造

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

(2) 代入のオーバーロード

  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 const型のイテレータ

const 型イテレータについては、次のことを理解する必要があります。const 型のイテレータは、イテレータが指すデータを変更できませんが、イテレータ自体を変更することはできません。イテレータ自体は、トラバーサル操作を実行するために ++、-、およびその他の操作を完了する必要があるため、const 型イテレータを作成するときは、イテレータが指すコンテンツに返す関数に対してのみ const 変更を行い、他の関数はそのまま残ります。変更なし。

  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. 完全なコード

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

個人プロフィール

彼は 30 年以上テクノロジーの研究に専念しており、java、linux、javascript、php、css などのさまざまな言語に堪能であり、オープンソース分野で多くの貢献を行っています。将来の参考のために技術開発におけるいくつかの問題を共有する開発者ドキュメント ステーション。

プライベートな連絡先の最初の情報

送料