【C++】list底层的模仿实现

个人主页

🎄一、媒介

list是一个双向链表的容器，它可以在其内部中存储各种范例的元素，而且支持动态地添加、删除和修改元素。
🏠二、根本框架

list可以分为三部门：一个是list节点类，一个是迭代器类，尚有一个是list类自己。
它们三个类底层的成员变量又分别代表差异的功能。
此中list节点类封装了list的元素以及前后指针，且完成了节点的初始化。
迭代器类封装了指向节点的指针，还负责重载++、–等运算符。
list类自己负责初始化以及负责插入和删除等功能。
🎡三、list节点类的实现

链表中数据以及前后指针的范例都是由模板主动天生的，可以为内置范例或自界说范例。

1. template<class T>
2. struct list_node
3. {
4.         T _data;
5.         list_node<T>* _next;
6.         list_node<T>* _prev;
8.         //构造
9.         list_node(const T& data = T())
10.                 :_data(data)
11.                 , _next(nullptr)
12.                 , _prev(nullptr)
13.         {};
14. };

复制代码

🎉四、list迭代器类

由于迭代器涉及平凡迭代器和const迭代器，因此我们可以利用模板，在模板内里设置三个差异的范例，分别为节点的数据范例、引用范例和指针范例。

1. template<class T,class Ref,class Ptr>
2. struct list_iterator
3. {
4.         typedef list_node<T> Node;
5.         typedef list_iterator<T, Ref, Ptr> Self;
6.         //用来访问Node类型的成员变量
7.         Node* _node;
8. };

复制代码

迭代器的默认构造函数由于支持根本的隐式范例转换，因此实现起来也很简单。

1. list_iterator(Node* node)
2.         :_node(node)
3. {}

复制代码

1.Ref operator*()

负责重载迭代器的解引用，直接返回当前该迭代器指向的节点数据即可。

1. Ref operator*()
2. {
3.         return _node->_data;
4. }

复制代码

2.Ptr operator->()

由于我们想把迭代器当成指针利用，因此重载->是须要的，其返回值为节点元素的地点。为什么是返回地点呢？这是由于在利用迭代器->时，编译器会主动优化成->->。

1. Ptr operator->()
2. {
3.         return &_node->_data;
4. }

复制代码

3.Self& operator++()前置和Self& operator–()前置

直接让节点指向下一个和前一个即可。

1. //前置++
2. Self& operator++()
3. {
4.         _node = _node->_next;
5.         return *this;
6. }
7. //前置--
8. Self& operator--()
9. {
10.         _node = _node->_prev;
11.         return *this;
12. }

复制代码

4.Self operator++(int)后置和Self operator–(int)后置

我们只需把当前迭代器实例化的对象拷贝给一个新的迭代器对象tmp，然后把当前的数据举行处理处罚，末了将tmp举行返回即可。

1. //后置++
2. Self operator++(int)
3. {
4.         Self tmp(*this);
5.         _node = _node->_next;
6.         return tmp;
7. }
8. //后置--
9. Self& operator--(int)
10. {
11.         Self tmp(*this);
12.         _node = _node->_prev;
13.         return tmp;
14. }

复制代码

5.bool operator!=(const Self& s) const和bool operator==(const Self& s) const

判定节点是否相称不能只判定值是否相称，由于差异的节点可以存放类似的值，因此必要比力其节点是否相称即可。

1. bool operator!=(const Self& s) const
2. {
3.         return _node != s._node;
4. }
6. bool operator==(const Self& s) const
7. {
8.         return _node == s._node;
9. }

复制代码

⭐五、list类

1.初始化

初始化只需初始化头结点即可。

1. //无参初始化
2. list()
3. {
4.         //通过调用这一函数来创建头节点
5.         empty_init();
6. }
8. //空初始化
9. void empty_init()
10. {
11.         _head = new Node;
12.         _head->_next = _head;
13.         _head->_prev = _head;
14.         _size = 0;
15. }

复制代码

2.构造函数

当链表为空时，_head节点的头和尾都指向它自己，因此在后续有节点插入时，只需改变一下prev和next指向的位置即可。

1. list()
2. {
3.         _head = new Node<T>();
4.         _head->next = _head;
5.         _head->prev = _head;
6. }

复制代码

4.析构函数和clear函数

析构函数是用来开释节点空间的，因此必要先界说一个clear函数用来开释全部的有效节点，确保没有有效节点后再把哨兵位的_head举行删除，然后将_head置为空。

1. //析构
2. ~list()
3. {
4.         clear();
5.         delete _head;
6.         _head = nullptr;
7. }
9. void clear()
10. {
11.         auto it = begin();
12.         while (it != end())
13.         {
14.                 it = erase(it);
15.         }
16. }

