list(c++)

前言

这里我们学习的是gcc下STL版本的list。STL里的list容器底层是一个双向带头节点的一个链表，不再是单链表，单链表现实运用很少，更多的是双向带头链表。

正文

list利用

默认成员函数

构造函数	接口说明
list (size_type n, const value_type& val = value_type())	构造的list中包含n个值为val的元素
list()	构造空的list
list (const list& x)	拷贝构造函数
list (InputIterator first, InputIterator last)	用[first, last)区间中的元素构造list

迭代器

函数声明	接口说明
begin + end	返回第一个元素的迭代器+返回末了一个元素下一个位置的迭代器
rbegin + rend	返回第一个元素的reverse_iterator,即end位置，返回末了一个元素下一个位置的 reverse_iterator,即begin位置

容量

函数声明	接口说明
empty	检测list是否为空，是返回true，否则返回false
size	返回list中有效节点的个

增删查改

函数声明	接口说明
push_front	在list首元素前插入值为val的元素
pop_front	删除list中第一个元素
push_back	在list尾部插入值为val的元素
pop_back	删除list中末了一个元素
insert	在list position 位置中插入值为val的元素
erase	删除list position位置的元素
swap	互换两个list中的元素
clear	清空list中的有效元素

代码演示

这里list利用很简朴，我就不一个一个演示了。就用一个测试案例测试下吧

2. void Print(const li::list<int>& lt)
3. {
4.         li::list<int>::const_iterator it = lt.begin();
5.         while (it != lt.end())
6.         {
7.                 //(*it)++;
8.                 cout << *it << " ";
9.                 ++it;
10.         }
11. }
12. void list_test01()
13. {
14.         li::list<int> lt;
15.         lt.push_back(1);
16.         lt.push_back(2);
17.         lt.push_back(3);
18.         lt.push_back(4);
19.         Print(lt);
20.         cout << endl;
21.         //这里是拷贝构造 内置类型 浅拷贝
22.         li::list<int>::iterator it = lt.begin();
23.         while (it != lt.end())
24.         {
25.                 (*it)++;
26.                 cout << *it << " ";
27.                 ++it;
28.         }
29. }

复制代码

这里我就简朴测试下，必要注意的是，erase之后迭代器被开释失效，记得用返回值担当。clear这里底层上就是开释掉了所有的节点，只留下一个头节点。因为链表结构决定了它是可以部分删除容量的，不像连续地址的顺序表。因此，list的clear就直接删除节点了，而不是仅仅清除数据。

list模仿实现

成员变量

2. template<class T>
3. struct list_node
4. {
5.         list_node<T>* _next;
6.         list_node<T>* _prev;
7.         T _val;
9.         list_node(const T& x = T())
10.                 :_next(nullptr),
11.                 _prev(nullptr),
12.                 _val(x)
13.         {
15.         }
16. };
17. template<class T>
18. class list
19. {
20.         typedef list_node<T> Node;
21.     //...
22.     //
23.     private:
24.         Node* _head;
25.         size_t _size;
27. }

复制代码

从链表开始，就有点复杂了，利用许多封装和重命名。这里我们必要先实现一个结构体(结点)，
这里必要重名命下这个类模板，这是为啥呢？这是一个风俗问题。祖师爷在研究STL的时候，他本身也是从c语言过度来的，虽然类模板也是它老人家研究出来的。但是在声明一个变量的时候，加上一个模板，很容易忘记，尤其风俗了c语言的命名变量的语法。以是，这里重命名下是一种风俗问题，并且也可以简化代码。这也是一个好风俗，因为你的模板可不肯定只有一个，如果你的leader突然让你改一下这个容器，增加一个模板，你难不成一个一个该吗？这时候重命名就香许多了，只必要改一下。
这里还有一个size,有这个参数我们就可以很直观的观察链表，和判定链表是否为空。有利于我们更直观的利用链表和调试。

默认成员函数

2.                 void empty_init()
3.                 {
4.                         _head = new Node;
5.                         _head->_next = _head;
6.                         _head->_prev = _head;
7.                         _size = 0;
8.                 }
9.                 list()
10.                 {
11.                         empty_init();
12.                 }
13.                 //不能用const引用
14.                 void swap(list<T>& lt)
15.                 {
16.                         std::swap(_head, lt._head);
17.                         std::swap(_size, lt._size);
18.                 }
19.                 list<T>& operator=(list<T> lt)
20.                 {
21.                         swap(lt);
22.                         return *this;
23.                 }
24.                 list(const list<T>& lt)
25.                 {
26.                         empty_init();
27.                         for (auto& e : lt)
28.                         {
29.                                 push_back(e);
30.                         }
31.                 }
32.         ~list()
33.         {
34.                 clear();
35.                 delete _head;
36.                 _head = nullptr;
37.         }

