clone模式在平衡排序二叉树实现中的应用
clone模式在平衡排序二叉树实现中的应用
作者：wujinglong
clone模式既prototype模式,是构造模式中的一种。其意图为:用原型实例指定创建对象的种类,并且通过拷贝这些原型创建新的对象。
关键代码如下:
virtual product * prototype::clone(){
return new prototype(this-datas);
}
virtual product * concreteprototype_1::clone(){
//return copy of self
return new concreteprototype_1(this-datas);
}
virtual product * concreteprototype_2::clone(){
//return copy of self
return new concreteprototype_2(this-datas);
}
有Java经验的会在Object中看到clone方法。
clone模式有两个问题:
(一)内存泄漏,在clone函数中新建了一个对象,如果没有在外部接收它,它就不会自己释放自己。
(二)clone一个组件,如组合模式(composite)产生的抽象对象。
第一个问题的解决方案为智能指针,有很多文献介绍过这类问题。
这里讨论如何用clone模式clone一个组件。
virtual component * component::clone(){
component * pnew = new component(this-datas);
for(all components of this object (this-o)){
if(this-o != NULL)
//复制本组件中的每一个元件
pnew-o = this-o-clone();
}
return pnew;
}譬如一个链表结点类:class Node{
private:
DataType datas;
Node * next;
public:
virtual Node* clone(){
Node* pnew=new Node(this-datas);
if(this-next != NULL)pnew-next = this-next-clone();
return pnew;
}
//other codes
}
这样复制一个结点与复制一个链表统一起来了,不是很好吗?大功告成。
但是不要高兴太早,现在有一个链表,是循环链表(单向),试用上面方法复制它。 你将会进入死循环,最后内存耗竭而报错.
最后一个结点的下一个为头结点,应该将其后向指针指向新建的头结点,而不是再生成一个结点。
即将上面代码改为:...
for(all components of this object (this-o)){
if(this-o ==NULL){
pnew-o=NULL;
}else if(this-o 未被复制){
//复制本组件中的每一个元件
pnew-o = this-o-clone();
}else{
pnew-o = this-o 的复制品;
}
return pnew;
}
为判断组件 o 是否已经被复制应该在组件 o 中加一个标志cloned,cloned为真表示已经被复制。 为找到组件 o 的复制品应该在组件 o
中保存复制品的地址 pclone。
this-cloned=true;
this-pclone=pnew;
...
if(this-o == NULL)
pnew-o=NULL;
}else if(this-o-cloned==false){
//复制本组件中的每一个元件
pnew-o = this-o-clone();
}else{
pnew-o = this-o-pclone;
}注意,执行一次clone操作后必须将cloned置false.
当然还有其它方法表示是否已经复制.class Node{
static int Cloned=0;
int cloned=0;
...
virtual Node * clone(){
...
if(cloned==Cloned){
//已经复制
...
}else{
//未复制
...
}
...
}
public:
Node * clone_for_call(){
Cloned++;
return clone();
}
...
}
如果Cloned不溢出,就有对每个结点node,node.cloned<=Cloned(已经复制时取等号)。
