移情别恋c++ ദ്ദി˶ｰ̀֊ｰ́ ) ——7.list（模仿实现） ...

1.前言

1.1list与vector的不同

   区别：list的迭代器底层和其他两个迭代器底层有很大区别，因为list的链式结构决定了与它们两个的不一样
  相同：迭代器用法大致一样，其他成员函数的使用也大致一样。
  
  vector与list都是STL中非常紧张的序列式容器，由于两个容器的底层结构不同，导致其特性以及 应用场景不同，其主要不同如下
  

  1.2 迭代器的分类 

   

  

 例子：

   可以得知list类型无法使用std中的sort函数，因为list的迭代器是双向的，而sort函数的迭代器参数是随机的 ，同理可以得出，string，vector，deque都可以使用std中的sort
   1.3 list的本质

   带头双向循环链表！！！！！！！！！！！！！！！！！！！
  2.list节点 

  

1. template<class T>//记得每一个类前要写模板
2. struct list_node       //struct和class一样均为类，不同的是struct中的所有成员均为公有（public）类型，可直接访问
3. {
4.         T data;
5.         list_node<T>* next;
6.         list_node<T>* prev;
9.         list_node(const T& x=T())  //const T& x=T()，在没有给值的情况下，系统会通过T（）自动生成一个类型匹配的值赋给x
10.                 :data(x)
11.                 ,next(nullptr)
12.                 ,prev(nullptr)
13.         {}
16. };

复制代码

用类来封装一个一个结点，内里有两个指针，一个是指向下一个位置的指针，一个是指向前一个位置，还有一个用来存放数据的变量
  3.list类框架 

  

1. template<class T>
2. class List
3. {
4. public:
5.         typedef List_node<T> node;//取别名
6.     void empty_list()
7.         {
8.                 head = new Node;
9.                 head->_next = head;
10.                 head->_prev = head;
11.         }
12.         List()//构造函数
13.         {
14.             empty_list();
15.         }
16. private:
17.      node*head;//头节点
18.      size_t _size;
19. }

复制代码

list类内里包含的是结点的指针，也就是哨兵位头节点的指针
  4.list迭代器

4.1 list迭代器框架

   这里的迭代器是用封装加运算符重载来实现的，由于迭代器也会有许多类型，以是我们使用模板的情势

1. //T,T&,T*
2. //T,const T&,const T*        //设定了两种迭代器
3. template<class T,class Ref,class Ptr>//记得每一个类前要写模板,可设置多个模板参数
4. struct list_iterator
5. {
6.         typedef list_node<T> node;
7.         typedef list_iterator<T,Ref,Ptr> self;
8.         node* node1;
11.         list_iterator(node* node2)
12.                 :node1(node2)
13.         {}
14. }

复制代码

4.2 list常用迭代器 

  

1. //T,T&,T*
2. //T,const T&,const T*        //设定了两种迭代器
4. template<class T,class Ref,class Ptr>//记得每一个类前要写模板,可设置多个模板参数
5. struct list_iterator
6. {
7.         typedef list_node<T> node;
8.         typedef list_iterator<T,Ref,Ptr> self;
9.         node* node1;
12.         list_iterator(node* node2)
13.                 :node1(node2)
14.         {}
16.         self& operator++()
17.         {
18.                 node1 = node1->next;
19.                 return *this;           //模拟++
20.         }
22.         self& operator--()
23.         {
24.                 node1 = node1->prev;
25.                 return *this;           //模拟--
26.         }
29.         Ref operator*()
30.         {
31.                 return node1->data;    //模拟指针解引用
32.         }
35.         Ptr operator->()
36.         {
37.                 return &node1->data;
38.         }
40.         bool operator!=(const self& S)
41.         {
42.                 return node1 != S.node1;
43.         }
45. };

复制代码

迭代器的每一个操作都接纳了运算符重载，着实这样看来还是指针在操作，只不外他不是直接的进行操作，而是换了一种方式
  5.list函数详解 

5.1插入和删除

  

