【C++】—— list 模仿实现

1 list 根本结构

                                l                      i                      s                      t                          list               list 的底层就是我们之前学过的双向链表，它由一个哨兵位头结点 _pHead 和纪录链表长度的 _size 构成。
  而链表中的每个节点都是由两个自身范例指针和一个存储数据的变量构成的。因此，我们不光要界说链表的类，还要界说节点的类
  下面是                               l                      i                      s                      t                          list               list 的成员变量和团体框架

1. namespace my_list
2. {
3.         template<class T>
4.         struct ListNode
5.         {
6.                 ListNode* _prev;
7.                 ListNode* _next;
8.                 T _val;
9.                
10.                 //默认构造
11.                 ListNode(const T& val = T())
12.                         :_prev(nullptr)
13.                         ,_next(nullptr)
14.                         ,_val(val)
15.                 {}
16.         };
18.         template<class T>
19.         class list
20.         {
21.                 typedef ListNode<T> Node;//给节点重命名
22.                 //成员函数···
23.                
24.         private:
25.                 Node* _pHead;//哨兵位头结点指针
26.                 size_t _size;
27.         }
28. }

复制代码

  由于我们要频仍访问节点，因此我们直接用                                    s                         t                         r                         u                         c                         t                              struct                  struct 界说节点，其成员变量默认全公有。
  
  
2 默认构造

  我们先写一个简朴的无参默认构造出来。
  默认构造可以直接如许写吗？

1. list()
2.         :_pHead(nullptr)
3.         ,_size(0)
4. {}

复制代码

  不可以的，由于双向链表有个哨兵位。纵然链表中没有任何数据，头节点指针也是指向哨兵位，而不是空，以是我们应创建哨兵位，并将其初始化
  而哨兵位的前驱指针 _                              p                      r                      e                      v                          prev               prev 和后继指针 _                              n                      e                      x                      t                          next               next，由于整个链表只有它自己，它的前一个和后一个节点都是自己，因此 _                                   p                         r                         e                         v                              prev                  prev 和 _                                   n                         e                         x                         t                              next                  next 都是指向哨兵位自己

1. list()
2. {
3.         _pHead = new Node;
4.         _pHead->_next = _pHead;
5.         _pHead->_prev = _pHead;
6.         _size = 0；
7. }

复制代码

  其是不光仅是无参的构造，全部的构造函数第一步都是初始化哨兵位，因此我们不妨单独写一个函数出来

1. list()
2. {
3.         CreateHead()；
4. }
6. void CreateHead()
7. {
8.         _pHead = new Node;
9.         _pHead->_next = _pHead;
10.         _pHead->_prev = _pHead;
11.         _size = 0;
12. }

复制代码

  
  这里有个标题就是CreateHead()黑白                               c                      o                      n                      s                      t                          const               const 成员函数，那界说                               c                      o                      n                      s                      t                          const               const 成员是否还能来调用呢？答案天然是可以的，由于                                    c                         o                         n                         s                         t                              const                  const 变量在界说的时间是不具有                                    c                         o                         n                         s                         t                              const                  const 属性的，界说完成之后才有。好比说：

1. //如果在定义之前就具有const属性，那么n就无法赋值
2. //const变量只有在定义时可以被赋值
3. const int n = 10;
4. const list<int> l1;

复制代码

  
  
3 迭代器

  要模仿实现                               l                      i                      s                      t                          list               list ，迭代器的实现是此中的重中之重。
  前面我们模仿实现                               s                      t                      r                      i                      n                      g                          string               string 和                               v                      e                      c                      t                      o                      r                          vector               vector，他们的迭代器都是原生指针，他们的原生指针完善符合迭代器的全部要求。其本质是由于他们底层物理空间是一连的。
  但                               l                      i                      s                      t                          list               list 不像                               s                      t                      r                      i                      n                      g                          string               string 和                               v                      e                      c                      t                      o                      r                          vector               vector 那样天生丽质，它的底层结构是一个一个节点，并不一连，无法满足迭代器的要求（好比 ++，我们渴望的是迭代器跳到下一个节点，如果利用原生指针，由于不是一连的物理空间，当前节点 ++ 大概率是个野指针）。
  但没关系，                               l                      i                      s                      t                          list               list 可以通过封装，通过运算符重载，来满足迭代器的要求。
  
