woaidongmao

文章均收录自他人博客,但不喜标题前加-[转贴],因其丑陋,见谅!~
随笔 - 1469, 文章 - 0, 评论 - 661, 引用 - 0
数据加载中……

一种基于引用计数机制的智能指针实现

很久以前就对基于引用计数的指针指针很感兴趣,今天突然又一次想到这个问题,所以就写了一个基于引用技术的智能指针。该智能指针的具体实现方式如下:

  1clip_image001#include <iostream>
  2clip_image001#include <numeric>
  3clip_image001#include <algorithm>
  4clip_image001#include <map>
  5clip_image001#include <assert.h>
  6clip_image001
  8clip_image001
  9clip_image001using namespace std;
10clip_image001
11clip_image001template<typename T>
12clip_image001class SmartPointByRefCount
13clip_image002clip_image003clip_image004{
14clip_image005public:
15clip_image005    SmartPointByRefCount(T* pT) : m_pT(pT)
16clip_image006clip_image007    clip_image004{
17clip_image005        SmartPointByRefCount::AddRefCount((unsigned int)m_pT);
18clip_image008    }
19clip_image005
20clip_image005    SmartPointByRefCount(const SmartPointByRefCount& ref)
21clip_image006clip_image007    clip_image004{
22clip_image005        SmartPointByRefCount::AddRefCount((unsigned int)(ref.m_pT));
23clip_image005        m_pT = ref.m_pT;
24clip_image008    }
25clip_image005
26clip_image005    SmartPointByRefCount& operator=(const SmartPointByRefCount& ref)
27clip_image006clip_image007    clip_image004{
28clip_image005        if (this != &ref)
29clip_image006clip_image007        clip_image004{
30clip_image005            SmartPointByRefCount::AddRefCount(ref.m_pT);
31clip_image005            m_pT = ref.m_pT;
32clip_image008        }
33clip_image005
34clip_image005        return *this;
35clip_image008    }
36clip_image005
37clip_image005    ~SmartPointByRefCount()
38clip_image006clip_image007    clip_image004{
39clip_image005        if (SmartPointByRefCount::IsShouldDelete((unsigned int)m_pT))
40clip_image006clip_image007        clip_image004{
41clip_image005            SmartPointByRefCount::DelRefCount((unsigned int)m_pT);
42clip_image005            delete m_pT;
43clip_image008        }
44clip_image005        else
45clip_image006clip_image007        clip_image004{
46clip_image005            SmartPointByRefCount::RedRefCount((unsigned int)m_pT);
47clip_image008        }
48clip_image008    }
49clip_image005
50clip_image005    T* operator->()
51clip_image006clip_image007    clip_image004{
52clip_image005        return m_pT;
53clip_image008    }
54clip_image005
55clip_image005    T& operator*()
56clip_image006clip_image007    clip_image004{
57clip_image005        return *m_pT;
58clip_image008    }
59clip_image005
60clip_image005private:
61clip_image005    T *m_pT;
62clip_image005
63clip_image005private:
64clip_image005    static std::map<unsigned int, unsigned int> m_mapUseCount;
65clip_image005
66clip_image005public:
67clip_image005    static bool IsShouldDelete(unsigned int);
68clip_image005    static void AddRefCount(unsigned int);
69clip_image005    static void RedRefCount(unsigned int);
70clip_image005    static void DelRefCount(unsigned int);
71clip_image009};
72clip_image001
73clip_image001
74clip_image001template<typename T>  std::map<unsigned int, unsigned int> SmartPointByRefCount<T>::m_mapUseCount;
75clip_image001
76clip_image001template<typename T> 
77clip_image001bool SmartPointByRefCount<T>::IsShouldDelete(unsigned int nPointer)
78clip_image002clip_image003clip_image004{
79clip_image005    std::map<unsigned int, unsigned int>::const_iterator it = m_mapUseCount.find(nPointer);
80clip_image005    if (it != m_mapUseCount.end())
81clip_image006clip_image007    clip_image004{
82clip_image005        return ( 1 == it->second );
83clip_image008    }
84clip_image005    else
85clip_image006clip_image007    clip_image004{
86clip_image005        assert(false);
87clip_image005        return false;
88clip_image008    }
89clip_image009}
90clip_image001
91clip_image001template<typename T> 
92clip_image001void SmartPointByRefCount<T>::AddRefCount(unsigned int nPointer)
93clip_image002clip_image003clip_image004{
94clip_image005    std::map<unsigned int, unsigned int>::iterator it = m_mapUseCount.find(nPointer);
95clip_image005    if (it != m_mapUseCount.end())
96clip_image006clip_image007    clip_image004{
97clip_image005        (it->second)++;
98clip_image008    }
99clip_image005    else
100clip_image006clip_image007    clip_image004{
101clip_image005        m_mapUseCount[nPointer] = 1;
102clip_image008    }
103clip_image009}
104clip_image001
105clip_image001template<typename T> 
106clip_image001void SmartPointByRefCount<T>::RedRefCount(unsigned int nPointer)
107clip_image002clip_image003clip_image004{
108clip_image005    std::map<unsigned int, unsigned int>::iterator it = m_mapUseCount.find(nPointer);
109clip_image005    if (it != m_mapUseCount.end() && 1 < it->second)
110clip_image006clip_image007    clip_image004{
111clip_image005        (it->second)--;
112clip_image008    }
113clip_image005    else
114clip_image006clip_image007    clip_image004{
115clip_image005        assert(false);
116clip_image008    }
117clip_image009}
118clip_image001
119clip_image001template<typename T> 
120clip_image001void SmartPointByRefCount<T>::DelRefCount(unsigned int nPointer)
121clip_image002clip_image003clip_image004{
122clip_image005    std::map<unsigned int, unsigned int>::iterator it = m_mapUseCount.find(nPointer);
123clip_image005    if (it != m_mapUseCount.end())
124clip_image006clip_image007    clip_image004{
125clip_image005        m_mapUseCount.erase(it);
126clip_image008    }
127clip_image005    else
128clip_image006clip_image007    clip_image004{
129clip_image005        assert(false);
130clip_image008    }
131clip_image009}

        以下是测试代码,该智能指针能够完全通过这些测试代码。