复制代码

5.深拷贝

先对其举行空初始化利用，然后用迭代器依次对其举行访问然后插入即可。

1. //深拷贝
2. list(const list<T>& lt)
3. {
4.         empty_init();
5.         for (auto& e : lt)
6.         {
7.                 push_back(e);
8.         }
9. }

复制代码

6.深赋值

我们可以调用swap函数将两者数据举行交换即可。

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

复制代码

7.头插和头删函数

头插函数就是每次在begin位置之进步行插入，由于begin是第一个有效的元素；而头删就是每次在begin位置举行删除。

1. void push_front(const T& x)
2. {
3.         Insert(begin(), x);
4. }
6. void pop_front()
7. {
8.         erase(--begin());

复制代码

8.尾插和尾删函数

尾插就是每次在end()位置举行插入，由于end是末了一个有效的元素；而尾删则是在end()的位置上举行删除。
由于我们实现了insert函数，因此就可以调用insert函数在其尾部插入数据即可。

1. void push_back(const T& x)
2. {
3.         Insert(end(), x);
4.         ++_size;
5. }
7. void pop_back()
8. {
9.         erase(--end());
10. }

复制代码

9.insert和erase函数

insert函数就是在pos位置插入值。

1. iterator Insert(iterator pos, const T& x)
2. {
3.         //取到pos位置的节点
4.         Node* cur = pos._node;
5.         //保留之前的节点
6.         Node* prev = cur->_prev;
7.         //创建新节点
8.         Node* newnode = new Node(x);
9.         //改变指向，最后更新一下_size
10.         newnode->_next = cur;
11.         cur->_prev = newnode;
12.         newnode->_prev = prev;
13.         prev->_next = newnode;
14.         ++_size;
15.         return newnode;
16. }

复制代码

erase函数起首要举行断言，防止删除哨兵位。然后将pos位置节点的前和后举行毗连，末了删除pos位置的节点，更新一下_size的巨细。

1. iterator erase(iterator pos)
2. {
3.         assert(pos != end());
4.         Node* prev = pos._node->_prev;
5.         Node* next = pos._node->_next;
6.         prev->_next = next;
7.         next->_prev = prev;
8.         delete pos._node;
9.         --_size;
10.         return next;
11. }

复制代码

10.迭代器的实现（平凡和const)

由于存在平凡成员变量和const成员变量的调用，因此必要实现两个迭代器。
begin迭代器是返回第一个有效位置，由于哨兵位_head并没有数据，因此返回哨兵位的下一个位置。end迭代器是返回末了一个元素的下一个位置，而这个位置是无效的，双向链表无效的位置就只有哨兵位这一个位置，因此返回哨兵位即可。

1. iterator begin()
2. {
3.         return _head->_next;
4. }
6. iterator end()
7. {
8.         return _head;
9. }
11. //const迭代器
12. const_iterator begin() const
13. {
14.         return _head->_next;
15. }
17. const_iterator end() const
18. {
19.         return _head;
20. }

复制代码

11.判空

直接判定_size是否为空即可。

1. //判空
2. bool empty() const
3. {
4.         return _size == 0;
5. }

复制代码

12.size()函数

直接返回_size即可。

1. size_t size() const
2. {
3.         return _size;
4. }

复制代码

🚀六、vector和list函数的区别

起首，vector是一个动态数组，在插入和删除数据的时间会挪动背面的元素，这就有大概会导致迭代器失效；而list则为链表，它可以在恣意位置举行插入和删除，因此迭代器的稳固性就更高。
其次，vector的迭代器通常为随机访问迭代器，允许向前向后访问元素，而list迭代器大概为双向迭代器，只能向前或向后移动。
末了，vector的随机访问速率快，因此在查找元素时的服从高，但假如频仍的插入大概删除元素时，list通常会更快，由于它不必要移动大量的元素。
🏝️七、源代码

