C++ STL：从零开始模仿实现 list 容器

引言

C++ 标准模板库(STL)中的 list 是一个双向链表容器，它提供了高效的插入和删除操作。本文将领导你一步步实现一个简化版的 list 容器，帮助你深入理解其底层原理和设计头脑。
1. 疑难点解析

1.1 迭代器类为什么设置三个模版参数？

   为了区分 list 的 const类 和 平凡类 ，我们都知道 const类 的变量是不能修改内部值的，就算用指针也不行。而我们的迭代器也恰好是在模仿指针的举动，所以指针不能修改 const类 变量，我们的迭代器也不行。
为了区分对 const类 的 list（只读） 和 平凡类list（可读可写）的区别，我们需要另一个能做到对容器只读不写的 const类迭代器 ，我们最好的方式便是写两个基本一样的迭代器类（一份供平凡类list调用的平凡迭代器类，一份供const类list调用的const类的迭代器）。
但如许既欠好修改又欠好调试，而在有了模版之后，我们便可以将写两份代码的工作交给编译器去实现（俗称模版实例化，根据传入参数差别，模版可以实例化为多个差别类），所以我们就多加了一个模版参数Ref，根据 list 传入的范例差别，从而区分实例化为 const类 的迭代器照旧 平凡类 ，而又因为我们迭代器可以用 * 和 -> 两种操作符访问，且两操作符的返回值又各差别，所以 迭代器模版 又多加一个 Ptr ，以区分 ->运算符重载函数 对 const类 和 平凡类 的访问。
  2. 完备源码