1clip_image001SmartPointByRefCount<int> TestSPR(SmartPointByRefCount<int> dd)
2clip_image002clip_image003clip_image004{
3clip_image005    *dd = 4;
4clip_image005    return dd;
5clip_image009}
6clip_image001
7clip_image001
8clip_image001int main(int argc, char *argv)
9clip_image002clip_image003clip_image004{
10clip_image005    SmartPointByRefCount<int> spb1(new int(0));
11clip_image005    SmartPointByRefCount<int> spb2 = TestSPR(spb1);
12clip_image005    *spb1 = 2;
13clip_image005
14clip_image005   
15clip_image006clip_image007    clip_image004{
16clip_image005        SmartPointByRefCount<int> spb3(spb2);
17clip_image005        SmartPointByRefCount<int> spb4 = TestSPR(spb3);
18clip_image008    }
19clip_image005
20clip_image005    return 0;
21clip_image009}

        写完这个智能指针之后我在网上找了找其他人写的智能指针,发现智能指针有两种典型实现方式:侵入式、非侵入式,而我的实现方式是非侵入式的。以下两篇文章是从网上引用的,从这两篇文章中发现了一些问题,也学到了一些知识。以下引用内容的所有版权归原作者所有。

第一篇:
            
一种自适应的引用计数智能指针的实现

0 引言
       
自行管理内存是C ++ 语言的一个重要特征, 它为开发人员充分、灵活利用内存空间提供了方 便,但同时也负担了大量内存的请求、释放工作.
 