3.1 团体框架

  迭代器其自己就是模仿指针的举动，既然节点的原生指针无法满足迭代器的要求，我们对节点指针举行封装，通过运算符重载让其满足迭代器的需求

1. template<class T>
2. struct ListIterator
3. {
4.         typedef ListIterator<T> Self;//给自身类(迭代器)重命名，短一点方便
5.         typedef ListNode<T> Node;//节点重命名
7.         //成员变量：节点的指针
8.         Node* pNode;
10.         //成员函数
11.         //···
13. };

复制代码

  由于待会链表中要大量访问成员变量，我们直接用默认全公有的                               s                      t                      r                      u                      c                      t                          struct               struct
  
   到如今，我们一共实现了三个类，为什么要实现三个类呢？我们先把每个类的作用过一遍：
  

• class list：链表这个类是链表的根本结构，指向哨兵位的头结点，管理这整个链表
  
• struct ListNode：节点这个类是由于链表中每个节点都是自界说范例，每个数据都是存在一个独立的结构体内里
  
• struct ListIterator：迭代器这个类，遍历整个链表原来是用节点的指针，但是节点的指针是不符合我们的预期，我们渴望有一个迭代器同一的方式举行遍历，因此我们用一个结构去封装节点的指针，封装以后通过重载运算符使节点的指针能到达迭代器那样的举动
  

    
  
3.2 成员函数

  有了迭代器这个类，我们就可以运用运算符重载满足迭代器的举动啦

1. template<class T>
2. struct ListIterator
3. {
4.         typedef ListIterator<T> Self;
5.         typedef ListNode<T> Node;
7.         //成员变量
8.         Node* pNode;
9.        
10.         //解引用
11.         T& operator*()
12.         {
13.                 return pNode->_val;
14.         }
15.        
16.         //前置++
17.         Self& operator++()
18.         {
19.                 pNode = pNode->_next;
20.                 return *this;
21.         }
22.        
23.         //后置++
24.         Self& operator++(int)
25.         {
26.                 Self tmp = *this;
27.                 pNode = pNode->_next;
28.                 return tmp;
29.         }
30.        
31.         //前置--
32.         Self& operator--()
33.         {
34.                 pNode = pNode->_prev;
35.                 return *this;
36.         }
37.        
38.         //后置--
39.         Self& operator--(int)
40.         {
41.                 Self tmp = *this;
42.                 pNode = pNode->_prev;
43.                 return tmp;
44.         }
45.        
46.         //不等于
47.         bool operator!=(const Self& x)
48.         {
49.                 return pNode != x.pNode;
50.         }
51.        
52.         //等于
53.         bool operator==(const Self& x)
54.         {
55.                 return pNode == x.pNode;
56.         }
57. }

复制代码

  
  
3.3 begin() 与 end() 的实现

  迭代器的根本举动实现了，我们也可以在list类中实现begin()、end()等函数了
  begin()函数是返回第一个迭代器，我们要构造第一个位置的迭代器，那怎么构造呢？我们用第一个节点的指针，即_pHead->_next，就能构造第一个迭代器，但如今ListIterator类中还缺少一个构造函数：

1. //默认构造
2. ListIterator(Node* p = nullptr)
3.         :pNode(p)
4. {}
6. //拷贝构造
7. ListIterator(const ListIterator& x)
8. {
9.         pNode = x.pNode;
10. }

复制代码

  着实上述拷贝构造可以不消实现，编译器会自己天生一个拷贝构造，完成浅拷贝，指向链表的节点。
  这里不要以为有指针指向资源就要自己实现深拷贝，而是看指针所指向的资源是不是属于自己的。像                               s                      t                      r                      i                      n                      g                          string               string、                              v                      e                      c                      t                      o                      r                          vector               vector 那些就必要自己实现深拷贝，但迭代器指向的是链表的资源，并不是迭代器自己的，而且迭代器自己的目标就是指向链表的节点，以此来访问遍历链表，因此浅拷贝即可。
  以是赋值重载和析构与不必要写
  
  如今，万事具备只欠东风，我们还要在list类中将ListIterator类                               t                      y                      p                      e                      d                      e                      f                          typedef               typedef 成                                    i                         t                         e                         r                         a                         t                         o                         r                              iterator                  iterator

