第二十六课 典型问题分析(Bugfix)

问题1:

第二十六课   典型问题分析(Bugfix)

glibc中的strdup实现如下:

第二十六课   典型问题分析(Bugfix)

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

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

第二十六课   典型问题分析(Bugfix)

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

问题2:

第二十六课   典型问题分析(Bugfix)

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

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

示例程序:

 #include <iostream>
#include "LinkList.h" using namespace std;
using namespace DTLib; class Test : public Object
{
int m_id;
public:
Test(int id = )
{
m_id = id;
} ~Test()
{
if( m_id == )
{
throw m_id;
}
}
}; int main()
{
LinkList<Test> list;
Test t0(), t1(), t2(); try
{
list.insert(t0);
list.insert(t1);
list.insert(t2); list.remove();
}
catch(int e)
{
cout << e << endl;
cout << list.length() << endl;
} return ;
}

结果如下:

第二十六课   典型问题分析(Bugfix)

程序直接崩溃了。

vc下的运行结果如下:

第二十六课   典型问题分析(Bugfix)

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

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

修改LinkList.h:

 #ifndef LINKLIST_H
#define LINKLIST_H #include "List.h"
#include "Exception.h" namespace DTLib
{ template < typename T >
class LinkList : public List<T>
{
protected:
struct Node : public Object
{
T value;
Node* next;
}; mutable struct : public Object
{
char reserved[sizeof(T)];
Node* next;
}m_header; int m_length;
int m_step;
Node* m_current; Node* position(int i) const // O(n)
{
Node* ret = reinterpret_cast<Node*>(&m_header); for(int p = ; p < i; p++)
{
ret = ret->next;
} return ret;
} virtual Node* create()
{
return new Node();
} virtual void destroy(Node* pn)
{
delete pn;
} public:
LinkList()
{
m_header.next = NULL;
m_length = ;
m_step = ;
m_current = NULL;
} bool insert(const T& e)
{
return insert(m_length, e);
} bool insert(int i, const T& e) // O(n)
{
bool ret = (( <= i) && (i <= m_length)); if( ret )
{
Node* node = create(); if( node != NULL )
{
Node* current = position(i); node->value = e;
node->next = current->next;
current->next = node; m_length++;
}
else
{
THROW_EXCEPTION(NoEnoughMemoryException, "No memery to insert new element...");
}
} return ret;
} bool remove(int i) // O(n)
{
bool ret = (( <= i) && (i < m_length)); if( ret )
{
Node* current = position(i); Node* toDel = current->next; current->next = toDel->next; m_length--; destroy(toDel); } return ret;
} bool set(int i, const T& e) // O(n)
{
bool ret = (( <= i) && (i < m_length)); if( ret )
{
position(i)->next->value = e;
} return ret;
} T get(int i) const
{
T ret; if( get(i, ret) )
{
return ret;
}
else
{
THROW_EXCEPTION(IndexOutOfBoundsException, "Invalid parameter i to get element ...");
} return ret;
} bool get(int i, T& e) const // O(n)
{
bool ret = (( <= i) && (i < m_length)); if( ret )
{
e = position(i)->next->value;
} return ret;
} int find(const T& e) const // O(n)
{
int ret = -;
int i = ; Node* node = m_header.next; while( node )
{
if( node->value == e )
{
ret = i;
break;
}
else
{
node = node->next;
i++;
}
} return ret;
} int length() const // O(1)
{
return m_length;
} void clear() // O(n)
{
while( m_header.next )
{
Node* toDel = m_header.next; m_header.next = toDel->next; m_length--; destroy(toDel);
} // m_length = 0;
} bool move(int i, int step = )
{
bool ret = ( <= i) && (i < m_length) && (step > ); if( ret )
{
m_current = position(i)->next;
m_step = step;
} return ret;
} bool end()
{
return (m_current == NULL);
} T current()
{
if( !end() )
{
return m_current->value;
}
else
{
THROW_EXCEPTION(InvalidOperationException, "No value at current position ...");
}
} bool next() //每次移动step步
{
int i = ; while((i < m_step) && !end())
{
m_current = m_current->next;
i++;
} return (i == m_step);
} ~LinkList() // O(n)
{
clear();
}
}; } #endif // LINKLIST_H

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

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

问题3:

第二十六课   典型问题分析(Bugfix)

测试程序如下:

第二十六课   典型问题分析(Bugfix)

结果如下:

第二十六课   典型问题分析(Bugfix)

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

图解:

第二十六课   典型问题分析(Bugfix)

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

修改LinkList.h中的remove函数:

 bool remove(int i)   // O(n)
{
bool ret = (( <= i) && (i < m_length)); if( ret )
{
Node* current = position(i); Node* toDel = current->next; if( m_current == toDel )
{
m_current = toDel->next;
} current->next = toDel->next; m_length--; destroy(toDel); } return ret;
}

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