程序的逻辑错误以及不确定的异常引发,通常会由于内存未释放而造成系统的内存泄漏. 实际工 作证明,内存泄漏是最主要的C + + 程序Bug  ,由程序进行自动内存管理可有效地避免内存 泄漏,这也是提高C + + 程序质量的重要途经之 .
自动内存管理通常的方式是引入垃圾回收 (Garbage Collection) 机制. 垃圾回收作为动态语言 的特征之一早已存在于多种程序设计语言中, JavaPython . 遗憾的是最新的C ++ 标准并没有将其引入,同时,由于C ++ 语言是强类型的静态语言,通过程序来模拟垃圾回收机制非常困难,且功能有限. 避开垃圾回收,通过运用C ++ 语言的运算符重载和范型机制,C ++ 社区产生了称为智能指针(Smart Pointer) 的内存工具. 所谓智能指针,实际上是一种类模板,当其实例化后包含有指向动态分配内存的指针,它通过重载* ->运算符来模拟指针的行为,同时在适当的时候释放内存,以达到自动内存管理的目的,其定义通常为template < typename T > class Smart Ptr. 现在,智能指针在C ++ 应用开发中大量使用, 已经成为C ++ 标准的工具之一.

1   智能指针的一般实现和使用
 
通常,智能指针按使用的策略分为两类:一类是面向控制资源的所有权的智能指针,这类智能指针保证资源只被一个确定的对象使用,任何智能指针的拷贝或传递均会发生所有权的转换,如标准库提供的std : :auto ptr[1 ] ;另一类是面向资源共享的智能指针,这类智能指针内部通常存在使用资源的记数器,称为引用计数,它保证引用计数为0 (即不再有对象使用资源) 释放资源, Boost 库的boost : :shared ptr[2 ] . 智能指针能很好的完成内存自动释放,而它
 
的使用与普通指针非常类似:
{
 
  
⋯⋯
  
 //定义int 的智能指针si
       boost : :shared ptr < int > si = new int (1) ;
      //
直接使用si
      std::cout<<*si<<std : :endl ;
      //
定义string 的智能指针st
      boost::shared-ptr<std::string > st = new std::string(″Foo″) ;
      //
通过- > 运算符访问string 的成员函数
      st->clear () ;
      //qt
st 访问的是同一资源
      boost : :shared ptr < std : :string > qt = st ;
      qt - > append(″Bar″) ;
      
⋯⋯
       //si st
中的指针将自动释放
}

2   引用计数的实现
       
资源共享型的智能指针引用计数的设计,一般分侵入式与非侵入式两种. 侵入式引用计数,将计数器作为包含对象的一部分,该方法效率比较 高,但要求包含类型总是继承自一个计数对象;非侵入式引用计数,计数器通过动态内存分配获得,任何的对象均可作为智能指针的范型参数,但小内存的new 操作会降低智能指针的效率. 关于效率和灵活的平衡,在智能指针的设计中是不能完成的,只有把这个问题交给智能指针的使用者. 但通过模板元编程以及模板偏特化,我们可以为使用者提供自动识别包含类型的智能指针[3 ] . 通过模板元编程可在程序的编译期间判断一个类型是否继承自计数对象,如果是则采用侵入式,否则采用非侵入式.侵入式的引用计数应继承的基类:
   class IntrusiveRefCount
   {
   //
操作引用计数成员函数
  
⋯⋯
   protected :
  
  int refCount ;PPP< 引用计数
  } ;
 
通过不同的方式实现智能指针,模板参数IntrRefCount 缺省为True ,即采用侵入式:
  template < typename T,bool IntrRefCount >
  class SmartPtrImp
  {
 
  //重载赋值运算符.
   
 //通过调用T的成员函数DecRef()IncRef ( ) 来改变引用值
        SmartPtrImp &operator = (const SmartPtrImp &sptr)
        {
          //
释放当前资源
          if (pointee ! = 0 &&pointee - > DecRef ( ) == 0)
             delete pointee ;
          pointee = sptr.pointee ;
          if (pointee ! = 0)
            pointee->IncRef() ;
          return *this ;
         }
         //
拷贝构造函数. 同样有引用值的操作
         SmartPtrImp (const SmartPtrImp &sptr) ;
protected :
             T *pointee ;///
对象指针
    };
  
