C++根本知识7 list

1. list的先容及使用

1.1 list的先容

1.2 list的使用

1.2.1 list的构造

1.2.2 list iterator的使用

此处，各人可临时将迭代器明确成一个指针，该指针指向list中的某个节点。

   【注意】
  

• begin与end为正向迭代器，对迭代器实行++使用，迭代器向后移动
  
• rbegin(end)与rend(begin)为反向迭代器，对迭代器实行++使用，迭代器向前移动
  

  1.2.3 list capacity

1.2.4 list element access

1.2.5 list modifiers

1.2.6 list的迭代器失效

前面说过，此处各人可将迭代器临时明确成类似于指针，迭代器失效即迭代器所指向的节点的无
效，即该节点被删除了。由于list的底层结构为带头结点的双向循环链表，因此在list中举行插入
时是不会导致list的迭代器失效的，只有在删除时才会失效，而且失效的只是指向被删除节点的迭
代器，其他迭代器不会受到影响。

---

使用接口

1. #include<iostream>
2. #include<algorithm>
3. #include<list>
4. #include<vector>
5. using namespace std;

复制代码

---

1. void test_list1()
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);
9.         list<int>::iterator it = lt.begin();
10.         while (it != lt.end())
11.         {
12.                 cout << *it << " ";
13.                 ++it;
14.         }
15.         cout << endl;
17.         for (auto e : lt)
18.         {
19.                 cout << e << " ";
20.         }
21.         cout << endl;
23. }

复制代码

  支持迭代器就支持范围for
  

---

1. struct A
2. {
3. public:
4.         A(int a1 = 1, int a2 = 1)
5.                 :_a1(a1)
6.                 , _a2(a2)
7.         {
8.                 cout << "A(int a1 = 1, int a2 = 1)" << endl;
9.         }
11.         A(const A& aa)
12.                 :_a1(aa._a1)
13.                 , _a2(aa._a2)
14.         {
15.                 cout << "A(const A& aa)" << endl;
16.         }
18.         int _a1;
19.         int _a2;
20. };

复制代码

---

1. void test_list2()
2. {
3.         list<A> lt;
4.         A aa1(1, 1);
5.         lt.push_back(aa1);
6.         lt.push_back(A(2, 2));//匿名对象
7. }

复制代码

  传参走隐式范例转换
  

---

1. void test_list3()
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);
9.         lt.push_back(6);
11.         for (auto e : lt)
12.         {
13.                 cout << e << " ";
14.         }
15.         cout << endl;
17.         auto it = lt.begin();
18.         int k = 3;
19.         while (k--)
20.         {
21.                 ++it;
22.         }
24.         lt.insert(it, 30);
26.         for (auto e : lt)
27.         {
28.                 cout << e << " ";
29.         }
30.         cout << endl;
32.         int x = 0;
33.         cin >> x;
34.         it = find(lt.begin(), lt.end(), x);
35.         if (it != lt.end())
36.         {
37.                 lt.erase(it);
38.         }
40.         for (auto e : lt)
41.         {
42.                 cout << e << " ";
43.         }
44.         cout << endl;
45. }

复制代码

  list迭代器只支持了+±-运算符的重载，因此实现+=智能通过++实现
  

---

1. void test_list4()
2. {
3.         list<int> lt;
4.         lt.push_back(1);
5.         lt.push_back(20);
6.         lt.push_back(3);
7.         lt.push_back(5);
8.         lt.push_back(4);
9.         lt.push_back(5);
10.         lt.push_back(6);
12.         for (auto e : lt)
13.         {
14.                 cout << e << " ";
15.         }
16.         cout << endl;
18.         // 升序
19.         // lt.sort();
20.         // 降序 - 仿函数
21.         // less<int> ls;
22.         // greater<int> gt;
23.         // lt.sort(gt);
24.         lt.sort(greater<int>());
26.         lt.reverse();//类方法
27.         reverse(lt.begin(), lt.end());//算法库实现的
29.         for (auto e : lt)
30.         {
31.                 cout << e << " ";
32.         }
33.         cout << endl;
35.         std::list<double> first, second;
37.         first.push_back(3.1);
38.         first.push_back(2.2);
39.         first.push_back(2.9);
41.         second.push_back(3.7);
42.         second.push_back(7.1);
43.         second.push_back(1.4);
45.         first.sort();
46.         second.sort();
48.         first.merge(second);
49. }