运行结果如下:

第二十六课   典型问题分析(Bugfix)

问题4:

第二十六课   典型问题分析(Bugfix)

程序改进:

 void destroy(Node* pn)
{
SNode* space = reinterpret_cast<SNode*>(m_space);
SNode* psn = dynamic_cast<SNode*>(pn); for(int i = ; i<N; i++)
{
if( psn == (space + i))
{
m_used[i] = ;
psn->~SNode();
break;
}
}
}

添加了第12行的break。

问题5:

第二十六课   典型问题分析(Bugfix)

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

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

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

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

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

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

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

子类中的版本是:

第二十六课   典型问题分析(Bugfix)

父类中提供的版本是:

第二十六课   典型问题分析(Bugfix)

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

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

改进程序,添加子类的析构函数:

 #ifndef STATICLINKLIST_H
#define STATICLINKLIST_H #include "LinkList.h" namespace DTLib
{ template< typename T, int N >
class StaticLinkList : public LinkList<T>
{
protected:
// Node和泛指类型T有关系,因此,不能直接在子类中使用sizeof(Node),而应该
// sizeof(LinkList<T>::Node)
// unsigned char m_space[sizeof(typename LinkList<T>::Node) * N]; // 预留空间
typedef typename LinkList<T>::Node Node; struct SNode : public Node
{
void* operator new(unsigned int size, void* loc)
{
(void)size; // 消除 size没有使用的警告
return loc;
}
}; unsigned char m_space[sizeof(SNode) * N]; // 预留空间
int m_used[N]; //预留空间的标记数组 Node* create()
{
SNode* ret = NULL; for(int i = ; i < N; i++)
{
if( !m_used[i] )
{
ret = reinterpret_cast<SNode*>(m_space) + i;
ret = new(ret)SNode(); //在指定空间ret上调用SNode类的构造函数。
m_used[i] = ;
break;
}
} return ret;
} void destroy(Node* pn)
{
SNode* space = reinterpret_cast<SNode*>(m_space);
SNode* psn = dynamic_cast<SNode*>(pn); for(int i = ; i<N; i++)
{
if( psn == (space + i))
{
m_used[i] = ;
psn->~SNode();
break;
}
}
} public:
StaticLinkList()
{
for(int i = ; i < N; i++)
{
m_used[i] = ;
}
} int capacity()
{
return N;
} ~StaticLinkList()
{
this->clear();
}
}; } #endif // STATICLINKLIST_H

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

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

第二十六课   典型问题分析(Bugfix)

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

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

 #include <iostream>
#include "StaticLinkList.h" using namespace std;
using namespace DTLib; int main()
{
StaticLinkList<int, > list; list.insert(); cout << list.get() << endl; return ;
}

结果如下:

第二十六课   典型问题分析(Bugfix)

问题6:

第二十六课   典型问题分析(Bugfix)

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

示例程序:

 #include <iostream>
#include "StaticLinkList.h"
#include "DynamicArray.h" using namespace std;
using namespace DTLib; int main()
{
StaticLinkList<int, > list; DynamicArray< DynamicArray<int> > d; d.resize(); for(int i=; i < d.length(); i++)
{
d[i].resize();
} for(int i=; i<d.length(); i++)
{
for(int j=; j<d[i].length(); j++)
{
d[i][j] = i * j;
}
} for(int i=; i<d.length(); i++)
{
for(int j=; j<d[i].length(); j++)
{
cout << d[i][j] << " ";
} cout << endl;
} return ;
}

结果如下:

第二十六课   典型问题分析(Bugfix)

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

 #include <iostream>
#include "StaticLinkList.h"
#include "DynamicArray.h" using namespace std;
using namespace DTLib; int main()
{
StaticLinkList<int, > list; DynamicArray< DynamicArray<int> > d; d.resize(); for(int i=; i < d.length(); i++)
{
d[i].resize(i + );
} for(int i=; i<d.length(); i++)
{
for(int j=; j<d[i].length(); j++)
{
d[i][j] = i + j;
}
} for(int i=; i<d.length(); i++)
{
for(int j=; j<d[i].length(); j++)
{
cout << d[i][j] << " ";
} cout << endl;
} return ;
}

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

第二十六课   典型问题分析(Bugfix)

实践经验:

第二十六课   典型问题分析(Bugfix)

上一篇:python基础 : 1.计算机基础 2.注释 3.变量 4.标识符 5.输出 6.格式化输出 7.输入 8.算数运算符 9.字符串操作


下一篇:使用shiro框架,解决跳转页面出现404的问题