采用模板偏特化参数IntrRefCount ( 特化为false) ,此类模板采用非侵入式模式:
   template < typename T>
   class SmartPtrImp < T,false >
   {
  
  //重载赋值运算符.
 
 //直接new int (0) 来获取记数器
           SmartPtrImp &operator = (T* ptr)
          {
                   if (pointee ! = 0)
                   {
                             if (--(*refCountPtr ) == 0)
                                    delete pointee ;
                           else
                           //
失去了对原对象的控制,原对象的引用计数也要放弃
                               refCountPtr = new int (0) ;
                     }
                  pointee = ptr ;
                  if (pointee ! = 0)
                          ++refCountPtr ;
          return *this ;
}
         //
拷贝构造函数. 同样有引用值的操作
         SmartPtrImp (const SmartPtrImp &sptr) ;
  protected :
         T *pointee ;///
对象指针
        int *refCountPtr;///
引用计数
} ;
 
3       
智能指针的实现
       
现在我们需要一个算法判断一个类是否是另一个类的子类的范型算法[4 ] ,实现如下:
       
//如果没有看过陈伟柱翻译的《C++ Template》的话下面的代码可能很难看懂,如果看不懂的话,不妨找这本书看一下
         template < typename D ,typename B >
         struct IsDerivedFrom
         {
                 class No {} ;
                 class Yes {No no[2 ] ;} ;
       
      static Yes Test (B*) ;
 
          static No Test (
) ;
            
 enum {Is = sizeof (Test ( static cast <D*> (0) ) ) = = sizeof(Yes) } ;
         } ;
        
如果类型D B 的子类IsDerivedFrom < D ,B>::Is 的值就为1.
        
有了如上工具,我们就可以将智能指针的实现拼接起来:
           template < typename T>
           class SmartPtr :
 
      public SmartPtrImp < T, IsDerivedFrom < T, IntrusiveRefCount>::Is == 1 >
           {
   
      typedef SmartPtrImp < T, IsDerivedFrom < T, IntrusiveRefCount>::Is == 1, Deletor < T > > ParentCls ;
  
     public :
   
     SmartPtr () :ParentCls () {}
  
   explicit SmartPtr (T &t) :ParentCls (t) {}
    
     explicit SmartPtr (T*t) :ParentCls (t) {}
   
   SmartPtr (const SmartPtr &sptr) :ParentCls (sptr) {}
     }

                         
       
从以上的说明上看,这篇论文只有一点有价值的——讲明白了智能指针的两种实现方式,侵入式和非侵入式。至于这篇自适应的说法,个人感觉在编码的时候根本不会用到。其中红色的文字是我添加的。


第二篇:

       
指针 是C++中不得不谈的一个话题,或许我还不是很能熟练的掌握指针以及我所要讨论的引用计数型指针的全部,但是还是有那么些迫不及待想要表达一下。
       
指针pointer 是资源泄漏 resource leak 的根源(当然可能还有其他一些什么东西,在我的映像中 异常 仿佛也会造成资源泄漏)最简单的一个资源泄漏的例子就是newdelete这样的动态内存分配算子没有正确使用造成的:
struct A
{
A()  { printf("A Constructor!"); }
~A() { printf("A Destructor!"); }
};

void area()
{
A *p = new A();
}
执行完 area() 后,自然是只有A构造的消息,而A的析构却不见影踪。这里我们在离开了area作用域后,我们就无法对p所指向之资源进行操作,A的实例就会被悬挂在内存的某处得不到清理。一个形象点的比方就像人类发送的宇宙卫星失去了动力以及和地球的联系,无法收回,就变成了宇宙垃圾~。
然而利用对象来管理资源是一个很好的办法,因为对象的实例本身在脱离作用域后会自动清理,就像这样