1. void push_back(const T& x)  //尾插
2. {
3.         insert(end(), x);
4. }
6. void push_front(const T& x)  //头插
7. {
8.         insert(begin(), x);
9. }
11. void pop_front()      //头删
12. {
13.         erase(begin());
14. }
16. void pop_back()      //尾删
17. {
18.         erase(--end());
19. }
21. iterator insert(iterator pos, const T& x)//在pos位置插入x
22. {
23.         node* it = pos.node1;
24.         node* newnode = new node(x);
25.         node* prev = it->prev;
26.         prev->next = newnode;
27.         newnode->prev = prev;
28.         newnode->next = it;
29.         it->prev = newnode;
31.         ++_size;
33.         return iterator(newnode);                    //返回新插入的元素的位置
34. }
36. iterator erase(iterator pos)
37. {
38.         node* it = pos.node1;
39.         node* prev = it->prev;
40.         node* next = it->next;
42.         delete it;
43.         prev->next = next;
44.         next->prev = prev;
45.         --_size;
47.         return iterator(next);       //返回删除后的当前位置
48. }

复制代码

  5.2  拷贝构造和赋值运算符重载

  

1. list(const list<T>& it)    //i1(i2)
2. {
3.         int i = 0;
4.         empty_list();  //初始化列表
5.         for (auto e : it)  //相当于自动调用迭代器，并解引用，最后迭代器再++
6.         {
7.                 i = 1;
8.                 push_back(e);
9.         }
11. }
14. void swap(list<T>& it)
15. {
16.         std::swap(head, it.head);
17.         std::swap(_size, it._size);
18. }
20. list operator=(list<T>it)// i1=i2      传参直接调用拷贝构造
21. {
22.         swap(it);
23.         return *this;
24. }
27. size_t size()
28. {
29.         return _size;
30. }

复制代码

5.3 list析构函数 

  

1. ~list()
2. {
3.         clear();
4.         delete head;
5.         head = nullptr;
7. }
9. void clear()
10. {
11.         iterator it = begin();
12.         while (it != end())
13.         {
14.                 it = erase(it);
15.         }
17. }

复制代码

  6.打印函数 

  

1. //打印
2. template<typename Container>
3. void print_container(const Container& con)
4. {
5.         typename Container::const_iterator it = con.begin();
6.         while (it != con.end())
7.         {
8.                 cout << *it << " ";
9.                 ++it;
10.         }
11.         cout << endl;
12. }

复制代码

这里用的是typename，原因在于编译器在编译的时间，会去Container内里去找const_iterator这个类型，但是Container是一个模板，并没有实例化，以是编译器也不知道怎么定义，以是就在编译的时间就过不了，但是我们在前面加一个typename就会告诉编译器，先过，后面再来实例化，这样就可以办理问题了
  
  适用于不知道list<T>中的T到底是什么类型时同一调用打印函数
  7.代码总览