1. template<class T>
2. class list
3. {
4.         typedef ListNode<T> Node;
5.         typedef ListIterator<T> iterator;//重命名为iterator
6.         //成员函数···
7.        
8. private:
9.         Node* _pHead;
10.         size_t _size;
11. }

复制代码

  下面是begin()的实现

1. iterator begin()
2. {
3.         iterator it(_pHead->_next);
4.         return it;
5. }

复制代码

  上述是闻名对象的写法，我们可以用匿名对象的写法

1. iterator begin()
2. {       
3.         return iterator(_pHead->_next);
4. }

复制代码

  
  乃至我们可以用隐式范例转换，直接传指针就好啦
     迭代器自己就是节点的指针，指针节点指针自己不满足迭代器的那些需求，以是我们才用一个类把他封装一层，用重载运算符使其到达迭代器的要求。
    

1. iterator begin()
2. {
3.         return _pHead->_next;
4. }

复制代码

  end()是末了一个数据的下一个位置，就是哨兵位的头结点

1. iterator end()
2. {
3.         return _pHead;
4. }

复制代码

  
  
3.4 operator-> 的实现

  既然迭代器模仿的是指针的举动，那它还要实现 operator->
  什么情况下用到 -> 运算符呢？
  如今我们界说一个范例 AA，链表中存储的数据是 AA 范例，我们想依次遍历链表，打印每个节点 AA 中的两个成员变量

1. struct AA
2. {
3.         int _a1 = 1;
4.         int _a2 = 2;
5. }
7. void test1()
8. {
9.         list<AA> lta;
10.         lta.push_back(AA());
11.         lta.push_back(AA());
12.         lta.push_back(AA());
14.         list<AA>::iterator it = lta.begin();
15.         while (it != lta.end())
16.         {
17.                 cout << (*it)._a1 << " " << (*it)._a2 << endl;
18.                 cout << it->_a1 << " " << it->_a2 << endl;
19.         }
20. }

复制代码

  上述(*it)._a1与it->_a1的写法是等价的，但如今还没重载->运算符
  下面是operator->的实现方式

1. T* operator->()
2. {
3.         return &(pNode->_val);
4. }

复制代码

  operator->的实现方式非常奇怪，返回的是T*
  
  着实这里省略了一个 ->，由于太丢脸了，为了可读性省略了一个 ->

1. cout << it->_a1 << " " << it->_a2 << endl;
3. //本质是这样的
4. cout << it->->_a1 << " " << it->->_a2 << endl;

复制代码

  
  第一个->是运算符重载出来的，第二个则是平凡的->
  本质是如许的:

1. cout << it.operator->()->_a1 << " " << it.operator->()->_a2 << endl;
3. cout << &(pNode->_val)->_a1 << " " << &(pNode->_val)->_a2 << endl;

复制代码

  
  
3.5 const 迭代器

3.5.1 const 迭代器为什么定名 const_iterator

  起首问各人一个标题：                              c                      o                      n                      s                      t                          const               const 迭代器为什么是const_iterator，而不是const iterator呢
                                c                      o                      n                      s                      t                          const               const 迭代器是自身不能修改还是指向的内容不能修改呢？
  就和指针一样，指针的                               c                      o                      n                      s                      t                          const               const 有两个，一个在 * 之前，一个在 * 之后

1. T* const ptr1//指针本身不能修改
2. const T* ptr2//指向的内容不能修改

复制代码

  
  如果是 const iterator ，const 直接修饰一个变量，就是这个变量自己不能修改，即迭代器自己不能修改，而我们                               c                      o                      n                      s                      t                          const               const 迭代器是要指向的内容不能修改，以是const_iterator更符合
  
  
3.5.2 const 迭代器的实现

  那我们怎样让迭代器指向的内容不能修改呢？
  迭代器修改我们指向的内容是怎么修改的？通过operator* 和operator->，那我们在其返回值上加上                                    c                         o                         n                         s                         t                              const                  const 就不能修改了

1. const T& operator*(){        return pNode->_val;}const T* operator->()
2. {
3.         return &(pNode->_val);
4. }

复制代码

  那我们就再自己实现一个                               c                      o                      n                      s                      t                          const               const 迭代器的封装吧