class  A_holder
{
public:
expilict A_holder(A* p = NULL):ptr(p) {}

~A_holder()
{
if (ptr)
delete ptr;
}
private:
A* ptr;
};
如此,我们在area里面把资源的管理权力交给A_holder,就像下面这样
void area()
{
A_holder ah(new A);
}
这样,ah在离开area后会自动调用其析构函数,就达到了自动管理该资源的目的。
利用C++的类的实例离开作用域会自动调用其析构函数的机制,可以比较方便的管理资源,但是在使用普通指针的情况下会存在多个指针指向同一对象的情况。
void multi_point()
{
int a;
int *p1,*p2;

p1 = &a;
p2 = &a;
}
实际的指针指向情况应该是这样 p1 –>ß a à<- p2
这里就出现了一个问题,我们想取消p1的时候可能会出现两种语义:
1
、将p1和其指向的对象一起删除,这样p2也就不可以继续对a进行使用。但是往往p2的使用者不会知道a已经删除,则出现了错误。
2
、将p1与其指向的对象解除关系,这样p2还可以对a进行使用。
对于普通的delete操作,实现的是第一种情况,这样通过p2a进行访问必然会造成致命的错误。
在实现holder类的时候应该也考虑到第二种情况,如果有另外一个holder也指向这个资源,其中一个holder销毁,另外一个holder还可能会使用到它们共同指向的那个资源。于是,holder的作用就不仅仅是单单的持有和施放资源,还应该处理有多少个对其hold资源的引用(即引用计数),并且在引用计数降为0时真正的销毁资源实体。
如此,一个行为类似指针(有->,*操作符)的智能指针出现,它管理赋予其资源的引用计数,也管理该资源的生死存亡。
一个简单的Reference Count Smart Pointer的实现如下:
#ifndef COUNTED_PTR_HPP
#define COUNTED_PTR_HPP
/*class for counted reference semantics
*-deletes the object to which it refers when the last CountedPtr
* that refers to it is destroyed
*/
template <class T>
class CountedPtr
{
private:
T* ptr;        // pointer to the value
long* count;   // shared number of owners
public:
//initialize pointer with existing pointer
//-requires that the pointer p is a return value of new
explicit CountedPtr (T* p=0)
  : ptr(p), count(new long(1)) {}
//copy pointer (one more owner)
CountedPtr (const CountedPtr<T>& p) throw()
  : ptr(p.ptr), count(p.count)
{
  ++*count;
}
//destructor (delete value if this was the last owner)
~CountedPtr () throw()
{
  dispose();
}
//assignment (unshare old and share new value)
CountedPtr<T>& operator= (const CountedPtr<T>& p) throw() {
  if (this != &p) {
   dispose();
   ptr = p.ptr;
   count = p.count;
   ++*count;
  }
  return *this;
}
//access the value to which the pointer refers
T& operator*() const throw() {
  return *ptr;
}
T* operator->() const throw() {
  return ptr;
}
private:
void dispose() {
  if (--*count == 0) {
   delete count;
   delete ptr;
  }
}
};
#endif /*COUNTED_PTR_HPP*/
由此,一个新的问题出现了!循环引用!
这样的一个引用计数型智能指针目的是为了防止资源泄漏,但是只需要一个很小巧的代码就可以让这样的初衷化为乌有……
class A
{
public:
A() {cout<<"A CON"<<endl;}
~A() {cout<<"A DES"<<endl;}

void hold(CountedPtr<A> ptr)
{
  m_ptr = ptr;
}
private:
CountedPtr<A> m_ptr;
};

void self_cir_area()
{
CountedPtr<A> pA(new A());
pA->hold(pA);
}