复制代码

这里构造函数里面套了一个函数初始化，这也是向库里版本靠齐。这里的赋值重载是用的现代写法，直接swap互换，传统的写法是直接手搓一遍(不推荐)。这里的拷贝构造函数里面复用了push_back，析构函数复用了clear()，这也体现list的高度封装性，其实库里的比这里还复杂。动态内存分配也不是new而是封装了一个空间配置器，就是效率高点。我在vector的博客也提及过。我们学习STL的代码，强烈不发起一行一行看，否则你会直接想放弃的。这里我们先知道个大要逻辑。到下文会解释clear和push_back()这两个函数，其实push_back里面也是套用了insert的。就像套娃一样，这里的代码。
迭代器

重点 重点 重点 重要的事说三遍，list的迭代器可谓是学习list的重点也是一个难点，先问一下，如何设计list的迭代器？可以像vector里那样吗？直接指针吗？可是这里是一个自定义类型呀？解引用也不是结点的值呀？因此，这里肯定是要对*赋值重载的。以是，就可以先否定直接指针了，这肯定不行的！既然要赋值重载，那我们就肯定要自定义类型呀？对，这里的迭代器就是一个自定义类型，里面包含着一个结点指针，还有构造函数，完成初始化。这里不介绍反向迭代器，因为反向迭代器的设计和正向有点不一样，这里我们先学习正向迭代器，正向迭代器就够喝一壶了。

2. template<class T,class Ref,class Ptr>
3. struct _list_iterator
4. {
5.         typedef list_node<T> Node;
6.         typedef _list_iterator<T,Ref,Ptr> self;
7.         Node* _node;
8.         _list_iterator(Node* node)
9.                 :_node(node)
10.         {}
11.         Ref operator*()
12.         {
13.                 return _node->_val;
14.         }
15.         Ptr operator->()
16.         {
17.                 return &(_node->_val);
18.         }
19.         self& operator++()
20.         {
21.                 _node = _node->_next;
22.                 return *this;
23.         }
24.         self& operator++(int)
25.         {
26.                 self tmp(*this);
27.                 _node = _node->_next;
28.                 return tmp;
29.         }
30.         self& operator--()
31.         {
32.                 _node = _node->_prev;
33.                 return *this;
34.         }
35.         self& operator--(int)
36.         {
37.                 self tmp(*this);
38.                 _node = _node->_prev;
39.                 return tmp;
40.         }
41.         bool operator!=(const self& it) const
42.         {
43.                 return _node != it._node;
44.         }
45.         bool operator==(const self& it) const
46.         {
47.                 return _node == it._node;
48.         }
49. };

复制代码

这里先给大家看一下完整版的迭代器设计，是不是很蒙，发现和我想的有点不一样呀!

2. ​
3. struct _list_iterator
4. {
5. typedef list_node<T> Node;
6. Node* _node;
7. _list_iterator(Node* node)
8.                 :_node(node)
9.         {}
10. };
12. ​

复制代码

这里先看我上面这个代码，是不是发现又看懂了。这里我们学习迭代器必要一步一步拆开学，他的设计其实有点难理解。我们上面讲了，迭代器必要设计成一个自定义类型，必要包装一下结点的指针，以便我们访问。这里的代码是一个雏形，有了这个雏形，对于begin(),end()，我们就完成的差不多了。但还必要大大的完善。这里还要对*，++等运算符赋值重载。那为啥有三个模板呢？这里是根据需求来设定的。首先*赋值重载返回的就是数据本身，以是数据的类型模板，我们必要你上传，直接引用，纵然结构体的数据还是什么其他自定义类型数据，都可以返回精确的值。末了一个模板为啥要传一个指针呢？迭代器模仿的是指针的举动？既然是指针那么就可以用箭头访问结构体。以是，这里的迭代器也满意了这种要求。利用箭头访问结点的元素。同理，本身上传一个指针，这样后续更改代码，我们只用修改这部分代码。这里是如何设计const修饰的迭代器呢？这时候我们的模板就香许多了，我们这必要在上传模板的时候加上一个 const,这样子你必要什么我就返回什么。这也证实我们为啥要搞三个模板，就是因为，后面的代码设计是必要利用的。其实刚开始学这里的迭代器的时候，我也很蒙蔽，但是学到后面，你才发现祖师爷的这套设计有多厉害！这里的命名也是向库里靠拢的，发起大家以后命名也尽量向库里靠拢。