1. template<class T>
2. struct const_ListIterator
3. {
4.         typedef const_ListIterator<T> Self;
5.         typedef ListNode<T> Node;
7.         Node* pNode;
9.         const_ListIterator(Node* p = nullptr)
10.                 :pNode(p)
11.         {}
12.        
13.         const T& operator*()
14.         {
15.                 return pNode->_val;
16.         }
18.         const T* operator->()
19.         {
20.                 return &(pNode->_val);
21.         }
23.         Self& operator++()
24.         {
25.                 pNode = pNode->_next;
26.                 return *this;
27.         }
29.         Self& operator++(int)
30.         {
31.                 Self tmp = *this;
32.                 pNode = pNode->_next;
33.                 return tmp;
34.         }
36.         Self& operator--()
37.         {
38.                 pNode = pNode->_prev;
39.                 return *this;
40.         }
42.         Self& operator--(int)
43.         {
44.                 Self tmp = *this;
45.                 pNode = pNode->_prev;
46.                 return tmp;
47.         }
49.         bool operator!=(const Self& x)
50.         {
51.                 return pNode != x.pNode;
52.         }
54.         bool operator==(const Self& x)
55.         {
56.                 return pNode == x.pNode;
57.         }
58. };

复制代码

  
3.5.3 归并两个迭代器

  上面我们再重新封装了一个const_iterator，根本满足了需求，但是代码太冗余了，除了operator* 和operator-> 的返回值范例不一样，其他代码满是一样的，有什么办法将他们合二为一呢？
  我们来看一下库中是怎么实现的
   

    库中的__list_iterator类，用了三个模板参数，新增了 Ref 与 Ptr 两个参数。
  在                               l                      i                      s                      t                          list               list 类中，将__list_iterator<T, T&, T*>                              t                      y                      p                      e                      d                      e                      f                          typedef               typedef 成                                    i                         t                         e                         r                         a                         t                         o                         r                              iterator                  iterator，将__list_iterator<T, const T&, const T*>                               t                      y                      p                      e                      d                      e                      f                          typedef               typedef 成                                    c                         o                         n                         s                         t                              const                  const_                                   i                         t                         e                         r                         a                         t                         o                         r                              iterator                  iterator。
  也就是说                                    i                         t                         e                         r                         a                         t                         o                         r                              iterator                  iterator 的                                    R                         e                         f                              Ref                  Ref 参数即 T&，                                   P                         t                         r                              Ptr                  Ptr 即参数 T*，                                   c                         o                         n                         s                         t                              const                  const_                                   i                         t                         e                         r                         a                         t                         o                         r                              iterator                  iterator 的                                    R                         e                         f                              Ref                  Ref参数即                                    c                         o                         n                         s                         t                              const                  const T&，                                   P                         t                         r                              Ptr                  Ptr 参数即                                   c                         o                         n                         s                         t                              const                  const T*
以operator* 举例：
  T& 传给Ref，Ref 即reference，operator*的返回值是reference，更换过来operator*的返回值就是 T&
对                                    c                         o                         n                         s                         t                              const                  const_                                   i                         t                         e                         r                         a                         t                         o                         r                              iterator                  iterator
                                     c                         o                         n                         s                         t                              const                  const T& 传给                                    R                         e                         f                              Ref                  Ref，更换过来operator*的返回值就是                                    c                         o                         n                         s                         t                              const                  const T&
  着实，这种写法与上面我们自己实现两个类模板并没有本质区别，他们实例化出来都是两个差异的类。差异的是第一种写法是我们自己写了两个差异的类，而第二种是我们通过控制模板参数让编译器实例化出两个差异的类，把我们干的活交给了编译器
  
代码如下：

