C++第十二弹 -- STL之list模拟实现

前言

通过模拟实现可以让我们更加深刻的理解C++底层STL的实现逻辑, 本篇就对list的底层进行模拟实现.
博客主页: 酷酷学!!! 点击关注 共同进步!!!

---

正文开始
模拟实现list

要模拟实现list, 必须要熟悉list的底层结构以及其接口的寄义, 通过上一篇的学习, 这些内容基本把握之后, 如今我们来模拟实现list.
1. ListNode节点类

1. #pragma once
2. #include<iostream>
3. using namespace std;
4. #include<assert.h>
6. namespace my
7. {
8.         //list的节点类
9.         template<class T>
10.         struct ListNode
11.         {
13.                 ListNode(const T& val = T())
14.                         : _prev(nullptr)
15.                         , _next(nullptr)
16.                         , _val(val)
17.                 {}
19.                 ListNode<T>* _prev;
20.                 ListNode<T>* _next;
21.                 T _val;
22.         };

复制代码

2. list的迭代器封装

1. list的迭代器
2. 迭代器有两种实现方式, 具体应根据容器底层数据结构的实现:
3. 1.原生态指针, 比如:vector
4. 2.将原生态指针进行封装, 因迭代器使用形式与指针完全相同,
5. 因此在自定义的类中必须实现以下方法:
6.         1.指针可以解引用,迭代器的类中必须重载operator*()
7.         2.指针可以通过->访问其所指空间成员,迭代器类中必须重载operator->()
8.         3.指针可以++向后移动,迭代器类中必须重载operator++()与operator++(int)
9.           至于operator--()/operator--(int)释放需要重载,根据具体的结构来抉择,
10.           双向链表可以向前或者向后移动,所以需要重载,如果是forward_list就不需要重载--
11.         4.迭代器需要进行是否相等的比较,因此还需要重载operator==()与operator!=()

复制代码

1.         template<class T,class Ref,class Ptr>
2.         class ListIterator
3.         {
4.                 typedef ListNode<T> Node;
5.                 typedef ListIterator<T, Ref, Ptr> Self;
6.                 //Ref 和 Ptr类型需要重新定义下,实现反向迭代器时需要用到
7.         public:
8.                 typedef Ref Ref;
9.                 typedef Ptr Ptr;
11.                 //构造
12.                 ListIterator(Node* node = nullptr)
13.                         : _node(node)
14.                 {}
16.                 //具有指针类似行为
17.                 Ref operator*()
18.                 {
19.                         return _node->_val;
20.                 }
22.                 Ptr operator->()
23.                 {
24.                         return &(operator*());
25.                 }
27.                 //迭代器支持移动
28.                 Self& operator++()
29.                 {
30.                         _node = _node->_next;
31.                         return *this;
32.                 }
34.                 Self operator++(int)
35.                 {
36.                         Self temp(*this);
37.                         _node = _node->_next;
38.                         return temp;
39.                 }
41.                 Self& operator--()
42.                 {
43.                         _node = _node->_prev;
44.                         return *this;
45.                 }
47.                 Self operator--(int)
48.                 {
49.                         Self temp(*this);
50.                         _node = _node->_prev;
51.                         return temp;
52.                 }
54.                 //迭代器支持比较
55.                 bool operator!=(const Self& l) const
56.                 {
57.                         return _node != l._node;
58.                 }
60.                 bool operator==(const Self & l) const
61.                 {
62.                         return _node == l._node;
63.                 }
65.                 Node* _node;
66.         };

复制代码

3. 反向迭代器

1.         //反向迭代器,迭代器复用
2.         template<class Iterator>
3.         class ReverseListIterator
4.         {
5.                 //注意:此处typename的作用是明确的告诉编译器,Ref是Iterator类中的一个类型,
6.                 //而不是静态成员变量,否则编译器编译时就不知道Ref是Iterator中的类型还是静态成员
7.                 //变量,因为静态成员变量也是按照 类名::静态成员变量名 的方式访问的
8.         public:
9.                 typedef typename Iterator::Ref Ref;
10.                 typedef typename Iterator::Ptr Ptr;
11.                 typedef ReverseListIterator<Iterator> Self;
13.                 //构造
14.                 ReverseListIterator(Iterator it)
15.                         : _it(it)
16.                 {}
18.                 //具有指针类似行为
19.                 Ref operator*()
20.                 {
21.                         Iterator temp(_it);
22.                         --temp;
23.                         return *temp;
24.                 }
26.                 Ptr operator->()
27.                 {
28.                         return &(operator*());
29.                 }
31.                 //迭代器支持移动
32.                 Self& operator++()
33.                 {
34.                         --_it;
35.                         return *this;
36.                 }
38.                 Self& operator++(int)
39.                 {
40.                         Self temp(*this);
41.                         --_it;
42.                         return *this;
43.                 }
45.                 Self& operator--()
46.                 {
47.                         ++_it;
48.                         return *this;
49.                 }
51.                 Self& operator--(int)
52.                 {
53.                         Self temp(*this);
54.                         ++_it;
55.                         return temp;
56.                 }
58.                 //迭代器支持比较
59.                 bool operator!=(const Self& l) const
60.                 {
61.                         return _it != l._it;
62.                 }
64.                 bool operator==(const Self& l) const
65.                 {
66.                         return _it == l._it;
67.                 }
68.                 Iterator _it;
69.         };

复制代码

4. list类的模拟实现

1.         template<class T>
2.         class list
3.         {
4.                 typedef ListNode<T> Node;
6.         public:
8.                 //正向迭代器
9.                 typedef ListIterator<T, T&, T*> iterator;
10.                 typedef ListIterator<T, const T&, T*> const_iterator;
12.                 //反向迭代器
13.                 typedef ReverseListIterator<iterator> reverse_iterator;
14.                 typedef ReverseListIterator<const_iterator> const_reverse_iterator;
15.                
16.                 //List的构造
17.                 list()
18.                 {
19.                         CreateHead();
20.                 }
22.                 list(int n, const T& value = T())
23.                 {
24.                         CreateHead();
25.                         for (int i = 0; i < n; ++i)
26.                         {
27.                                 push_back(value);
28.                         }
29.                 }
31.                 template<class Iterator>
32.                 list(Iterator first, Iterator last)
33.                 {
34.                         CreateHead();
35.                         while (first != last)
36.                         {
37.                                 push_back(*first);
38.                                 ++first;
39.                         }
40.                 }
41.                
42.                 list(const list<T>& l)
43.                 {
44.                         CreateHead();
45.                         //用l中的元素构造临时的temp,然后与当前对象交换
46.                         list<T> temp(l.begin(), l.end());
47.                         this->swap(temp);
48.                 }
50.                 list<T>& operator=(list<T> l)
51.                 {
52.                         this->swap(l);
53.                         return *this;
54.                 }
56.                 ~list()
57.                 {
58.                         clear();
59.                         delete _head;
60.                         _head = nullptr;
61.                 }
64.                 //list的迭代器
65.                 iterator begin()
66.                 {
67.                         return iterator(_head->_next);
68.                 }
70.                 iterator end()
71.                 {
72.                         return iterator(_head);
73.                 }
75.                 const_iterator begin() const
76.                 {
77.                         return const_iterator(_head->_next);
78.                 }
80.                 const_iterator end() const
81.                 {
82.                         return const_iterator(_head);
83.                 }
85.                 reverse_iterator rbegin()
86.                 {
87.                         return reverse_iterator(end());
88.                 }
90.                 reverse_iterator rend()
91.                 {
92.                         return reverse_iterator(begin());
93.                 }
95.                 const_reverse_iterator rbegin() const
96.                 {
97.                         return const_reverse_iterator(end());
98.                 }
100.                 const_reverse_iterator rend() const
101.                 {
102.                         return const_reverse_iterator(begin());
103.                 }
105.                 //List的容器相关
106.                 size_t size() const
107.                 {
108.                         Node* cur = _head->_next;
109.                         size_t count = 0;
110.                         while (cur != _head)
111.                         {
112.                                 ++count;
113.                                 cur = cur->_next;
114.                         }
115.                         return count;
116.                 }
118.                 bool empty() const
119.                 {
120.                         return _head->_next = _head;
121.                 }
123.                 void resize(size_t newsize, const T* data = T())
124.                 {
125.                         size_t oldsize = size();
126.                         if (newsize <= oldsize)
127.                         {
128.                                 //将有效元素减少到newsize
129.                                 while (newsize < oldsize)
130.                                 {
131.                                         pop_back();
132.                                         --oldsize;
133.                                 }
134.                         }
135.                         else
136.                         {
137.                                 while (oldsize < newsize)
138.                                 {
139.                                         push_back(data);
140.                                         ++oldsize;
141.                                 }
142.                         }
143.                 }
145.                 //list的元素访问操作
146.                 //注意:List不支持operator[]
147.                 T& front()
148.                 {
149.                         return _head->_next->_val;
150.                 }
152.                 const T& front() const
153.                 {
154.                         return _head->_next->_val;
155.                 }
157.                 T& back()
158.                 {
159.                         return _head->_prev->_val;
160.                 }
162.                 const T& back() const
163.                 {
164.                         return _head->_prev->_val;
165.                 }
168.                 //list的插入和删除
169.                 void push_back(const T& val)
170.                 {
171.                         insert(end(), val);
172.                 }
174.                 void pop_back()
175.                 {
176.                         erase(--end());
177.                 }
179.                 void push_front(const T& val)
180.                 {
181.                         insert(begin(), val);
182.                 }
184.                 void pop_front()
185.                 {
186.                         erase(begin());
187.                 }
189.                 //在pos位置前插入值为val的节点
190.                 iterator insert(iterator pos, const T& val)
191.                 {
192.                         Node* pNewNode = new Node(val);
193.                         Node* pCur = pos._node;
194.                         //先将新节点插入
195.                         pNewNode->_prev = pCur->_prev;
196.                         pNewNode->_next = pCur;
197.                         pNewNode->_prev->_next = pNewNode;
198.                         pCur->_prev = pNewNode;
199.                         return iterator(pNewNode);
200.                 }
202.                 //删除pos位置的节点,返回该节点的下一个位置
203.                 iterator erase(iterator pos)
204.                 {
205.                         //找到待删除的节点
206.                         Node* pDel = pos._node;
207.                         Node* pRet = pDel->_next;
209.                         //将该节点从链表中拆下来并删除
210.                         pDel->_prev->_next = pDel->_next;
211.                         pDel->_next->_prev = pDel->_prev;
212.                         delete pDel;
214.                         return iterator(pRet);
215.                 }
217.                 void clear()
218.                 {
219.                         Node* cur = _head->_next;
220.                         //采用头删除删除
221.                         while (cur != _head)
222.                         {
223.                                 Node* next = cur->_next;
224.                                 delete cur;
225.                                 cur = next;
226.                         }
227.                         _head->_next = _head->_prev = _head;
228.                 }
229.                
230.                 void swap(my::list<T>& l)
231.                 {
232.                         std::swap(_head, l._head);
233.                 }
235.         private:
236.                 void CreateHead()
237.                 {
238.                         _head = new Node;
239.                         _head->_prev = _head;
240.                         _head->_next = _head;
241.                 }
242.                 Node* _head;
243.         };       
244. }