2.         typedef list_node<T> Node;
3. public:
4.         typedef _list_iterator<T,T&,T*> iterator;
5.         typedef _list_iterator<T, const T&,const T*> const_iterator;
7.         iterator begin()
8.         {
9.                 return _head->_next; //单参数的构造函数支持隐式类型转换
10.                 //return iterator(_head->_next);
11.         }
12.         iterator end()
13.         {
14.                 return _head;
15.         }
16.         const_iterator begin() const
17.         {
18.                 return _head->_next;
19.                
20.         }
21.         const_iterator end() const
22.         {
23.                 return _head;
24.         }

复制代码

虽然这里链表里的迭代器看起来很简朴，和vector差不多。但底层是很复杂的，这里也体现了迭代器的重要。为啥我们要用迭代器遍历数据，祖师爷为啥要研究出个迭代器。就是因为，有了迭代器，我们可以统一用法访问任何容器的任何形式数据。不像数组就要用下标，链表就要用指针。不方便程序员的开发。有了迭代器，STL里的任何容器都可以用迭代器访问。从list开始，迭代器才真正开始上难度，而不是简朴的复用指针，这里我们学习list的迭代器的时候，不仅仅要懂list迭代器是如何实现，更要体会的是祖师爷设计的理念和头脑。更重要的是人家这种头脑，极大进步了编程简化。其实学习c++，c++意义不仅仅在利用c++开发软件和编写底层体系上，而且c++的设计的语法和理念为其他语言提供了模板，许多语言都有c++的影子，尤其像java语言，可以说是一个接近满分的抄作业选手。

容量

2.         bool empty()
3.         {
4.                 return _size == 0;
5.         }
6.         size_t size()
7.         {
8.                 return _size;
9.         }

复制代码

这里就是简朴返回，没啥好说的。
增删查改

2. void clear()
3. {
4.         iterator it = begin();
5.         while (it != end())
6.         {
7.                 it = erase(it);
8.         }
9.         _size = 0;
10. }
11. void push_back(const T& x)
12. {
13.         /*Node* tail = _head->_prev;
14.         Node* newNode = new Node(x);
16.         tail->_next = newNode;
17.         newNode->_prev = tail;
19.         newNode->_next = _head;
20.         _head->_prev = newNode;*/
21.         insert(end(), x);
22. }
23. void push_front(const T& x)
24. {
25.         insert(begin(), x);
26. }
27. void pop_back()
28. {
29.         erase(--end());
30. }
31. void pop_front()
32. {
33.         erase(begin());
34. }
35. iterator insert(iterator pos, const T& x)
36. {
37.         Node* cur = pos._node;
38.         Node* prev = cur->_prev;
39.         Node* next = cur->_next;
40.         Node* newNode = new Node(x);
41.         prev->_next = newNode;
42.         newNode->_prev = prev;
44.         newNode->_next = cur;
45.         cur->_prev = newNode;
46.         _size++;
47.         return newNode;
48. }
49. iterator erase(iterator pos)
50. {
51.         assert(pos != end());
52.         Node* cur = pos._node;
53.         Node* prev = cur->_prev;
54.         Node* next = cur->_next;
56.         prev->_next = next;
57.         next->_prev = prev;
58.         delete cur;
59.         _size--;
60.         return next;
61. }
62. void swap(list<T>& lt)
63. {
64.         std::swap(_head, lt._head);
65.         std::swap(_size, lt._size);
66. }

复制代码

这里要说一下，push_back和pop_back分别内部调用了insert和erase， 这里增删查改不消一个一个写，库里就是把大量重复的代码，封装起来。以后利用到这段代码就调用这个封装的函数，险些全是封装。现实上，底层还是那几个指针互换位置。
源码