1. template<class T, class Ref, class Ptr>
2. struct ListIterator
3. {
4.         typedef ListIterator<T, Ref, Ptr> Self;
5.         typedef ListNode<T> Node;
7.         Node* pNode;
9.         ListIterator(Node* p = nullptr)
10.                 :pNode(p)
11.         {}
12.        
13.         Ref operator*()
14.         {
15.                 return pNode->_val;
16.         }
18.         Ptr operator->()
19.         {
20.                 return &(pNode->_val);
21.         }
23.         Self& operator++()
24.         {
25.                 pNode = pNode->_next;
26.                 return *this;
27.         }
29.         Self& operator++(int)
30.         {
31.                 Self tmp = *this;
32.                 pNode = pNode->_next;
33.                 return tmp;
34.         }
36.         Self& operator--()
37.         {
38.                 pNode = pNode->_prev;
39.                 return *this;
40.         }
42.         Self& operator--(int)
43.         {
44.                 Self tmp = *this;
45.                 pNode = pNode->_prev;
46.                 return tmp;
47.         }
49.         bool operator!=(const Self& x)
50.         {
51.                 return pNode != x.pNode;
52.         }
54.         bool operator==(const Self& x)
55.         {
56.                 return pNode == x.pNode;
57.         }
58. };

复制代码

  
  
4 源码

对于                               l                      i                      s                      t                          list               list 的其他成员函数，与前面的                               s                      t                      r                      i                      n                      g                          string               string、                              v                      e                      c                      t                      o                      r                          vector               vector 实现起来都大同小异，这里就不再赘述了，我们直接看源码

