技術共有

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. template<class T>
  15. class list
  16. {
  17. typedef list_node<T> Node;
  18. void empty_init()
  19. {
  20. _head = new Node;
  21. _head -> next = _head;
  22. _head -> prev = _head;
  23. _size = 0;
  24. }
  25. list()
  26. {
  27. empty_init();
  28. }
  29. void push_back(const T& x)
  30. {
  31. Node* newnode = new Node(x);
  32. Node* tail = _head->prev;
  33. tail->_next = newnode;
  34. newnode->prev = tail;
  35. newnode->_next = _head;
  36. _head->prev = newnode;
  37. _size++;
  38. }
  39. private:
  40. Node* _node;
  41. size_t _size;
  42. }

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. template<class T>
  15. struct __list_iterator
  16. {
  17. typedef list_node<T> Node;
  18. typedef __list_iterator self;
  19. Node* _node;
  20. __list_iterator(Node* node)
  21. :_node(node)
  22. {
  23. }
  24. T& operator *(Node * node)
  25. {
  26. return _node->_data;
  27. }
  28. T* operator(Node * node)
  29. {
  30. return &_node->_data;
  31. }
  32. self& operator++()
  33. {
  34. _node = _node->next;
  35. return *this;
  36. }
  37. self& operator--()
  38. {
  39. _node = _node->prev;
  40. return *this;
  41. }
  42. bool operator!=(const self& s)
  43. {
  44. return _node != s._node;
  45. }
  46. }
  47. template<class T>
  48. class list
  49. {
  50. typedef list_node<T> Node;
  51. typedef __list_iterator<T> iterator;
  52. iterator begin()
  53. {
  54. return iterator(_head->next);
  55. }
  56. iterator end()
  57. {
  58. return iterator(_head);
  59. }
  60. void empty_init()
  61. {
  62. _head = new Node;
  63. _head -> next = _head;
  64. _head -> prev = _head;
  65. _size = 0;
  66. }
  67. list()
  68. {
  69. empty_init();
  70. }
  71. void push_back(const T& x)
  72. {
  73. Node* newnode = new Node(x);
  74. Node* tail = _head->prev;
  75. tail->_next = newnode;
  76. newnode->prev = tail;
  77. newnode->_next = _head;
  78. _head->prev = newnode;
  79. _size++;
  80. }
  81. private:
  82. Node* _node;
  83. size_t _size;
  84. }

上記の操作が完了したら、次のようにプログラムをデバッグできます。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. while(it != lt.end())
  9. {
  10. cout << *it << " ";
  11. ++it;
  12. }
  13. cout<< endl;
  14. }

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. prev->_next = newnode;
  7. newnode->_prev = prev;
  8. newnode->_next = cur;
  9. cur->_prev = newnode;
  10. return newnode;
  11. }
  12. iterator erase(iterator pos)
  13. {
  14. Node* cur = pos._node;
  15. Node* prev = cur->_prev;
  16. Node* next = cur->_next;
  17. delete cur;
  18. prev->_next = next;
  19. next->_prev = prev;
  20. return next;
  21. }
  22. void push_back(const T& x)
  23. {
  24. insert(this.end(),x);
  25. }
  26. void push_front(const T& x)
  27. {
  28. insert(begin(),x);
  29. }
  30. void pop_back()
  31. {
  32. erase(--end());
  33. }
  34. void pop_front()
  35. {
  36. erase(begin());
  37. }

2.6 リンクリスト機能の追加(clear関数とデストラクタ)

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

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

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. const T& operator *()
  12. {
  13. return _node->_data;
  14. }
  15. const T* operator->()
  16. {
  17. return &_node->_data;
  18. }
  19. };

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