2. #pragma once
3. #include <assert.h>
4. #include <iostream>
5. namespace li
6. {
7.         template<class T>
8.         struct list_node
9.         {
10.                 list_node<T>* _next;
11.                 list_node<T>* _prev;
12.                 T _val;
14.                 list_node(const T& x = T())
15.                         :_next(nullptr),
16.                         _prev(nullptr),
17.                         _val(x)
18.                 {
20.                 }
21.         };
22.         template<class T,class Ref,class Ptr>
23.         struct _list_iterator
24.         {
25.                 typedef list_node<T> Node;
26.                 typedef _list_iterator<T,Ref,Ptr> self;
27.                 Node* _node;
28.                 _list_iterator(Node* node)
29.                         :_node(node)
30.                 {}
31.                 Ref operator*()
32.                 {
33.                         return _node->_val;
34.                 }
35.                 Ptr operator->()
36.                 {
37.                         return &(_node->_val);
38.                 }
39.                 self& operator++()
40.                 {
41.                         _node = _node->_next;
42.                         return *this;
43.                 }
44.                 self& operator++(int)
45.                 {
46.                         self tmp(*this);
47.                         _node = _node->_next;
48.                         return tmp;
49.                 }
50.                 self& operator--()
51.                 {
52.                         _node = _node->_prev;
53.                         return *this;
54.                 }
55.                 self& operator--(int)
56.                 {
57.                         self tmp(*this);
58.                         _node = _node->_prev;
59.                         return tmp;
60.                 }
61.                 bool operator!=(const self& it) const
62.                 {
63.                         return _node != it._node;
64.                 }
65.                 bool operator==(const self& it) const
66.                 {
67.                         return _node == it._node;
68.                 }
69.         };
70.         template<class T>
71.         class list
72.         {
73.                 typedef list_node<T> Node;
74.         public:
75.                 typedef _list_iterator<T,T&,T*> iterator;
76.                 typedef _list_iterator<T, const T&,const T*> const_iterator;
78.                 iterator begin()
79.                 {
80.                         return _head->_next; //单参数的构造函数支持隐式类型转换
81.                         //return iterator(_head->_next);
82.                 }
83.                 iterator end()
84.                 {
85.                         return _head;
86.                 }
87.                 const_iterator begin() const
88.                 {
89.                         return _head->_next;
90.                        
91.                 }
92.                 const_iterator end() const
93.                 {
94.                         return _head;
95.                 }
96.                 void empty_init()
97.                 {
98.                         _head = new Node;
99.                         _head->_next = _head;
100.                         _head->_prev = _head;
101.                         _size = 0;
102.                 }
103.                 list()
104.                 {
105.                         empty_init();
106.                 }
107.                 //不能用const引用
108.                 void swap(list<T>& lt)
109.                 {
110.                         std::swap(_head, lt._head);
111.                         std::swap(_size, lt._size);
112.                 }
113.                 list<T>& operator=(list<T> lt)
114.                 {
115.                         swap(lt);
116.                         return *this;
117.                 }
118.                 list(const list<T>& lt)
119.                 {
120.                         empty_init();
121.                         for (auto& e : lt)
122.                         {
123.                                 push_back(e);
124.                         }
125.                 }
126.                 ~list()
127.                 {
128.                         clear();
129.                         delete _head;
130.                         _head = nullptr;
131.                 }
132.                 bool empty()
133.                 {
134.                         return _size == 0;
135.                 }
136.                 size_t size()
137.                 {
138.                         return _size;
139.                 }
140.                 void clear()
141.                 {
142.                         iterator it = begin();
143.                         while (it != end())
144.                         {
145.                                 it = erase(it);
146.                         }
147.                         _size = 0;
148.                 }
149.                 void push_back(const T& x)
150.                 {
151.                         /*Node* tail = _head->_prev;
152.                         Node* newNode = new Node(x);
154.                         tail->_next = newNode;
155.                         newNode->_prev = tail;
157.                         newNode->_next = _head;
158.                         _head->_prev = newNode;*/
159.                         insert(end(), x);
160.                 }
161.                 void push_front(const T& x)
162.                 {
163.                         insert(begin(), x);
164.                 }
165.                 void pop_back()
166.                 {
167.                         erase(--end());
168.                 }
169.                 void pop_front()
170.                 {
171.                         erase(begin());
172.                 }
173.                 iterator insert(iterator pos, const T& x)
174.                 {
175.                         Node* cur = pos._node;
176.                         Node* prev = cur->_prev;
177.                         Node* next = cur->_next;
178.                         Node* newNode = new Node(x);
179.                         prev->_next = newNode;
180.                         newNode->_prev = prev;
182.                         newNode->_next = cur;
183.                         cur->_prev = newNode;
184.                         _size++;
185.                         return newNode;
186.                 }
187.                 iterator erase(iterator pos)
188.                 {
189.                         assert(pos != end());
190.                         Node* cur = pos._node;
191.                         Node* prev = cur->_prev;
192.                         Node* next = cur->_next;
194.                         prev->_next = next;
195.                         next->_prev = prev;
196.                         delete cur;
197.                         _size--;
198.                         return next;
199.                 }
200.         private:
201.                 Node* _head;
202.                 size_t _size;
203.         };
204. }

复制代码

总结

学习list，学会利用是其次，更重要的是理解list底层的编写的理念和设计。这才是最终要的，关于list的学习，此中最重要的就是他的迭代器的设计，这里是最难的。其他部分都是高度的重复，像增删查改就是简朴的链表编写。


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

继续阅读请点击广告