复制代码

  排序时我们使用了一个仿函数，仿函数是一个类可以实现排序时升序照旧降序。
merge支持将将两个排序好的链表归并插入到*this中
  

---

1. void test_list5()
2. {
3.         list<int> lt;
4.         lt.push_back(1);
5.         lt.push_back(20);
6.         lt.push_back(3);
7.         lt.push_back(5);
8.         lt.push_back(5);
9.         lt.push_back(4);
10.         lt.push_back(5);
11.         lt.push_back(6);
13.         lt.sort();
14.         for (auto e : lt)
15.         {
16.                 cout << e << " ";
17.         }
18.         cout << endl;
20.         lt.unique();
21.         for (auto e : lt)
22.         {
23.                 cout << e << " ";
24.         }
25.         cout << endl;
26. }

复制代码

  unique实现删除重复元素（在链表排序好的情况下）
  

---

1. void test_list6()
2. {
3.         // 一个链表节点转移给另一个链表
4.         std::list<int> mylist1, mylist2;
5.         std::list<int>::iterator it;
7.         // set some initial values:
8.         for (int i = 1; i <= 4; ++i)
9.                 mylist1.push_back(i);      // mylist1: 1 2 3 4
11.         for (int i = 1; i <= 3; ++i)
12.                 mylist2.push_back(i * 10);   // mylist2: 10 20 30
14.         it = mylist1.begin();
15.         ++it;                         // points to 2
17.         mylist1.splice(it, mylist2); // mylist1: 1 10 20 30 2 3 4
18.         // mylist2 (empty)
19.         // "it" still points to 2 (the 5th element
21. // 调整当前链表节点的顺序
22.         list<int> lt;
23.         lt.push_back(1);
24.         lt.push_back(2);
25.         lt.push_back(3);
26.         lt.push_back(4);
27.         lt.push_back(5);
28.         lt.push_back(6);
29.         for (auto e : lt)
30.         {
31.                 cout << e << " ";
32.         }
33.         cout << endl;
35.         int x = 0;
36.         cin >> x;
37.         it = find(lt.begin(), lt.end(), x);
38.         if (it != lt.end())
39.         {
40.                 //lt.splice(lt.begin(), lt, it);
41.                 lt.splice(lt.begin(), lt, it, lt.end());
42.         }
44.         for (auto e : lt)
45.         {
46.                 cout << e << " ";
47.         }
48.         cout << endl;
49. }

复制代码

  splice实现粘连可以是一个链表内部的粘连也可以是两个链表去粘连

  

• 将链表x的全部结点粘连在position之前
  
• 将链表x中的i结点粘连在position之前
  
• 将链表x的迭代去区间粘连在position之前
  

  

---

1. void test_op()
2. {
3.         srand(time(0));
4.         const int N = 1000000;
6.         list<int> lt1;
7.         list<int> lt2;
9.         for (int i = 0; i < N; ++i)
10.         {
11.                 auto e = rand() + i;
12.                 lt1.push_back(e);
13.                 lt2.push_back(e);
14.         }
16.         int begin1 = clock();
17.         // 拷贝vector
18.         vector<int> v(lt2.begin(), lt2.end());
20.         // 排序
21.         sort(v.begin(), v.end());
23.         // 拷贝回lt2
24.         lt2.assign(v.begin(), v.end());
26.         int end1 = clock();
28.         int begin2 = clock();
29.         lt1.sort();
30.         int end2 = clock();
32.         printf("list copy vector sort copy list sort:%d\n", end1 - begin1);
33.         printf("list sort:%d\n", end2 - begin2);
34. }

复制代码

  链表排序在算法库中实现，不是类方法的一部门。但是对于链表排序最好把list放到vector中排序在调用assign返回给list，在如许的代价下排序的服从也是远高于对list排序
  

---

2.1 模拟实现list

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