复制代码

测试代码

对构造函数进行测试

1. //对模拟实现的list进行测试
2. //正向打印链表
3. template<class T>
4. void PrintList(const my::list<T>& l)
5. {
6.         auto it = l.begin();
7.         while (it != l.end())
8.         {
9.                 cout << *it << " ";
10.                 ++it;
11.         }
12.         cout << endl;
13. }
15. //测试list的构造
16. void Testmylist1()
17. {
18.         my::list<int> l1;
19.         my::list<int> l2(10, 5);
20.         PrintList(l2);
22.         int array[] = { 1,2,3,4,5,6,7,8,9,0 };
23.         my::list<int> l3(array, array + sizeof(array) / sizeof(array[0]));
24.         PrintList(l3);
26.         my::list<int> l4(l3);
27.         PrintList(l4);
29.         l1 = l4;
30.         PrintList(l1);
31. }

复制代码

对头/尾插入删除进行测试

1. //PushBack()/PopBack()/PushFront()/PopFront()
2. void Testmylist2()
3. {
4.         //测试pushBack和PopBack
5.         my::list<int> l;
6.         l.push_back(1);
7.         l.push_back(2);
8.         l.push_back(3);
9.         PrintList(l);
11.         l.pop_back();
12.         l.pop_back();
13.         PrintList(l);
15.         l.pop_back();
16.         cout << l.size() << endl;
18.         //测试pushFront与popFront
19.         l.push_front(1);
20.         l.push_front(2);
21.         l.push_front(3);
22.         PrintList(l);
24.         l.pop_front();
25.         l.pop_front();
26.         PrintList(l);
28.         l.pop_front();
29.         cout << l.size() << endl;
30. }

