C++STl——list

list的细节

list的细节之一就是其迭代器没有利用指针了，由于指针是无法到达迭代器的效果的，再增补下迭代器的范例，迭代器分为单向，双向，随机迭代器，单向迭代器的容器有forward_list，unordered_map等，单向迭代器只支持++，双向迭代器有list,map，双向迭代器支持++与–，随机迭代器有string，vector，deque支持++，–，+，-，迭代器的名字决定了其范例，list本身是有sort函数的，但是服从过低，不如将他粘贴到vector进行sort在粘贴返来，后续有代码证实。list也存在迭代器失效问题，list的insert相比于vector是没有失效问题的，由于list的insert不存在扩容问题，根本全部的erase都有迭代器失效问题，以是每个erase都会返回删除下一个位置的迭代器，string也是有的，只是string更风俗用[]而不是迭代器进行访问。
头文件

1. #pragma once
3. #include<assert.h>
5. namespace prime
6. {
7.         template<class T>
8.         struct list_node
9.         {
10.                 list_node* _next;
11.                 list_node* _prev;
12.                 T _data;
14.                 list_node(const T& x = T())
15.                         :_next(nullptr)
16.                         , _prev(nullptr)
17.                         , _data(x)
18.                 {}
19.         };
20.         //这里是封装了iterator类，因为list的原生指针无法作为迭代器
21.         // typedef list_iterator<T, T&, T*> iterator;三个模版参数，是为了后面的const做铺垫
22.         // 如果需要const迭代器，我们是没办法完成的，所以这里封装一个const_iterator，由于普通ite与const的区别
23.         // 就只有*上，所以就通过添加参数来进行合并
24.         // typedef list_iterator<T, const T&, const T*> const_iterator;
25.         template<class T, class Ref, class Ptr>
26.         struct list_iterator
27.         {
28.                 typedef list_node<T> Node;
29.                 typedef list_iterator<T, Ref, Ptr> Self;
30.                 Node* _node;
32.                 list_iterator(Node* node)
33.                         :_node(node)
34.                 {}
36.                 Ref operator*()
37.                 {
38.                         return _node->_data;
39.                 }
41.                 Ptr operator->()
42.                 {
43.                         return &_node->_data;
44.                 }
46.                 Self& operator++()
47.                 {
48.                         _node = _node->_next;
49.                         return *this;
50.                 }
52.                 Self operator++(int)//因为tmp会销毁，所以不能传引用
53.                 {
54.                         Self tmp(*this);
55.                         _node = _node->_next;
57.                         return tmp;
58.                 }
60.                 Self& operator--()
61.                 {
62.                         _node = _node->_prev;
63.                         return *this;
64.                 }
66.                 Self operator--(int)
67.                 {
68.                         Self tmp(*this);
69.                         _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.         struct list_const_iterator
87.         {
88.                 typedef list_node<T> Node;
89.                 typedef list_const_iterator<T> Self;
90.                 Node* _node;
92.                 list_const_iterator(Node* node)
93.                         :_node(node)
94.                 {}
96.                 const T& operator*()
97.                 {
98.                         return _node->_data;
99.                 }
101.                 Self& operator++()
102.                 {
103.                         _node = _node->_next;
104.                         return *this;
105.                 }
107.                 Self operator++(int)
108.                 {
109.                         Self tmp(*this);
110.                         _node = _node->_next;
112.                         return tmp;
113.                 }
115.                 Self& operator--()
116.                 {
117.                         _node = _node->_prev;
118.                         return *this;
119.                 }
121.                 Self operator--(int)
122.                 {
123.                         Self tmp(*this);
124.                         _node = _node->_prev;
126.                         return tmp;
127.                 }
129.                 bool operator!=(const Self& s) const
130.                 {
131.                         return _node != s._node;
132.                 }
134.                 bool operator==(const Self& s) const
135.                 {
136.                         return _node == s._node;
137.                 }
138.         };*/
140.         template<class T>
141.         class list
142.         {
143.                 typedef list_node<T> Node;
144.         public:
145.                 typedef list_iterator<T, T&, T*> iterator;
146.                 //typedef list_const_iterator<T> const_iterator;
147.                 typedef list_iterator<T, const T&, const T*> const_iterator;
149.                 iterator begin()
150.                 {
151.                         return iterator(_head->_next);
152.                 }
154.                 iterator end()
155.                 {
156.                         return iterator(_head);
157.                 }
159.                 const_iterator begin() const
160.                 {
161.                         return const_iterator(_head->_next);
162.                 }
164.                 const_iterator end() const
165.                 {
166.                         return const_iterator(_head);
167.                 }
168.                 //这里单独封装一个初始化函数不选择用初始化列表进行初始化，是因为后续需要额外创建链表时需要初始化
169.                 //初始化头节点需要创建Node对象并设置其_next和_prev指针指向自身。
170.                 //这类多步操作无法直接在构造函数的初始化列表中完成（初始化列表仅支持表达式，不支持语句）
171.                 void empty_init()
172.                 {
173.                         _head = new Node;
174.                         _head->_next = _head;
175.                         _head->_prev = _head;
177.                         _size = 0;
178.                 }
180.                 list()
181.                 {
182.                         empty_init();
183.                 }
185.                 list(initializer_list<T> il)
186.                 {
187.                         empty_init();
188.                         for (auto& e : il)
189.                         {
190.                                 push_back(e);
191.                         }
192.                 }
194.                 // lt2(lt1)
195.                 //list(const list<T>& lt)
196.                 list(list<T>& lt)
197.                 {
198.                         empty_init();
199.                         for (auto& e : lt)
200.                         {
201.                                 push_back(e);
202.                         }
203.                 }
205.                 void swap(list<T>& lt)
206.                 {
207.                         std::swap(_head, lt._head);
208.                         std::swap(_size, lt._size);
209.                 }
211.                 // lt1 = lt3
212.                 list<T>& operator=(list<T> lt)
213.                 {
214.                         swap(lt);
215.                         return *this;
216.                 }
218.                 ~list()
219.                 {
220.                         clear();
221.                         delete _head;
222.                         _head = nullptr;
223.                 }
225.                 void clear()
226.                 {
227.                         auto it = begin();
228.                         while (it != end())
229.                         {
230.                                 it = erase(it);
231.                         }
232.                 }
234.                 size_t size()
235.                 {
236.                         return _size;
237.                 }
239.                 void push_back(const T& x)
240.                 {
241.                         /*Node* tail = _head->_prev;
242.                         Node* newnode = new Node(x);
244.                         tail->_next = newnode;
245.                         newnode->_prev = tail;
246.                         newnode->_next = _head;
247.                         _head->_prev = newnode;*/
248.                         insert(end(), x);
249.                 }
251.                 void push_front(const T& x)
252.                 {
253.                         insert(begin(), x);
254.                 }
256.                 void pop_back()
257.                 {
258.                         erase(--end());
259.                 }
261.                 void pop_front()
262.                 {
263.                         erase(begin());
264.                 }
266.                 void insert(iterator pos, const T& x)
267.                 {
268.                         Node* cur = pos._node;
269.                         Node* prev = cur->_prev;
270.                         Node* newnode = new Node(x);
271.                         // prev newnode cur
272.                         prev->_next = newnode;
273.                         newnode->_prev = prev;
274.                         newnode->_next = cur;
275.                         cur->_prev = newnode;
277.                         ++_size;
278.                 }
280.                 iterator erase(iterator pos)
281.                 {
282.                         assert(pos != end());
284.                         Node* cur = pos._node;
285.                         Node* prev = cur->_prev;
286.                         Node* next = cur->_next;
288.                         prev->_next = next;
289.                         next->_prev = prev;
291.                         delete cur;
293.                         --_size;
295.                         //return iterator(next);
296.                         return next;
297.                 }
298.         private:
299.                 Node* _head;
300.                 size_t _size;
301.         };
303.         void test_list1()
304.         {
305.                 list<int> lt;
306.                 lt.push_back(1);
307.                 lt.push_back(2);
308.                 lt.push_back(3);
309.                 lt.push_back(4);
311.                 list<int>::iterator it = lt.begin();
312.                 while (it != lt.end())
313.                 {
314.                         *it += 10;
315.                         cout << *it << " ";
316.                         ++it;
317.                 }
318.                 cout << endl;
320.                 lt.push_front(1);
321.                 lt.push_front(2);
322.                 lt.push_front(3);
323.                 lt.push_front(4);
325.                 for (auto e : lt)
326.                 {
327.                         cout << e << " ";
328.                 }
329.                 cout << endl;
331.                 lt.pop_back();
332.                 lt.pop_back();
333.                 lt.pop_front();
334.                 lt.pop_front();
336.                 for (auto e : lt)
337.                 {
338.                         cout << e << " ";
339.                 }
340.                 cout << endl;
341.         }
343.         void test_list2()
344.         {
345.                 list<int> lt;
346.                 lt.push_back(1);
347.                 lt.push_back(2);
348.                 lt.push_back(3);
349.                 lt.push_back(4);
351.                 list<int>::iterator it = lt.begin();
352.                 while (it != lt.end())
353.                 {
354.                         if (*it % 2 == 0)
355.                         {
356.                                 it = lt.erase(it);
357.                         }
358.                         else
359.                         {
360.                                 ++it;
361.                         }
362.                 }
364.                 for (auto e : lt)
365.                 {
366.                         cout << e << " ";
367.                 }
368.                 cout << endl;
369.         }
371.         // const T* p1;
372.         // T* const p2;
373.         void print(const list<int>& lt)
374.         {
375.                 // const迭代器的要求不是本身不能修改，而是指向的内容不能修改
376.                 //const list<int>::iterator it = lt.begin();
377.                 list<int>::const_iterator it = lt.begin();
378.                 while (it != lt.end())
379.                 {
380.                         // *it = 10;
381.                         cout << *it << " ";
382.                         ++it;
383.                 }
384.                 cout << endl;
385.         }
387.         void test_list3()
388.         {
389.                 list<int> lt1;
390.                 lt1.push_back(1);
391.                 lt1.push_back(2);
392.                 lt1.push_back(3);
393.                 lt1.push_back(4);
395.                 for (auto e : lt1)
396.                 {
397.                         cout << e << " ";
398.                 }
399.                 cout << endl;
401.                 list<int> lt2(lt1);
403.                 for (auto e : lt2)
404.                 {
405.                         cout << e << " ";
406.                 }
407.                 cout << endl;
409.                 list<int> lt3 = { 1,2,3,4,5,6 };
410.                 lt1 = lt3;
412.                 for (auto e : lt1)
413.                 {
414.                         cout << e << " ";
415.                 }
416.                 cout << endl;
417.         }
419.         struct AA
420.         {
421.                 int _a1;
422.                 int _a2;
424.                 AA(int a1 = 1, int a2 = 1)
425.                         :_a1(a1)
426.                         , _a2(a2)
427.                 {}
428.         };
430.         void test_list4()
431.         {
432.                 //AA aa1 = { 1,1 };
433.                 vector<AA> v1;
434.                 v1.push_back({ 1,1 });
435.                 v1.push_back({ 2,2 });
436.                 v1.push_back({ 3,3 });
437.                 vector<AA>::iterator it1 = v1.begin();
438.                 while (it1 != v1.end())
439.                 {
440.                         cout << it1->_a1 << ":" << it1->_a2 << endl;
441.                         ++it1;
442.                 }
443.                 cout << endl;
445.                 list<AA> lt1;
446.                 lt1.push_back({ 1,1 });
447.                 lt1.push_back({ 2,2 });
448.                 lt1.push_back({ 3,3 });
449.                 list<AA>::iterator lit1 = lt1.begin();
450.                 while (lit1 != lt1.end())
451.                 {
452.                         //cout << (*lit1)._a1 <<":"<< (*lit1)._a2 << endl;
453.                         // 特殊处理，省略了一个->,为了可读性
454.                         cout << lit1->_a1 << ":" << lit1->_a2 << endl;
455.                         cout << lit1.operator->()->_a1 << ":" << lit1.operator->()->_a2 << endl;
457.                         ++lit1;
458.                 }
459.                 cout << endl;
460.         }
461. }

复制代码

源码

1. #define _CRT_SECURE_NO_WARNINGS
3. #include<iostream>
4. #include<list>
5. #include<vector>
6. #include<algorithm>
8. using namespace std;
10. //int main()
11. //{
12. //        // 21:05
13. //        list<int> lt1 = {1,2,2,2,3,3,4,2,3,5,6};
14. //        for (auto e : lt1)
15. //        {
16. //                cout << e << " ";
17. //        }
18. //        cout << endl;
19. //        sort(lt1.begin(), lt1.end());
20. //
21. //        /*lt1.sort();
22. //        lt1.unique();*/
23. //        lt1.remove(2);
24. //        for (auto e : lt1)
25. //        {
26. //                cout << e << " ";
27. //        }
28. //        cout << endl;
29. //
30. //        return 0;
31. //}
33. void test_op1()
34. {
35.         srand(time(0));
36.         const int N = 1000000;
38.         list<int> lt1;
39.         vector<int> v;
41.         for (int i = 0; i < N; ++i)
42.         {
43.                 auto e = rand() + i;
44.                 lt1.push_back(e);
45.                 v.push_back(e);
46.         }
48.         int begin1 = clock();
49.         // 排序
50.         sort(v.begin(), v.end());
51.         int end1 = clock();
53.         int begin2 = clock();
54.         lt1.sort();
55.         int end2 = clock();
57.         printf("vector sort:%d\n", end1 - begin1);
58.         printf("list sort:%d\n", end2 - begin2);
59. }
61. void test_op2()
62. {
63.         srand(time(0));
64.         const int N = 1000000;
66.         list<int> lt1;
67.         list<int> lt2;
69.         for (int i = 0; i < N; ++i)
70.         {
71.                 auto e = rand() + i;
72.                 lt1.push_back(e);
73.                 lt2.push_back(e);
74.         }
76.         int begin1 = clock();
77.         // 拷贝vector
78.         vector<int> v(lt2.begin(), lt2.end());
79.         // 排序
80.         sort(v.begin(), v.end());
82.         // 拷贝回lt2
83.         lt2.assign(v.begin(), v.end());
85.         int end1 = clock();
87.         int begin2 = clock();
88.         lt1.sort();
89.         int end2 = clock();
91.         printf("list copy vector sort copy list sort:%d\n", end1 - begin1);
92.         printf("list sort:%d\n", end2 - begin2);
93. }
95. void test_list1()
96. {
97.         // 一个链表的节点移动到另一个链表
98.         std::list<int> lt1 = { 1, 2, 3, 4, 5 };
99.         std::list<int> lt2 = { 10, 20, 30, 40 };
100.         for (auto e : lt1)
101.         {
102.                 cout << e << " ";
103.         }
104.         cout << endl;
106.         for (auto e : lt2)
107.         {
108.                 cout << e << " ";
109.         }
110.         cout << endl;
112.         lt1.splice(lt1.begin(), lt2);
113.         for (auto e : lt1)
114.         {
115.                 cout << e << " ";
116.         }
117.         cout << endl;
119.         for (auto e : lt2)
120.         {
121.                 cout << e << " ";
122.         }
123.         cout << endl;
125.         // 一个链表中节点调整顺序
126.         std::list<int> lt3 = { 1, 2, 3, 4, 5 };
127.         int x;
128.         cin >> x;
129.         auto it = find(lt3.begin(), lt3.end(), x);
130.         if (it != lt3.end())
131.         {
132.                 lt3.splice(lt3.begin(), lt3, it);
133.         }
135.         for (auto e : lt3)
136.         {
137.                 cout << e << " ";
138.         }
139.         cout << endl;
140. }
142. #include"List.h"
144. int main()
145. {
146.         prime::test_list4();
148.         return 0;
149. }

复制代码