1. #include<iostream>
2. #include<assert.h>
3. #include<list>
4. using namespace std;
6. namespace bit
7. {
8.         template<class T>
9.         struct list_node
10.         {
11.                 T _data;
12.                 list_node<T>* _next;
13.                 list_node<T>* _prev;
15.                 //构造
16.                 list_node(const T& data = T())
17.                         :_data(data)
18.                         , _next(nullptr)
19.                         , _prev(nullptr)
20.                 {};
21.         };
22.         //const迭代器
23.         template<class T,class Ref,class Ptr>
24.         struct list_iterator
25.         {
26.                 typedef list_node<T> Node;
27.                 typedef list_iterator<T, Ref, Ptr> Self;
28.                 Node* _node;
30.                 list_iterator(Node* node)
31.                         :_node(node)
32.                 {}
34.                 Ref operator*()
35.                 {
36.                         return _node->_data;
37.                 }
39.                 Ptr operator->()
40.                 {
41.                         return &_node->_data;
42.                 }
43.        
44.                 //前置++
45.                 Self& operator++()
46.                 {
47.                         _node = _node->_next;
48.                         return *this;
49.                 }
51.                 //后置++
52.                 Self operator++(int)
53.                 {
54.                         Self tmp(*this);
55.                         _node = _node->_next;
56.                         return tmp;
57.                 }
59.                 //前置--
60.                 Self& operator--()
61.                 {
62.                         _node = _node->_prev;
63.                         return *this;
64.                 }
66.                 //后置--
67.                 Self& operator--(int)
68.                 {
69.                         Self tmp(*this);
70.                         _node = _node->_prev;
71.                         return tmp;
72.                 }
74.                 bool operator!=(const Self& s) const
75.                 {
76.                         return _node != s._node;
77.                 }
79.                 bool operator==(const Self& s) const
80.                 {
81.                         return _node == s._node;
82.                 }
83.         };
85.         template<class T>
86.         class list
87.         {
88.                 typedef list_node<T> Node;
89.         public:
90.                 typedef list_iterator<T,T&,T*> iterator;
91.                 typedef list_iterator<T,const T&,const T*> const_iterator;
93.                 iterator begin()
94.                 {
95.                         return _head->_next;
96.                 }
98.                 iterator end()
99.                 {
100.                         return _head;
101.                 }
103.                 //const迭代器
104.                 const_iterator begin() const
105.                 {
106.                         return _head->_next;
107.                 }
109.                 const_iterator end() const
110.                 {
111.                         return _head;
112.                 }
114.                 //空初始化
115.                 void empty_init()
116.                 {
117.                         _head = new Node;
118.                         _head->_next = _head;
119.                         _head->_prev = _head;
120.                         _size = 0;
121.                 }
123.                 //无参初始化
124.                 list()
125.                 {
126.                         empty_init();
127.                 }
129.                 //析构
130.                 ~list()
131.                 {
132.                         clear();
133.                         delete _head;
134.                         _head = nullptr;
135.                 }
137.                 void clear()
138.                 {
139.                         auto it = begin();
140.                         while (it != end())
141.                         {
142.                                 it = erase(it);
143.                         }
144.                 }
146.                 //深拷贝
147.                 list(const list<T>& lt)
148.                 {
149.                         empty_init();
150.                         for (auto& e : lt)
151.                         {
152.                                 push_back(e);
153.                         }
154.                 }
156.                 //深赋值
157.                 void swap(list<int>& lt)
158.                 {
159.                         std::swap(_head, lt._head);
160.                         std::swap(_size, lt._size);
161.                 }
163.                 list<T>& operator=(list<T> lt)
164.                 {
165.                         swap(lt);
166.                         return *this;
167.                 }
169.                 size_t size() const
170.                 {
171.                         return _size;
172.                 }
174.                 void push_back(const T& x)
175.                 {
176.                         Insert(end(), x);
177.                         ++_size;
178.                 }
180.                 iterator Insert(iterator pos, const T& x)
181.                 {
182.                         Node* cur = pos._node;
183.                         Node* prev = cur->_prev;
184.                         Node* newnode = new Node(x);
185.                         newnode->_next = cur;
186.                         cur->_prev = newnode;
187.                         newnode->_prev = prev;
188.                         prev->_next = newnode;
189.                         ++_size;
190.                         return newnode;
191.                 }
192.        
193.                 void pop_back()
194.                 {
195.                         erase(--end());
196.                 }
198.                 void pop_front()
199.                 {
200.                         erase(--begin());
201.                 }
203.                 iterator erase(iterator pos)
204.                 {
205.                         assert(pos != end());
206.                         Node* prev = pos._node->_prev;
207.                         Node* next = pos._node->_next;
208.                         prev->_next = next;
209.                         next->_prev = prev;
210.                         delete pos._node;
211.                         --_size;
212.                         return next;
213.                 }
215.                 void push_front(const T& x)
216.                 {
217.                         Insert(begin(), x);
218.                 }
220.                 //判空
221.                 bool empty() const
222.                 {
223.                         return _size == 0;
224.                 }
225.        
226.         private:
227.                 Node* _head;
228.                 size_t _size;
229.         };
230. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！qidao123.com:ToB企服之家，中国第一个企服评测及软件市场,开放入驻,技术点评得现金