1. #pragma once
2. #include<assert.h>
3. #include<iostream>
4. using namespace std;
5. namespace Yusei
6. {
7.         template<class T>
8.         struct list_node
9.         {
10.                 T _date;
11.                 list_node<T>* _next;
12.                 list_node<T>* _prev;
13.                 list_node(const T& date=T())
14.                         :_next(nullptr)
15.                         ,_prev(nullptr)
16.                         ,_date(date)
17.                 {}
18.         };
19.         template<class T, class Ref, class Ptr>
20.         struct list_iterator
21.         {
22.                 typedef list_node<T> Node;
23.                 typedef list_iterator<T, Ref, Ptr> Self;
24.                 Node* _node;
26.                 list_iterator(Node* node)
27.                         :_node(node)
28.                 {}
29.                 Ref operator*()
30.                 {
31.                         return _node->_date;
32.                 }
33.                 Ptr operator ->()
34.                 {
35.                         return &_node->_date;
36.                 }
37.                 Self& operator++()
38.                 {
39.                          _node=_node->_next;
40.                          return *this;
41.                 }
42.                 Self& operator--()
43.                 {
44.                         _node = _node->_prev;
45.                         return *this;
46.                 }
47.                 Self& operator++(int)
48.                 {
49.                         Self tmp(*this);
50.                         _node = _node->_next;
51.                         return tmp;
52.                 }
53.                 Self& operator--(int)
54.                 {
55.                         Self tmp(*this);
56.                         _node = _node->_prev;
57.                         return tmp;
58.                 }
59.                 bool operator!=(const Self& s)const
60.                 {
61.                         return _node != s._node;
62.                 }
63.                 bool operator==(const Self& s)const
64.                 {
65.                         return _node == s._node;
66.                 }
67.         };
69.         template<class T>
70.         class list
71.         {
72.                 typedef list_node<T> Node;
73.         public:
74.                 typedef list_iterator<T, T&, T*> iterator;
75.                 typedef list_iterator<T, const T&, const T*> const_iterator;
77.                 iterator begin()
78.                 {
79.                         return _head->_next;
80.                 }
82.                 iterator end()
83.                 {
84.                         return _head;
85.                 }
87.                 const_iterator begin() const
88.                 {
89.                         return _head->_next;
90.                 }
92.                 const_iterator end() const
93.                 {
94.                         return _head;
95.                 }
97.                 void empty_init()
98.                 {
99.                         _head = new Node;
100.                         _head->_next = _head;
101.                         _head->_prev = _head;
102.                         _size = 0;
103.                 }
105.                 list()
106.                 {
107.                         empty_init();
108.                 }
110.                 list(initializer_list<T> il)
111.                 {
112.                         empty_init();
113.                         for (auto& e : il)
114.                         {
115.                                 push_back(e);
116.                         }
117.                 }
119.                 list(const list<T>& lt)
120.                 {
121.                         empty_init();
123.                         for (auto& e : lt)
124.                         {
125.                                 push_back(e);
126.                         }
127.                 }
129.                 void swap(list<T>& lt)
130.                 {
131.                         std::swap(_head, lt._head);
132.                         std::swap(_size, lt._size);
133.                 }
135.                 list<T>& operator=(list<T> lt)
136.                 {
137.                         swap(lt);
138.                         return *this;
139.                 }
141.                 ~list()
142.                 {
143.                         clear();
144.                         delete _head;
145.                         _head = nullptr;
146.                 }
148.                 void clear()
149.                 {
150.                         auto it = begin();
151.                         while (it != end())
152.                         {
153.                                 it = erase(it);
154.                         }
155.                 }
157.                 iterator insert(iterator pos, const T& x)
158.                 {
159.                         Node* cur = pos._node;
160.                         Node* prev = cur->_prev;
161.                         Node* newnode = new Node(x);
163.                         // prev newnode cur
164.                         newnode->_next = cur;
165.                         cur->_prev = newnode;
166.                         newnode->_prev = prev;
167.                         prev->_next = newnode;
169.                         ++_size;
171.                         return newnode;
172.                 }
174.                 void push_back(const T& x)
175.                 {
176.                         insert(end(), x);
177.                 }
179.                 void push_front(const T& x)
180.                 {
181.                         insert(begin(), x);
182.                 }
184.                 iterator erase(iterator pos)
185.                 {
186.                         assert(pos != end());
188.                         Node* prev = pos._node->_prev;
189.                         Node* next = pos._node->_next;
191.                         prev->_next = next;
192.                         next->_prev = prev;
193.                         delete pos._node;
195.                         --_size;
197.                         return next;
198.                 }
200.                 void pop_back()
201.                 {
202.                         erase(--end());
203.                 }
205.                 void pop_front()
206.                 {
207.                         erase(begin());
208.                 }
210.                 size_t size() const
211.                 {
212.                         return _size;
213.                 }
215.                 bool empty() const
216.                 {
217.                         return _size == 0;
218.                 }
219.         private:
220.                 Node* _head;
221.                 size_t _size;
222.         };
224.         struct AA
225.         {
226.                 int _a1 = 1;
227.                 int _a2 = 1;
228.         };
230.         template<class Container>
231.         void print_container(const Container& con)
232.         {
233.                 typename Container::const_iterator it = con.begin();
234.                 //auto it = con.begin();
235.                 while (it != con.end())
236.                 {
237.                         //*it += 10;
239.                         cout << *it << " ";
240.                         ++it;
241.                 }
242.                 cout << endl;
244.                 for (auto e : con)
245.                 {
246.                         cout << e << " ";
247.                 }
248.                 cout << endl;
249.         }
251.         void test_list1()
252.         {
253.                 list<int> lt;
254.                 lt.push_back(1);
255.                 lt.push_back(2);
256.                 lt.push_back(3);
257.                 lt.push_back(4);
259.                 list<int>::iterator it = lt.begin();
260.                 while (it != lt.end())
261.                 {
262.                         *it += 10;
264.                         cout << *it << " ";
265.                         ++it;
266.                 }
267.                 cout << endl;
269.                 for (auto e : lt)
270.                 {
271.                         cout << e << " ";
272.                 }
273.                 cout << endl;
274.                 print_container(lt);
276.                 list<AA> lta;
277.                 lta.push_back(AA());
278.                 lta.push_back(AA());
279.                 lta.push_back(AA());
280.                 lta.push_back(AA());
281.                 list<AA>::iterator ita = lta.begin();
282.                 while (ita != lta.end())
283.                 {
284.                         cout << ita->_a1 << ":" << ita->_a2 << endl;
285.                         cout << ita.operator->()->_a1 << ":" << ita.operator->()->_a2 << endl;
287.                         ++ita;
288.                 }
289.                 cout << endl;
290.         }
292.         void test_list2()
293.         {
294.                 list<int> lt;
295.                 lt.push_back(1);
296.                 lt.push_back(2);
297.                 lt.push_back(3);
298.                 lt.push_back(4);
300.                 // insert以后迭代器不失效
301.                 list<int>::iterator it = lt.begin();
302.                 lt.insert(it, 10);
303.                 *it += 100;
305.                 print_container(lt);
307.                 // erase以后迭代器失效
308.                 // 删除所有的偶数
309.                 it = lt.begin();
310.                 while (it != lt.end())
311.                 {
312.                         if (*it % 2 == 0)
313.                         {
314.                                 it = lt.erase(it);
315.                         }
316.                         else
317.                         {
318.                                 ++it;
319.                         }
320.                 }
322.                 print_container(lt);
323.         }
325.         void test_list3()
326.         {
327.                 list<int> lt1;
328.                 lt1.push_back(1);
329.                 lt1.push_back(2);
330.                 lt1.push_back(3);
331.                 lt1.push_back(4);
333.                 list<int> lt2(lt1);
335.                 print_container(lt1);
336.                 print_container(lt2);
338.                 list<int> lt3;
339.                 lt3.push_back(10);
340.                 lt3.push_back(20);
341.                 lt3.push_back(30);
342.                 lt3.push_back(40);
344.                 lt1 = lt3;
345.                 print_container(lt1);
346.                 print_container(lt3);
347.         }
349.         void func(const list<int>& lt)
350.         {
351.                 print_container(lt);
352.         }
354.         void test_list4()
355.         {
356.                 // 直接构造
357.                 list<int> lt0({ 1,2,3,4,5,6 });
358.                 // 隐式类型转换
359.                 list<int> lt1 = { 1,2,3,4,5,6,7,8 };
360.                 const list<int>& lt3 = { 1,2,3,4,5,6,7,8 };
362.                 func(lt0);
363.                 func({ 1,2,3,4,5,6 });
365.                 print_container(lt1);
367.                 //auto il = { 10, 20, 30 };初始化列表
368.         /*        initializer_list<int> il = { 10, 20, 30 };
369.                 cout << typeid(il).name() << endl;
370.                 cout << sizeof(il) << endl;*/
371.         }
372. }

复制代码