1. #pragma once
2. #include<iostream>
3. #include<assert.h>
5. using namespace std;
7. namespace my_list
8. {
9.         template<class T>
10.         struct ListNode
11.         {
12.                 ListNode* _prev;
13.                 ListNode* _next;
14.                 T _val;
16.                 ListNode(const T& val = T())
17.                         :_prev(nullptr)
18.                         ,_next(nullptr)
19.                         ,_val(val)
20.                 {}
22.         };
24.         template<class T, class Ref, class Ptr>
25.         struct ListIterator
26.         {
27.                 typedef ListIterator<T, Ref, Ptr> Self;
28.                 typedef ListNode<T> Node;
30.                 Node* pNode;
32.                 ListIterator(Node* p = nullptr)
33.                         :pNode(p)
34.                 {}
35.                
37.                 Ref operator*()
38.                 {
39.                         return pNode->_val;
40.                 }
42.                 Ptr operator->()
43.                 {
44.                         return &(pNode->_val);
45.                 }
47.                 Self& operator++()
48.                 {
49.                         pNode = pNode->_next;
50.                         return *this;
51.                 }
53.                 Self& operator++(int)
54.                 {
55.                         Self tmp = *this;
56.                         pNode = pNode->_next;
57.                         return tmp;
58.                 }
60.                 Self& operator--()
61.                 {
62.                         pNode = pNode->_prev;
63.                         return *this;
64.                 }
66.                 Self& operator--(int)
67.                 {
68.                         Self tmp = *this;
69.                         pNode = pNode->_prev;
70.                         return tmp;
71.                 }
73.                 bool operator!=(const Self& x)
74.                 {
75.                         return pNode != x.pNode;
76.                 }
78.                 bool operator==(const Self& x)
79.                 {
80.                         return pNode == x.pNode;
81.                 }
82.         };
84.         template<class T>
85.         class list
86.         {
87.                 typedef ListNode<T> Node;
88.         public:
89.                 typedef ListIterator<T, T&, T*> iterator;
90.                 typedef ListIterator<T, const T&, const T*> const_iterator;
92.                 list()
93.                         :_pHead(nullptr)
94.                         , _size(0)
95.                 {
96.                         CreateHead();
97.                 }
99.                 list(int n, const T& value = T())
100.                 {
101.                         CreateHead();
103.                         while (n--)
104.                         {
105.                                 push_back(value);
106.                         }
107.                 }
109.                 template <class Iterator>
110.                 list(Iterator first, Iterator last)
111.                 {
112.                         CreateHead();
113.                         Iterator it = first;
114.                         while (it != last)
115.                         {
116.                                 push_back(*it);
117.                                 ++it;
118.                         }
119.                 }
121.                 list(const list<T>& l)
122.                 {
123.                         CreateHead();
124.                         const_iterator it = l.begin();
125.                         while (it != l.end())
126.                         {
127.                                 push_back(*it);
128.                                 ++it;
129.                         }
130.                 }
131.                 list<T>& operator=(list<T> l)
132.                 {
133.                         swap(l);
134.                         return *this;
135.                 }
136.                 ~list()
137.                 {
138.                         clear();
139.                         delete _pHead;
140.                         _pHead = nullptr;
141.                 }
143.                 iterator begin()
144.                 {
145.                         return _pHead->_next;
146.                 }
147.                 iterator end()
148.                 {
149.                         return _pHead;
150.                 }
151.                 const_iterator begin() const
152.                 {
153.                         return _pHead->_next;
154.                 }
155.                 const_iterator end() const
156.                 {
157.                         return _pHead;
158.                 }
160.                 size_t size()const
161.                 {
162.                         return _size;
163.                 }
164.                 bool empty()const
165.                 {
166.                         return _size == 0;
167.                 }
169.                 T& front()                                                                                                
170.                 {
171.                         return _pHead->_next->_val;
172.                 }
174.                 T& back()
175.                 {
176.                         return _pHead->_prev->_val;
177.                 }
179.                 const T& front() const
180.                 {
181.                         return _pHead->_next->_val;
182.                 }
184.                 const T& back() const
185.                 {
186.                         return _pHead->_prev->_val;
187.                 }
189.                 void push_back(const T& val)
190.                 {
191.                         Node* p = new Node(val);
193.                         p->_next = _pHead;
194.                         _pHead->_prev->_next = p;
195.                         p->_prev = _pHead->_prev;
196.                         _pHead->_prev = p;
197.                         ++_size;
198.                 }
199.                 void pop_back()
200.                 {
201.                         Node* p = _pHead->_prev;
203.                         p->_prev->_next = _pHead;
204.                         _pHead->_prev = p->_prev;
205.                         delete p;
206.                         --_size;
207.                 }
208.                 void push_front(const T& val)
209.                 {
210.                         Node* p = new Node(val);
212.                         p->_next = _pHead->_next;
213.                         p->_prev = _pHead;
214.                         _pHead->_next = p;
215.                         p->_next->_prev = p;
216.                         ++_size;
217.                 }
218.                 void pop_front()
219.                 {
220.                         Node* p = _pHead->_next;
222.                         _pHead->_next = p->_next;
223.                         p->_next->_prev = _pHead;
224.                         delete p;
225.                         --_size;
226.                 }
228.                 iterator insert(iterator pos, const T& val)
229.                 {
230.                         Node* p = new Node(val);
232.                         p->_next = pos.pNode;
233.                         p->_prev = pos.pNode->_prev;
234.                         pos.pNode->_prev->_next = p;
235.                         pos.pNode->_prev = p;
237.                         ++_size;
239.                         return pos;
240.                 }
242.                 iterator erase(iterator pos)
243.                 {
244.                         assert(pos != end());
246.                         iterator ret = pos.pNode->_next;
247.                        
248.                         pos.pNode->_prev->_next = pos.pNode->_next;
249.                         pos.pNode->_next->_prev = pos.pNode->_prev;
250.                         delete pos.pNode;
252.                         --_size;
254.                         return ret;
255.                
256.                 }
258.                 void clear()
259.                 {
260.                         iterator it = begin();
262.                         while (it != end())
263.                         {
264.                                 iterator cur = it++;
265.                                 delete cur.pNode;
266.                         }
267.                         _pHead->_next = _pHead;
268.                         _pHead->_prev = _pHead;
270.                         _size = 0;
271.                 }
273.                 void swap(list<T>& l)
274.                 {
275.                         std::swap(_pHead, l._pHead);
276.                         std::swap(_size, l._size);
277.                 }
279.         private:
280.                 Node* _pHead;
281.                 size_t _size;
283.                 void CreateHead()
284.                 {
285.                         _pHead = new Node;
286.                         _pHead->_next = _pHead;
287.                         _pHead->_prev = _pHead;
288.                         _size = 0;
289.                 }
290.         };
291. }
293. template<class Container>
294. void print_container(const Container& v)
295. {
296.         auto it = v.begin();
297.         while (it != v.end())
298.         {
299.                 cout << *it << " ";
300.                 ++it;
301.         }
302.         cout << endl;
303. }

复制代码

  
  
  
  
  

---

  好啦，本期关于                                         l                            i                            s                            t                                  list                     list 的知识就先容到这里啦，渴望本期博客能对你有所资助。同时，如果有错误的地方请多多指正，让我们在 C++ 的学习路上一起进步！