复制代码

测试指定位置插入删除

1. //测试insert和erase
2. void Testmylist3()
3. {
4.         int array[] = { 1,2,3,4,5 };
5.         my::list<int> l(array, array + sizeof(array) / sizeof(array[0]));
6.         auto pos = l.begin();
7.         l.insert(l.begin(), 0);
8.         PrintList(l);
10.         ++pos;
11.         l.insert(pos, 2);
12.         PrintList(l);
14.         l.erase(l.begin());
15.         l.erase(pos);
16.         PrintList(l);
18.         //pos指向的节点已经被删除,pos迭代器失效
19.         cout << *pos << endl;
20.         auto it = l.begin();
21.         while (it != l.end())
22.         {
23.                 it = l.erase(it);
24.         }
25.         cout << l.size() << endl;
26. }

复制代码

测试反向迭代器

1. //测试反向迭代器
2. void Testmylist4()
3. {
4.         int array[] = { 1,2,3,4,5 };
5.         my::list<int> l(array, array + sizeof(array) / sizeof(array[0]));
6.        
7.         auto rit = l.rbegin();
8.         while (rit != l.rend())
9.         {
10.                 cout << *rit << " ";
11.                 ++rit;
12.         }
13.         cout << endl;
15.         const my::list<int> cl(l);
16.         auto crit = l.rbegin();
17.         while (crit != l.rend())
18.         {
19.                 cout << *crit <<" ";
20.                 ++crit;
21.         }
22.         cout << endl;
23. }

