第二十六课典型问题分析（Bugfix）

问题1：

glibc中的strdup实现如下：

没有对参数s进行空指针判断。

我们的Exception.cpp中应做改进：

在第12行进行判断空指针操作。

问题2：

t1在析构时会抛出异常，我们在remove一个对象时，要保证链表还是合法的，也就是保证异常安全性。

如上图，我们期望打印的链表长度为2。

示例程序：

 1 #include <iostream>
 2 #include "LinkList.h"
 3 
 4 using namespace std;
 5 using namespace DTLib;
 6 
 7 class Test : public Object
 8 {
 9     int m_id;
10 public:
11     Test(int id = 0)
12     {
13         m_id = id;
14     }
15 
16     ~Test()
17     {
18         if( m_id == 1 )
19         {
20             throw m_id;
21         }
22     }
23 };
24 
25 int main()
26 {
27     LinkList<Test> list;
28     Test t0(0), t1(1), t2(2);
29 
30     try
31     {
32         list.insert(t0);
33         list.insert(t1);
34         list.insert(t2);
35 
36         list.remove(1);
37     }
38     catch(int e)
39     {
40         cout << e << endl;
41         cout << list.length() << endl;
42     }
43 
44     return 0;
45 }

结果如下：

程序直接崩溃了。

vc下的运行结果如下：

打印e的值为1，链表长度为3，意味着单链表的状态出问题了。

我们的remove函数没有考虑异常安全性。

修改LinkList.h：

  1 #ifndef LINKLIST_H
  2 #define LINKLIST_H
  3 
  4 #include "List.h"
  5 #include "Exception.h"
  6 
  7 namespace DTLib
  8 {
  9 
 10 template < typename T >
 11 class LinkList : public List<T>
 12 {
 13 protected:
 14     struct Node : public Object
 15     {
 16         T value;
 17         Node* next;
 18     };
 19 
 20     mutable struct : public Object
 21     {
 22         char reserved[sizeof(T)];
 23         Node* next;
 24     }m_header;
 25 
 26     int m_length;
 27     int m_step;
 28     Node* m_current;
 29 
 30     Node* position(int i) const    //  O(n)
 31     {
 32         Node* ret = reinterpret_cast<Node*>(&m_header);
 33 
 34         for(int p = 0; p < i; p++)
 35         {
 36             ret = ret->next;
 37         }
 38 
 39         return ret;
 40     }
 41 
 42     virtual Node* create()
 43     {
 44         return new Node();
 45     }
 46 
 47     virtual void destroy(Node* pn)
 48     {
 49         delete pn;
 50     }
 51 
 52 public:
 53     LinkList()
 54     {
 55         m_header.next = NULL;
 56         m_length = 0;
 57         m_step = 1;
 58         m_current = NULL;
 59     }
 60 
 61     bool insert(const T& e)
 62     {
 63         return insert(m_length, e);
 64     }
 65 
 66     bool insert(int i, const T& e)   // O(n)
 67     {
 68         bool ret = ((0 <= i) && (i <= m_length));
 69 
 70         if( ret )
 71         {
 72             Node* node = create();
 73 
 74             if( node != NULL )
 75             {
 76                 Node* current = position(i);
 77 
 78                 node->value = e;
 79                 node->next = current->next;
 80                 current->next = node;
 81 
 82                 m_length++;
 83             }
 84             else
 85             {
 86                 THROW_EXCEPTION(NoEnoughMemoryException, "No memery to insert new element...");
 87             }
 88         }
 89 
 90         return ret;
 91     }
 92 
 93     bool remove(int i)   // O(n)
 94     {
 95         bool ret = ((0 <= i) && (i < m_length));
 96 
 97         if( ret )
 98         {
 99             Node* current = position(i);
100 
101             Node* toDel = current->next;
102 
103             current->next = toDel->next;
104 
105             m_length--;
106 
107             destroy(toDel);
108 
109         }
110 
111         return ret;
112     }
113 
114     bool set(int i, const T& e)   //  O(n)
115     {
116         bool ret = ((0 <= i) && (i < m_length));
117 
118         if( ret )
119         {
120             position(i)->next->value = e;
121         }
122 
123         return ret;
124     }
125 
126     T get(int i) const
127     {
128         T ret;
129 
130         if( get(i, ret) )
131         {
132             return ret;
133         }
134         else
135         {
136             THROW_EXCEPTION(IndexOutOfBoundsException, "Invalid parameter i to get element ...");
137         }
138 
139         return ret;
140     }
141 
142     bool get(int i, T& e) const    // O(n)
143     {
144         bool ret = ((0 <= i) && (i < m_length));
145 
146         if( ret )
147         {
148             e = position(i)->next->value;
149         }
150 
151         return ret;
152     }
153 
154     int find(const T& e) const    //  O(n)
155     {
156         int ret = -1;
157         int i = 0;
158 
159         Node* node = m_header.next;
160 
161         while( node )
162         {
163             if( node->value == e )
164             {
165                 ret = i;
166                 break;
167             }
168             else
169             {
170                 node = node->next;
171                 i++;
172             }
173         }
174 
175         return ret;
176     }
177 
178     int length() const   // O(1)
179     {
180         return m_length;
181     }
182 
183     void clear()    //  O(n)
184     {
185         while( m_header.next )
186         {
187             Node* toDel = m_header.next;
188 
189             m_header.next = toDel->next;
190 
191             m_length--;
192 
193             destroy(toDel);
194         }
195 
196         // m_length = 0;
197     }
198 
199     bool move(int i, int step = 1)
200     {
201         bool ret = (0 <= i) && (i < m_length) && (step > 0);
202 
203         if( ret )
204         {
205             m_current = position(i)->next;
206             m_step = step;
207         }
208 
209         return ret;
210     }
211 
212     bool end()
213     {
214         return (m_current == NULL);
215     }
216 
217     T current()
218     {
219         if( !end() )
220         {
221             return m_current->value;
222         }
223         else
224         {
225             THROW_EXCEPTION(InvalidOperationException, "No value at current position ...");
226         }
227     }
228 
229     bool next()   //每次移动step步
230     {
231         int i = 0;
232 
233         while((i < m_step) && !end())
234         {
235             m_current = m_current->next;
236             i++;
237         }
238 
239         return (i == m_step);
240     }
241 
242     ~LinkList()   //  O(n)
243     {
244         clear();
245     }
246 };
247 
248 }
249 
250 #endif // LINKLIST_H

