STL容器--list

1. list的介绍及使用
1.1 list的介绍

1. list是可以在常数范围内在任意位置举行插入和删除的序列式容器，并且该容器可从前后双向迭代。
2. list的底层是双向链表结构，双向链表中每个元素存储在互不相干的独立节点中，在节点中通过指针指其前一个元素和后一个元素。
3. list与forward_list非常相似：最紧张的差别在于forward_list是单链表，只能朝前迭代，已让其更简朴高效。
4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置举行插入、移除元素的执行效率更好。
5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，好比：要访问list的第6个元素，必须从已知的位置(好比头部大概尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相干联信息(对于存储类型较小元素的大list来说这大概是一个紧张的因素)
1.2 list的使用

list中的接口比力多，此处类似，只需要把握如何正确的使用，然后再去深入研究背后的原理，已到达可扩展的能力。以下为list中一些常见的紧张接口：
1.2.1 list的构造
 

1.2.2 list iterator的使用

list迭代器可以理解成一个指针，该指针指向list中的某个节点。实际它是指针的封装。

1. void testlist1()
2.         {
3.                 list<int> lt;
4.                 lt.push_back(1);
5.                 lt.push_back(2);
6.                 lt.push_back(3);
7.                 lt.push_back(4);
8.                 lt.push_back(5);
10.                 list<int>::iterator it = lt.begin();
11.                 cout << *it++ << endl;
12.                 while (it != lt.end())
13.                 {
14.                         cout << *it << " ";
15.                         it++;
16.                 }
18.                 cout << endl;
20.         }

复制代码

1.2.3 list capacity

1.2.4 list element access

1. int main()
2. {
4.         //list<int> lt(3);
5.         vector<int> v{ 4,5 };
7.     vector<string> tokens{ "4","13","5","/","+" };
8.     cout<<evalRPN(tokens)<<endl;
10.     list<int> lt;
11.     lt.push_back(1);
12.     lt.push_back(2);
13.     lt.push_back(3);
14.     lt.push_back(4);
15.     lt.push_back(5);
16.     //这里可以直接修改里面第一个元素的值
17.     lt.front() = 10;  
18.     for (auto e : lt)
19.     {
20.         cout << e << " ";
21.     }
22.     cout << endl;
23.    
24.         return 0;
25. }

复制代码

1.2.5 list modifiers

以下代码对部门接口举行测试：

1.         void testlist3()
2.         {
3.                 list<int> lt;
4.                 lt.push_front(1);
5.                 lt.push_front(2);
6.                 lt.push_front(3);
7.                 lt.push_front(4);
8.                 lt.push_front(5);
9.                 for (auto e : lt)
10.                 {
11.                         cout << e << " ";
12.                 }
13.                 cout << endl;
14.                 list<int> lt1;
15.                 lt1.push_front(10);
16.                 lt1.push_front(20);
17.                 lt1.push_front(30);
18.                 lt1.push_front(40);
19.                 lt.swap(lt1);
20.                 for (auto e : lt)
21.                 {
22.                         cout << e << " ";
23.                 }
24.                 cout << endl<<"头删后："<<endl;
26.                 lt.erase(lt.begin());
27.                 for (auto e : lt)
28.                 {
29.                         cout << e << " ";
30.                 }
31.                 cout << endl;
32.         }

复制代码

1.2.6 list的迭代器失效

迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中举行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。
删除list容器的全部值 正确写法：

1. void TestListIterator()
2. {
3.     int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
4.     list<int> l(array, array + sizeof(array) / sizeof(array[0]));
5.     for (auto e : l)
6.     {
7.         cout << e <<" ";
8.     }
9.     auto it = l.begin();
10.     while (it != l.end())
11.     {
12.         //此时it已经指向原来it的下一个迭代器位置
13.         l.erase(it++); // it = l.erase(it);
15.         //下面两行为错误写法
17.         //l.erase(it);
18.         //++it;
19.     }
20.     for (auto e : l)
21.     {
22.         cout << e <<endl;
23.     }
24. }

复制代码

2. list的模拟实现

2.1 模拟实现list

要模拟实现list，必须要熟悉list的底层结构以及其接口的含义，通过上面的学习，这些内容已基本把握，现在我们来模拟实现list。

1. namespace xwy {
2.         template<typename T>
3.         struct listNode
4.         {
5.                 T _data;
6.                 listNode<T>* _pre;
7.                 listNode<T>* _next;
8.                 //单参数构造函数
9.                 listNode(const T& val = T())
10.                         :_data(val),
11.                         _pre(nullptr),
12.                         _next(nullptr)
13.                 {
15.                 }
17.                
18.         };
19.         template<typename T, class Ref, class Ptr>
20.         struct _list_iterator
21.         {
22.                 //  受类域的限制
23.                 typedef listNode<T> Node;
24.                 typedef _list_iterator<T,Ref,Ptr> self;
25.                 Node* _node;
26.                 _list_iterator(Node *node=nullptr):
27.                         _node(node)
28.                 {
30.                 }
31.                 //操作符重载
32.                 Ref operator*()
33.                 {
34.                         return _node->_data;
35.                 }
36.                 Ptr operator->()
37.                 {
38.                         return &(_node->_data);
39.                 }
41.                 self& operator--()
42.                 {
43.                         _node = _node->_pre;
44.                         return *this;
45.                 }
46.                 self operator-(int a)
47.                 {
48.                         Node* ptr = _node;
50.                         while (a--&&ptr)
51.                         {
52.                                 ptr = ptr->_pre;
53.                         }
54.                         return ptr;
55.                 }
57.                 self& operator++()
58.                 {
59.                         _node = _node->_next;
60.                         return *this;
61.                 }
62.                 self operator++(int)
63.                 {
64.                         //  self tmp(*this)  拷贝构造自己
65.                         Node* tmp = _node;
66.                         _node = _node->_next;
67.                         return tmp;
68.                        
69.                 }
71.                 bool operator!=(const self& node)const
72.                 {
73.                         return _node != node._node;
74.                 }
76.         };
77.         // 适配器 -- 复用
78.         template<class Iterator, class Ref, class Ptr>
79.         struct Reverse_iterator
80.         {
81.                 Iterator _it;
82.                 typedef  Reverse_iterator<Iterator, Ref, Ptr> self;
83.                 Reverse_iterator(const Iterator &it):
84.                         _it(it)
85.                 {
87.                 }
88.                 //操作符重载
89.                 Ref operator*()
90.                 {
91.                         return *_it;
92.                 }
93.                 self& operator--()
94.                 {
95.                         ++_it;
96.                         return *this;
97.                 }
99.                 Ptr operator->()
100.                 {
101.                         return &(*_it);
102.                 }
104.                 self& operator++()
105.                 {
106.                         --_it;
107.                         return *this;
108.                 }
109.                 self operator++(int)
110.                 {
111.                         //  self tmp(*this)  拷贝构造自己
112.                         Iterator it = _it;
113.                         --_it;
114.                         return it;
116.                 }
118.                 bool operator!=(const self& lt) const   //const和const比较 ，非const和const比较
119.                 {
120.                         return lt._it != _it;   //不支持那两种类型的比较，是因为不存在那两种类型比较的重载
121.                 }
124.         };
126.         template<typename T>
127.         class list
128.         {
129.         public:
130.                 typedef listNode<T> Node;
131.                 typedef _list_iterator<T,T&,T*> iterator;   
132.                 typedef _list_iterator<T, const T&, const T*> const_iterator;
133.                 typedef Reverse_iterator<iterator,T&,T*> reverse_iterator;
134.                 typedef Reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;
135.                 //无参构造函数
136.                 list()
137.                 {
138.                         empty_init();
139.                        
140.                 }
141.                 template<class iterator>
142.                 list(iterator first,iterator last)
143.                 {
144.                         empty_init();
145.                         while (first != last)
146.                         {
147.                                 push_back(*first);
148.                                 first++;
149.                         }
150.                 }
151.                 //拷贝构造
152.                 list(const list& lt)
153.                 {
154.                         empty_init();
155.                         auto it = lt.begin();
156.                         while (it != lt.end())
157.                         {
158.                                 push_back(*it);
159.                                 it++;
160.                         }
162.                 }
164.                 //迭代器的实现
165.                 iterator begin()
166.                 {
167.                         return _head->_next;
168.                 }
170.                 iterator end()
171.                 {
172.                         return _head;
173.                 }
174.                 const_iterator begin() const
175.                 {
176.                         return _head->_next;
177.                 }
179.                 const_iterator end() const
180.                 {
181.                         return _head;
182.                 }
185.                 //反向迭代器
186.                 reverse_iterator rbegin()
187.                 {
188.                         return --end();
189.                 }
190.                 reverse_iterator rend()
191.                 {
192.                         return --begin();
193.                 }
195.                 const_reverse_iterator rbegin() const
196.                 {
197.                         return --end();
198.                 }
199.                 const_reverse_iterator rend() const
200.                 {
201.                         return --begin();
202.                 }
204.                
206.                 void push_back(const T& val)
207.                 {
208.                         Node* newnode = new Node(val);
209.                         newnode->_next = _head;
210.                         _head->_pre->_next = newnode;
211.                         newnode->_pre = _head->_pre;
212.                         _head->_pre = newnode;
213.                 }
216.                 iterator erase(iterator pos) //在pos位置删除
217.                 {
218.                         Node* cur = pos._node;
219.                         Node* prev = cur->_pre;
220.                         Node* next = cur->_next;
221.                         delete cur;
222.                         prev->_next = next;
223.                         next->_pre = prev;
224.                
225.                         return next;
226.                 }
227.                 // 在pos位置前插入值为val的节点
228.                 iterator insert(iterator pos, const T& val)
229.                 {
230.                         Node* cur = pos._node;
231.                         Node* newNode = new Node(val);
232.                         newNode->_next = cur;
233.                         newNode->_pre = cur->_pre;
234.                         cur->_pre->_next = newNode;
235.                         cur->_pre = newNode;
236.                         return pos;
237.                 }
238.                 /*void push_back(const T& val)
239.                 {
240.                         insert(_head, val);
241.                 }*/
242.                 void push_front(const T& val)
243.                 {
244.                         insert(_head->_next, val);
245.                 }
248.                 void swap(list<T>& l)
249.                 {
250.                         std::swap(l._head, _head);
251.                 }
252.        
253.                 void clear()
254.                 {
255.                         //清理数据,不清头节点
256.                         iterator it = begin();
257.                         while (it != end())
258.                         {
259.                                 it = erase(it);//it就是下一个位置
260.                         }
261.                 }
263.                 ~list()
264.                 {
265.                         clear();
266.                         delete _head;                // 只有节点是new出来，需要delete，但这个只delete 了一个节点
267.                 }
269.         private:
270.                 void empty_init()
271.                 {
272.                         _head = new Node();
273.                         _head->_next = _head->_pre = _head;
274.                 }
275.                 Node* _head;  
276.         };

复制代码

2.2 list的反向迭代器

反向迭代器的++就是正向迭代器的--，反向迭代器的--就是正向迭代器的++，因此反向迭代器的实现可以借助正向迭代器，即：反向迭代器内部可以包含一个正向迭代器，对正向迭代器的接口举行包装即可.

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

复制代码

3. list与vector的对比

vector与list都是STL中非常紧张的序列式容器，由于两个容器的底层结构差别，导致其特性以及应用场景差别，其紧张差别如下:

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