可以看见,一个对象A中有一个引用计数型智能指针,这样的设计可能会很常见(指向自身类型的结构体——链表)
但是,当自身循环引用发生的时候会怎么样呢? 下面就来看看这么两句代码
CountedPtr<A> pA(new A());
这里我们新建一个资源,并且把这个资源的管理权移交给pA这个引用计数型智能指针对象管理。如此,pA中的引用计数被初始化为1
pA->hold(pA);
这里,我们把pA对象传入给实例化的A对象中的引用计数型智能指针m_ptrm_ptr执行这样的一个成员函数:   
//assignment (unshare old and share new value)
CountedPtr<T>& operator= (const CountedPtr<T>& p) throw() {
if (this != &p) {
  dispose();
  ptr = p.ptr;
  count = p.count;
  ++*count;
}
return *this;
}
因为这里很明显不是自身赋值,A中的m_ptrpA不是同一个对象,所以进入if结构中调用下面的内容。dispose是用作清理,因为m_ptr并没有指向任何东西,所以第一个函数并没有真正的意义。然后
m_ptr.ptr = pA.ptr;
m_ptr.count = pA.count;
++(*m_ptr.count);  //(*pA.count)
也被++
到此,pA的引用计数为2
嗯,下面就pA这个对象理所当然的离开了作用域,调用其析构函数:
~CountedPtr () throw() {
dispose();
}
噢,是一个转向,调用其private成员函数dispose():
void dispose() {
if (--*count == 0) {
  delete count;
  delete ptr;
}
}
很简单,将引用计数-1,由2变成1,不为0,所以if结构内的语句不被执行。
由此,我们又制造了一个完美的太空垃圾……
这样的循环引用问题应该是在设计的过程中就应该避免的,如果用UML语言描述
A
中持有一个 引用计数型智能指针 的语义就是 这个 持有关系 是需要在 A消失的时候所持有的对象也随之消失(这正是智能指针的作用,在脱离作用域自动清除其持有的资源)。如此就构成了组合 关系。如果要表示 聚合 关系,即有 部分-整体 关系但是部分不随整体的消失而消失,这就不是 智能指针 所表达的语义。
还有可能遇见的循环引用就是 A1 持有 A2 A2 持有 A1 的情况……
这样A1,A2中对双方的引用计数都是2,当一方销毁的时候,双方的应用计数都变为1,实际上并没有销毁任何东西,制造了两个完美无暇的太空垃圾~
这里又引发出一个问题,这样的资源泄漏问题实际上还是由程序员自身引起的。
C++
之所以是一个很容易出错的语言,很大一部分在于其资源的管理权力全权交给了程序员。这样的权力到底是造福了程序员还是迷惑了程序员呢?
这里我却想起了蜘蛛侠中的一句名言:一个人能力有多大,责任就有多大!
C++中指针的指责不是一天两天了,其易错性无可厚非,但是它却给了你其他语言无法给你的能力!这就是我的观点,你能力有这么大,你就有责任来治理好这些资源。而非一再推卸责任。如果真的是要推卸责任,也就应该去选择其他那些剥夺你的能力而减少你的责任的语言,因为你有选择权!就像说英语和中文一样,并没有哪个人在强迫你,不是么?热爱C++是一种态度,对一个语言的利弊都了然于心,了解其可以做什么不可以做什么,怎样才可以更好的使用它来做什么,才能更好的使用它。更何况,there are rarely things that are not possible in C++

 

在没有看到这篇文章之前,我觉得智能指针能够应对所有情况,可是看过这篇文章让我了解到智能指针在循环引用的情况下也会出现问题。

另外,我还发现我的operator=函数有问题,具体的问题请参见上面两篇文章的operator=函数。此外,本实现还有一些问题没有考虑:线程安全,if(智能指针)等。
天太晚了,所以就不排版了,请见谅!

 

posted on 2011-04-21 13:04 肥仔 阅读(1860) 评论(0)  编辑 收藏 引用 所属分类: Windows开发


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理