复制代码

list的反向迭代器

我们知道, 反向迭代器的++就是正向迭代器的- -, 反向迭代器的- -就是正向迭代器的++, 因此反向迭代器的实现可以借助正向迭代器, 即: 返现迭代器内部可以包含一个正向迭代器, 对正向迭代器的接口进行包装即可.

1.         //反向迭代器,迭代器复用
2.         template<class Iterator>
3.         class ReverseListIterator
4.         {
5.                 //注意:此处typename的作用是明确的告诉编译器,Ref是Iterator类中的一个类型,
6.                 //而不是静态成员变量,否则编译器编译时就不知道Ref是Iterator中的类型还是静态成员
7.                 //变量,因为静态成员变量也是按照 类名::静态成员变量名 的方式访问的
8.         public:
9.                 typedef typename Iterator::Ref Ref;
10.                 typedef typename Iterator::Ptr Ptr;
11.                 typedef ReverseListIterator<Iterator> Self;
13.                 //构造
14.                 ReverseListIterator(Iterator it)
15.                         : _it(it)
16.                 {}
18.                 //具有指针类似行为
19.                 Ref operator*()
20.                 {
21.                         Iterator temp(_it);
22.                         --temp;
23.                         return *temp;
24.                 }
26.                 Ptr operator->()
27.                 {
28.                         return &(operator*());
29.                 }
31.                 //迭代器支持移动
32.                 Self& operator++()
33.                 {
34.                         --_it;
35.                         return *this;
36.                 }
38.                 Self& operator++(int)
39.                 {
40.                         Self temp(*this);
41.                         --_it;
42.                         return *this;
43.                 }
45.                 Self& operator--()
46.                 {
47.                         ++_it;
48.                         return *this;
49.                 }
51.                 Self& operator--(int)
52.                 {
53.                         Self temp(*this);
54.                         ++_it;
55.                         return temp;
56.                 }
58.                 //迭代器支持比较
59.                 bool operator!=(const Self& l) const
60.                 {
61.                         return _it != l._it;
62.                 }
64.                 bool operator==(const Self& l) const
65.                 {
66.                         return _it == l._it;
67.                 }
68.                 Iterator _it;
69.         };

复制代码

---

完
总结

通过以上的实现，可以模拟出一个雷同于list的数据结构，而且可以对其中的元素进行添加、删除、查找、等利用。如许就可以在不使用C++内置的list时，使用自己实现的List类来进行相同的利用。
感谢您的点赞与收藏!!!

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

继续阅读请点击广告