1. #include<assert.h>
3. namespace dza {
4.         // 惯例：当成员变量和成员函数全部是公有的时候，一般用struct
5.         // struct 与 class没有区别
6.         template<class T>
7.         struct list_node {
8.                 T _data;
9.                 list_node<T>* _next;
10.                 list_node<T>* _prev;
12.                 list_node(const T& x = T())
13.                         :_data(x)
14.                         , _next(nullptr)
15.                         , _prev(nullptr)
16.                 {}
17.         };
19.         // 单一参数的模板
20.         //template<class T>
21.         //struct list_iterator {
22.         //        typedef list_node<T> Node;
23.         //        // 定义一个迭代器Self
24.         //        typedef list_iterator<T> Self;
25.         //        Node* _node;
27.         //        list_iterator(Node* node)
28.         //                :_node(node)
29.         //        {}
31.         //        // 解引用的重载
32.         //        T& operator*()
33.         //        {
34.         //                return _node->_data;
35.         //        }
37.         //        // 公共函数。域内都可以使用
38.         //        T* operator->()
39.         //        {
40.         //                return &_node->_data;
41.         //        }
43.         //        // 迭代器的实现
44.         //        Self& operator++()
45.         //        {
46.         //                _node = _node->_next;
47.         //                return *this;
48.         //        }
50.         //        Self& operator--()
51.         //        {
52.         //                _node = _node->_prev;
53.         //                return *this;
54.         //        }
56.         //        Self operator++(int)
57.         //        {
58.         //                Self tmp(*this);
59.         //                _node = _node->_next;
60.         //                return tmp;
61.         //        }
63.         //        Self operator--(int)
64.         //        {
65.         //                Self tmp(*this);
66.         //                _node = _node->_prev;
67.         //                return tmp;
68.         //        }
70.         //        bool operator!=(const Self& s)
71.         //        {
72.         //                return _node != s._node;
73.         //        }
75.         //        bool operator==(const Self& s)
76.         //        {
77.         //                return _node == s._node;
78.         //        }
79.         //};
81.                 // 模板里面的多参数
82.                 template<class T,class Ref,class Ptr>
83.                 struct list_iterator {
84.                         typedef list_node<T> Node;
85.                         // 定义一个迭代器Self
86.                         typedef list_iterator<T,Ref,Ptr> Self;
87.                         Node* _node;
89.                         list_iterator(Node* node)
90.                                 :_node(node)
91.                         {}
93.                         // 解引用的重载
94.                         Ref operator*()
95.                         {
96.                                 return _node->_data;
97.                         }
99.                         // 公共函数。域内都可以使用
100.                         Ptr operator->()
101.                         {
102.                                 return &_node->_data;
103.                         }
105.                         // 迭代器的实现
106.                         Self& operator++()
107.                         {
108.                                 _node = _node->_next;
109.                                 return *this;
110.                         }
112.                         Self& operator--()
113.                         {
114.                                 _node = _node->_prev;
115.                                 return *this;
116.                         }
118.                         Self operator++(int)
119.                         {
120.                                 Self tmp(*this);
121.                                 _node = _node->_next;
122.                                 return tmp;
123.                         }
125.                         Self operator--(int)
126.                         {
127.                                 Self tmp(*this);
128.                                 _node = _node->_prev;
129.                                 return tmp;
130.                         }
132.                         bool operator!=(const Self& s)
133.                         {
134.                                 return _node != s._node;
135.                         }
137.                         bool operator==(const Self& s)
138.                         {
139.                                 return _node == s._node;
140.                         }
141.                 };
143.                 template<class T>
144.                 class list {
145.                         typedef list_node<T> Node;
146.                 public:
147.                         //typedef list_iterator<T> iterator;
148.                         // typedef list_const_iterator<T> iterator;
149.                         // 这个类要你自己实现
151.                         // or
152.                                                                                                           
153.                     // list_iterator要有三个模板参数，才能用下面的迭代器，并且const是加在后面的，而不是前面
155.                         typedef list_iterator<T, T&, T*> iterator;
156.                         typedef list_iterator<T, const T&, const T*> const_iterator;
158.                         iterator begin()
159.                         {
160.                                 return iterator(_head->_next);
161.                         }
163.                         iterator end()
164.                         {
165.                                 return iterator(_head);
166.                         }
168.                         const_iterator begin() const
169.                         {
170.                                 return const_iterator(_head->_next);
171.                         }
173.                         const_iterator end() const
174.                         {
175.                                 return const_iterator(_head);
176.                         }
178.                         void empty_init()
179.                         {
180.                                 _head = new Node();
181.                                 _head->_next = _head;
182.                                 _head->_prev = _head;
183.                                 _size = 0;
184.                         }
186.                         list()
187.                         {
188.                                 empty_init();
189.                         }
191.                         // it2(it1) 的模拟实现
192.                         list(const list<T>& It)
193.                         {
194.                                 empty_init();
196.                                 for (auto& e : It)
197.                                 {
198.                                         push_back(e);
199.                                 }
200.                         }
202.                         // it2 = it3 的模拟实现
203.                         list<T>& operator=(list<T> It)
204.                         {
205.                                 swap(It);
206.                                 return *this;
207.                         }
209.                         ~list()
210.                         {
211.                                 clear();
213.                                 delete _head;
214.                                 _head = nullptr;
215.                         }
217.                         void swap(list<T>& tmp)
218.                         {
219.                                 std::swap(_head, tmp._head);
220.                                 std::swap(_size, tmp._size);
221.                         }
223.                         void clear()
224.                         {
225.                                 auto it = begin();
226.                                 while (it != end())
227.                                 {
228.                                         it = erase(it);
229.                                         // 删除链表中的所有节点
230.                                         // erase在删除的时候会自动+1
231.                                 }
232.                         }
234.                         // it1(3,1)的模拟实现。往list中插入3个1
235.                         list(size_t n, const T& val = T())
236.                         {
237.                                 // 清空新链表
238.                                 empty_init();
240.                                 // 依次插入
241.                                 for (size_t i = 0; i < n; i++)
242.                                 {
243.                                         push_back(val);
244.                                 }
245.                         }
247.                         void push_back(const T& x)
248.                         {
249.                                 Node* new_node = new Node(x);// 指向待插入数据的指针
250.                                 Node* tail = _head->_prev;// 头结点的上一个节点。也就是链表的最后一个节点
252.                                 tail->_next = new_node;// 最后一个节点的 next 指向 new_node
253.                                 new_node->_prev = tail;// new_node 的 prev 指向最后一个节点
255.                                 new_node->_next = _head;// 由于 new_node 成为最后一个节点。所以更新链表中头结点的下一个指针
256.                                 _head->_prev = new_node;// 头节点的 prev 指向 new_node
258.                                 // // 新版本
259.                                 // insert(end(),x);
260.                         }
262.                         void push_front(const T& x)
263.                         {
264.                                 insert(begin(), x);
265.                         }
267.                         void pop_front()
268.                         {
269.                                 erase(begin());
270.                         }
272.                         void pop_back()
273.                         {
274.                                 erase(--end());
275.                         }
277.                         iterator insert(iterator pos, const T& val)
278.                         {
279.                                 // cur 需要插入新数据的节点
280.                                 Node* cur = pos._node;
281.                                 // newnode 需要插入的新数据
282.                                 Node* newnode = new Node(val);
283.                                 // 需要插入新数据节点的上一个节点
284.                                 Node* prev = cur->_prev;
286.                                 // list是链表，所以想要头插，就只需要改变上一个节点的next，下一个节点的prev
287.                                 prev->_next = newnode;// 上一个节点的 next 换成 newnode
288.                                 newnode->_prev = prev;// 新数据指向上一个节点的指针 prev 指向上一个节点
289.                                 newnode->_next = cur;// 新数据的下一个节点指向节点的原数据
290.                                 cur->_prev = newnode;// 原节点的 prev 指向新数据
291.                                 ++_size;// 改变整个链表的长度
293.                                 // return iterator 通常表示一个函数返回一个 迭代器（iterator） 对象
294.                                 // 它指向某个容器（如 std::vector、std::list、std::map 等）中的特定元素。
295.                                 return iterator(newnode);// 返回新数据
296.                         }
298.                         iterator erase(iterator pos)
299.                         {
300.                                 // 先判断是不是空链表
301.                                 assert(pos != end());
303.                                 Node* del = pos._node;// 指向待删除数据的节点的指针
304.                                 Node* next = del->_next;// 指向待删除数据节点的下一个节点
305.                                 Node* prev = del->_prev;// 指向待删除数据节点的上一个节点
307.                                 prev->_next = next;// 上一个节点的 next 指针指向下一个节点
308.                                 next->_prev = prev;// 下一个节点的 prev 指针指向上一个节点
309.                                 delete del;// 删除当前的节点
311.                                 --_size;// 减小整个数组的size
313.                                 // 返回待删除节点的下一个节点
314.                                 return iterator(next);
315.                         }
317.                 private:
318.                         Node* _head;
319.                         size_t _size;
320.                 };
322.                 // 通用的 swap 模版。所有的类型都能用
323.                 template <class T>
324.                 void swap(T& a, T& b)
325.                 {
326.                         T c(a);
327.                         a = b;
328.                         b = c;
329.                 }
331.                 // 特化的 list_swap 版本。仅适用于 list<T>类型 使用
332.                 // 特化的模版函数可以提高程序的运行效率
333.                 template<class T>
334.                 void swap(list<T>& a, list<T>& b)
335.                 {
336.                         a.swap(b);
337.                 }
338. }