1. namespace zone
2. {
3.         template<class T>//记得每一个类前要写模板
4.         struct list_node       //struct和class一样均为类，不同的是struct中的所有成员均为公有（public）类型，可直接访问
5.         {
6.                 T data;
7.                 list_node<T>* next;
8.                 list_node<T>* prev;
11.                 list_node(const T& x=T())  //const T& x=T()，在没有给值的情况下，系统会通过T（）自动生成一个类型匹配的值赋给x
12.                         :data(x)
13.                         ,next(nullptr)
14.                         ,prev(nullptr)
15.                 {}
18.         };     
20.         //T,T&,T*
21.         //T,const T&,const T*        //设定了两种迭代器
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* node1;
30.                 list_iterator(node* node2)
31.                         :node1(node2)
32.                 {}
34.                 self& operator++()
35.                 {
36.                         node1 = node1->next;
37.                         return *this;           //模拟++
38.                 }
40.                 self& operator--()
41.                 {
42.                         node1 = node1->prev;
43.                         return *this;           //模拟--
44.                 }
46.                
48.                 Ref operator*()
49.                 {
50.                         return node1->data;    //模拟指针解引用
51.                 }
54.                 Ptr operator->()
55.                 {
56.                         return &node1->data;
57.                 }
59.                 bool operator!=(const self& S)
60.                 {
61.                         return node1 != S.node1;
62.                 }
64.         };
66.         //
67.         template<class T>//记得每一个类前要写模板
68.         class list
69.         {
70.                 typedef list_node<T> node;
72.             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 iterator(head->next);
80.                         }
83.                         iterator end()
84.                         {
85.                                 return iterator(head);
86.                         }
88.                         const_iterator begin()const   //只可读，不可写
89.                         {
90.                                 return const_iterator(head->next);
91.                         }
94.                         const_iterator end()const
95.                         {
96.                                 return const_iterator(head);
97.                         }
102.                         void empty_list()
103.                         {
104.                                 head = new node;
105.                                 head->next = head;
106.                                 head->prev = head;
107.                                 _size = 0;
108.                         }//建立头节点
110.                         list()
111.                         {
112.                                 empty_list();  //初始化列表
113.                         }
115.                         ~list()
116.                         {
117.                                 clear();
118.                                 delete head;
119.                                 head = nullptr;
121.                         }
123.                         void clear()
124.                         {
125.                                 iterator it = begin();
126.                                 while (it != end())
127.                                 {
128.                                         it = erase(it);
129.                                 }
131.                         }
133.                         void push_back(const T& x)
134.                         {
135.                                 insert(end(), x);
136.                         }
138.                         void push_front(const T& x)
139.                         {
140.                                 insert(begin(), x);
141.                         }
143.                         void pop_front()
144.                         {
145.                                 erase(begin());
146.                         }
148.                         void pop_back()
149.                         {
150.                                 erase(--end());
151.                         }
153.                         iterator insert(iterator pos, const T& x)//在pos位置插入x
154.                         {
155.                                 node* it = pos.node1;
156.                                 node* newnode = new node(x);
157.                                 node* prev = it->prev;
158.                                 prev->next = newnode;
159.                                 newnode->prev = prev;
160.                                 newnode->next = it;
161.                                 it->prev = newnode;
163.                                 ++_size;
165.                                 return iterator(newnode);                    //返回新插入的元素的位置
166.                         }
168.                         iterator erase(iterator pos)
169.                         {
170.                                 node* it = pos.node1;
171.                                 node* prev = it->prev;
172.                                 node* next = it->next;
174.                                 delete it;
175.                                 prev->next = next;
176.                                 next->prev = prev;
177.                                 --_size;
179.                                 return iterator(next);       //返回删除后的当前位置
180.                         }
183.                         list(const list<T>& it)    //i1(i2)
184.                         {
185.                                 int i = 0;
186.                                 empty_list();  //初始化列表
187.                                 for (auto e : it)  //相当于自动调用迭代器，并解引用，最后迭代器再++
188.                                 {
189.                                         i = 1;
190.                                         push_back(e);
191.                                 }
193.                         }
196.                         void swap(list<T>& it)
197.                         {
198.                                 std::swap(head, it.head);
199.                                 std::swap(_size, it._size);
200.                         }
202.                         list operator=(list<T>it)// i1=i2      传参直接调用拷贝构造
203.                         {
204.                                 swap(it);
205.                                 return *this;
206.                         }
209.                         size_t size()
210.                         {
211.                                 return _size;
212.                         }
213.                        
214.             private:
215.                         node* head;
216.                         size_t _size;
218.         };
221.         void test()
222.         {
223.                 list<int> arr; //调用class里的初始化列表
224.                 arr.push_back(1);
225.                 arr.push_back(2);
226.                 arr.push_back(3);
227.                 arr.push_back(4);
228.                 arr.push_back(5);
229.                 arr.pop_back();
231.                 int i = 0;
233.                 list<int> brr(arr);
234.                 for (auto e : brr)
235.                 {
236.                         i = 1;
237.                         cout << e << ' ';
238.                 }
240.         }
242. }

复制代码

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