在remove函数中，先让m_length--，再做摧毁节点的操作。

在clear函数中，注释掉原来的196行，添加第191行，每次摧毁前让m_length--。

问题3：

测试程序如下：

结果如下：

删除之后，游标m_current指向这个释放之后的内存，current函数返回的是这个释放了的内存中保存的value。

图解：

删除之后current函数返回的这块被释放了的堆内存中的value的值，所以会打印出随机值。

修改LinkList.h中的remove函数：

 1 bool remove(int i)   // O(n)
 2     {
 3         bool ret = ((0 <= i) && (i < m_length));
 4 
 5         if( ret )
 6         {
 7             Node* current = position(i);
 8 
 9             Node* toDel = current->next;
10 
11             if( m_current == toDel )
12             {
13                 m_current = toDel->next;
14             }
15 
16             current->next = toDel->next;
17 
18             m_length--;
19 
20             destroy(toDel);
21 
22         }
23 
24         return ret;
25     }

我们添加了第11-14行，在删除时，先进行判断，如果m_current和toDel指向的是同一个节点，那么先将m_current指向toDel的下一个节点，然后再删除。

运行结果如下：

问题4：

程序改进：

 1 void destroy(Node* pn)
 2     {
 3         SNode* space = reinterpret_cast<SNode*>(m_space);
 4         SNode* psn = dynamic_cast<SNode*>(pn);
 5 
 6         for(int i = 0; i<N; i++)
 7         {
 8             if( psn == (space + i))
 9             {
10                 m_used[i] = 0;
11                 psn->~SNode();
12                 break;
13             }
14         }
15     }

添加了第12行的break。

问题5：

StaticLinkList的构造函数中没有申请系统资源，从资源方面来看不用提供析构函数。

不提供析构函数的第二个条件是，该类为一个独立的类，没有任何继承关系，但是我们StaticLinkList不满足。

StaticLinkList继承自LinkList，LinkList中有析构函数，且这个析构函数调用了一个虚函数，但是多态是不会发生的。

构造函数和析构函数中不会发生多态。

StaticLinkList类中没有clear函数，因此，默认的析构函数会调用到LinkList的析构函数，进一步调用到clear函数，这个clear函数在子类和在父类中调用是一样的。

如果子类StaticLinkList中也有一个clear函数版本，那就要提供析构函数了。因为这两个含本的析构函数都要调用到。

但是我们再仔细观察可以发现，在clear函数中还调用了destroy函数，而这个函数在子类和父类中各有一个版本。

子类中的版本是：

父类中提供的版本是：

这意味着父类中的析构函数被调用的时候，调用到的destroy一直是父类中的destroy。子类中的destroy无法被调用到，因为析构函数中不能发生多态。

析构时父类中的destroy直接delete掉申请的空间，而这个空间是在我们的预留区域中申请的，不是堆空间，因此，可能会出现bug，造成程序的不稳定，因为delete关键字只能释放堆空间。