复制代码

3. 完备测试代码

1. #define _CRT_SECURE_NO_WARNINGS 1
3. #include<iostream>
4. using namespace std;
5. #include<list>
6. #include<vector>
7. #include<algorithm>
9. #include"list.h"
10. //#include"teacher's list.h"
12. class Pos
13. {
14. public:
15.         int _row;
16.         int _col;
18.         Pos(int row = 0, int col = 0)
19.                 :_row(row)
20.                 , _col(col)
21.         {
22.                 cout << "Pos(int row, int col)" << endl;
23.         }
25.         Pos(const Pos& p)
26.                 :_row(p._row)
27.                 , _col(p._col)
28.         {
29.                 cout << "Pos(const Pos& p)" << endl;
30.         }
31. };
33. void test_list01()
34. {
35.         dza::list<int> lt1;
36.         lt1.push_back(1);
37.         lt1.push_back(2);
38.         lt1.push_back(3);
39.         lt1.push_back(4);
40.         for (auto& e : lt1)
41.         {
42.                 cout << e << " ";
43.         }
44.         cout << endl;
46.         auto it1 = lt1.begin();
47.         while (it1 != lt1.end())
48.         {
49.                 cout << *it1++ << " ";
50.         }
51.         cout << endl;
52. }
54. void test_list02()
55. {
56.         dza::list<int> lt1;
57.     lt1.push_back(1);
58.     lt1.push_back(1);
59.         lt1.push_back(1);
60.         lt1.push_back(1);
62.         dza::list<int>::iterator it1 = lt1.begin();
63.         while (it1 != lt1.end())
64.         {
65.                 *it1 = 2;
67.                 cout << *it1 << " ";
68.                 ++it1;
69.         }
70.         cout << endl;
72.         for (auto e : lt1)
73.         {
74.                 cout << e << " ";
75.         }
76.         cout << endl;
77. }
79. void test_list03()
80. {
81.         dza::list<Pos> lt2;
83.         // _row构造次数 == 0，_row构造次数 r1++
84.         // _col构造次数 == 0，_col构造次数 c1++
85.         Pos p1(1, 1);
86.         lt2.push_back(p1);// r1++,c1++
87.         lt2.push_back(Pos(2, 2)); // r1++,c1++
88.         // {}隐式类型转换
89.         lt2.push_back({ 3,3 });// r1++,c1++
90.         // 动用4次_row构造。4次_col构造
92.         dza::list<Pos>::iterator it2 = lt2.begin();
94.         while (it2 != lt2.end())
95.         {
96.                 //cout << (*it2)._row << ":" << (*it2)._col << endl;
97.                 // 为了可读性，特殊处理，省略了一个->
99.                 // 两种读取方式。打印两次
100.                 cout << it2->_row << ":" << it2->_col << endl;
101.                 cout << it2.operator->()->_row << ":" << it2.operator->()->_col << endl;
103.                 ++it2;
104.         }
105.         cout << endl;
106. }
108. void test_list04()
109. {
110.         dza::list<int> l1;
111.         l1.push_back(1);
112.         l1.push_back(2);
113.         l1.push_back(3);
114.         l1.push_back(4);
116.         for (auto& e : l1)
117.         {
118.                 cout << e << " ";
119.         }
120.         cout << endl;
122.         auto it1 = l1.begin();
123.         int x = 0;
124.         l1.pop_back();
125.         while (it1 != l1.end())
126.         {
127.                 cout << *it1++ << " ";
128.         }
129.         cout << endl;
130.        
131.         // 头删完成之后需要更新一下it1。否则it1指向原来的位置，为空的迭代器
132.         l1.pop_front();
133.         it1 = l1.begin();
134.         while (it1 != l1.end())
135.         {
136.                 cout << *it1++ << " ";
137.         }
138.         cout << endl;
140.         l1.push_front(0);
141.         l1.push_front(1);
142.         for (auto& e : l1)
143.         {
144.                 cout << e << " ";
145.         }
146.         cout << endl;
147. }
149. void test_list05()
150. {
151.         dza::list<int> l1;
152.         l1.push_back(1);
153.         l1.push_back(2);
154.         l1.push_back(3);
155.         l1.push_back(4);
157.         dza::list<int> l2(l1);
159.         for (auto& e : l1)
160.         {
161.                 cout << e << " ";
162.         }
163.         cout << endl;
165.         for (auto& e : l2)
166.         {
167.                 cout << e << " ";
168.         }
169.         cout << endl;
171.         dza::list<int> l3(3,1);
172.         for (auto& e : l3)
173.         {
174.                 cout << e << " ";
175.         }
176.         cout << endl;
178.         l3.clear();
179.         for (auto& e : l3)
180.         {
181.                 cout << e << " ";
182.         }
183.         cout << endl;
184. }
186. void test_list06()
187. {
188.         dza::list<int> l1;
189.         l1.push_back(1);
190.         l1.push_back(2);
191.         l1.push_back(3);
192.         l1.push_back(4);
194.         for (auto& e : l1)
195.         {
196.                 cout << e << " ";
197.         }
198.         cout << endl;
200.         auto it1 = l1.begin();
201.         it1++;
202.         it1++;
204.         l1.insert(it1, 30);
205.         for (auto& e : l1)
206.         {
207.                 cout << e << " ";
208.         }
209.         cout << endl;
211.         l1.erase(l1.begin());
212.         for (auto& e : l1)
213.         {
214.                 cout << e << " ";
215.         }
216.         cout << endl;
218. }
220. int main()
221. {
222.         test_list06();
224.         return 0;
225. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。