改进程序，添加子类的析构函数：

 1 #ifndef STATICLINKLIST_H
 2 #define STATICLINKLIST_H
 3 
 4 #include "LinkList.h"
 5 
 6 namespace DTLib
 7 {
 8 
 9 template< typename T, int N >
10 class StaticLinkList : public LinkList<T>
11 {
12 protected:
13     // Node和泛指类型T有关系，因此，不能直接在子类中使用sizeof(Node),而应该
14     // sizeof(LinkList<T>::Node)
15     // unsigned char m_space[sizeof(typename LinkList<T>::Node) * N];  // 预留空间
16     typedef typename LinkList<T>::Node Node;
17 
18     struct SNode : public Node
19     {
20         void* operator new(unsigned int size, void* loc)
21         {
22             (void)size; // 消除 size没有使用的警告
23             return loc;
24         }
25     };
26 
27     unsigned char m_space[sizeof(SNode) * N];  // 预留空间
28     int m_used[N];   //预留空间的标记数组
29 
30     Node* create()
31     {
32         SNode* ret = NULL;
33 
34         for(int i = 0; i < N; i++)
35         {
36             if( !m_used[i] )
37             {
38                 ret = reinterpret_cast<SNode*>(m_space) + i;
39                 ret = new(ret)SNode(); //在指定空间ret上调用SNode类的构造函数。
40                 m_used[i] = 1;
41                 break;
42             }
43         }
44 
45         return ret;
46     }
47 
48     void destroy(Node* pn)
49     {
50         SNode* space = reinterpret_cast<SNode*>(m_space);
51         SNode* psn = dynamic_cast<SNode*>(pn);
52 
53         for(int i = 0; i<N; i++)
54         {
55             if( psn == (space + i))
56             {
57                 m_used[i] = 0;
58                 psn->~SNode();
59                 break;
60             }
61         }
62     }
63 
64 public:
65     StaticLinkList()
66     {
67         for(int i = 0; i < N; i++)
68         {
69             m_used[i] = 0;
70         }
71     }
72 
73     int capacity()
74     {
75         return N;
76     }
77 
78     ~StaticLinkList()
79     {
80         this->clear();
81     }
82 };
83 
84 }
85 
86 #endif // STATICLINKLIST_H

添加了第78-81行的析构函数，这时的clear是从父类继承来的，但是clear中的destroy函数就是子类自己实现的了。

这样的话析构时，先调用子类的析构函数，然后是子类继承过来的clear函数，然后子类的destroy函数。子类的析构函数执行完时，再调用父类的析构函数，然后父类的clear函数，最后调用父类的destroy函数。但是单步执行时，我们发现并没有调用到父类的destroy函数，这里可能令人迷惑，其实是因为调用父类的析构函数时，clear函数中的while循环已经不成立的，也就不会再调用父类的destroy函数了。单步执行时要注意这一点，调用不到父类的destroy是因为条件不成立，而不是其他的机制导致的。如下：

从子类的析构函数执行完，到调用到父类的析构函数时，clear函数中的190行的条件已经不成立了。

我们在子类的析构函数和destroy函数，父类的析构函数和destroy函数加上打印，测试程序如下：

 1 #include <iostream>
 2 #include "StaticLinkList.h"
 3 
 4 using namespace std;
 5 using namespace DTLib;
 6 
 7 
 8 int main()
 9 {
10     StaticLinkList<int, 10> list;
11 
12     list.insert(0);
13 
14     cout << list.get(0) << endl;
15 
16     return 0;
17 }

结果如下：

问题6：

没有必要定义多维数组的类，由一位数组就可以构成。

示例程序：

 1 #include <iostream>
 2 #include "StaticLinkList.h"
 3 #include "DynamicArray.h"
 4 
 5 using namespace std;
 6 using namespace DTLib;
 7 
 8 
 9 int main()
10 {
11     StaticLinkList<int, 10> list;
12 
13     DynamicArray< DynamicArray<int> > d;
14 
15     d.resize(3);
16 
17     for(int i=0; i < d.length(); i++)
18     {
19         d[i].resize(3);
20     }
21 
22     for(int i=0; i<d.length(); i++)
23     {
24         for(int j=0; j<d[i].length(); j++)
25         {
26             d[i][j] = i * j;
27         }
28     }
29 
30     for(int i=0; i<d.length(); i++)
31     {
32         for(int j=0; j<d[i].length(); j++)
33         {
34             cout << d[i][j] << " ";
35         }
36 
37         cout << endl;
38     }
39 
40     return 0;
41 }

结果如下：

还可以构造不规则的数组：

 1 #include <iostream>
 2 #include "StaticLinkList.h"
 3 #include "DynamicArray.h"
 4 
 5 using namespace std;
 6 using namespace DTLib;
 7 
 8 
 9 int main()
10 {
11     StaticLinkList<int, 10> list;
12 
13     DynamicArray< DynamicArray<int> > d;
14 
15     d.resize(3);
16 
17     for(int i=0; i < d.length(); i++)
18     {
19         d[i].resize(i + 1);
20     }
21 
22     for(int i=0; i<d.length(); i++)
23     {
24         for(int j=0; j<d[i].length(); j++)
25         {
26             d[i][j] = i + j;
27         }
28     }
29 
30     for(int i=0; i<d.length(); i++)
31     {
32         for(int j=0; j<d[i].length(); j++)
33         {
34             cout << d[i][j] << " ";
35         }
36 
37         cout << endl;
38     }
39 
40     return 0;
41 }

第19行使得每个数组元素大小不一样，运行结果如下：

实践经验：

第二十六课 典型问题分析（Bugfix）

第二十六课典型问题分析（Bugfix）