More Effective C++ 条款29 Reference counting(引用计数)

1. reference counting使得多个等值对象可以共享同一实值,这样不仅简化了heap objects的簿记工作,便于管理内存,而且能够节省空间,提升效率.以下讨论以自实现的String为例.

2. Reference Counting(引用计数)的实现

基本设计像这样:

class String {
public:
    ...
private:
    struct StringValue { ... }; // 包含引用计数和字符串值
    StringValue *value; // value of this String
};

View Code
内嵌的结构体StringValue主要用于存储引用计数和字符串值,并使得引用计数和字符串值相关联.StringValue的实现像这样:

class String {
private:
    struct StringValue {
        int refCount;
        char *data;
        StringValue(const char *initValue);
        ~StringValue();
    };
    ...
};
String::StringValue::StringValue(const char *initValue): refCount(1)
{
    data = new char[strlen(initValue) + 1];
    strcpy(data, initValue);
}
String::StringValue::~StringValue()
{
    delete [] data;
}

View Code
StringValue只对String类可见,而对客户不可见,接口由String定义并提供给客户.

String的构造函数:

String(const char *initValue = "");
String(const String& rhs);

第一个构造函数的实现较简单,根据传入的char数组构造StringValue对象,然后使String中的指针指向这个String即可:

String::String(const char *initValue): value(new StringValue(initValue)){}

但这样的实现导致"分开构造,但拥有相同初值的String对象,并不共享同一个数据结构",因此像这样的代码:

String s1("More Effective C++");
String s2("More Effective C++");

尽管是s1和s2的值相同,但它们却并不共享同一个块内存,而是各自拥有独立内存.

拷贝构造函数可以使用引用计数,并共享内存,像这样:

String::String(const String& rhs): value(rhs.value){ ++value->refCount; }

析构函数负责在引用计数为0的时候撤销内存:

String::~String()
{
    if (--value->refCount == 0) 
        delete value;
}

View Code
赋值操作符要注意自身赋值的情况:

String& String::operator=(const String& rhs)
{
    if (value == rhs.value) { //处理自身赋值
        return *this; 
    } 
    if (--value->refCount == 0) { 
        delete value; 
    }
    value = rhs.value; 
    ++value->refCount;
    return *this;
}

View Code
3. Copy-on-Write(写时才复制)

对operator[]的重载比较复杂:const版本是只读动作,因而只返回指定字符即可,像这样:

const char& String::operator[](int index) const{ return value->data[index]; }

但non-const版本面临着被写入新的值的可能,由于对当前String的修改不应影响到共享内存的其他String对象,因此需要先为当前String分配独立内存并将原值进行拷贝,像这样:

char& String::operator[](int index)
{
    if (value->refCount > 1) {
        --value->refCount; 
        value =new StringValue(value->data); 
    }
    return value->data[index];
}

View Code
不仅是operator[],其他可能改变String对象的操作也应该采取和non-cons版本operator[]相同的动作.这其实是lazy evaluation的一种应用.

1. Pointers,References,以及Copy-on-Write

3中对operator[]的重载解释并解决了可能的写操作篡改共享内存的问题,但是却无法阻止外部指针或引用对共享内存的篡改,像这样:

String s1 = "Hello";
char *p = &s1[1];
String s2 = s1;

对p所指向的内存的任何写操作都会同时更改s1和s2的值,但是s1却对此一无所知,因为p和s1没有内在联系.解决办法并不难:为每一个StringValue对象加一个标志(flag)变量,用表示是否可以被共享,开始时先将flag设为true(可以共享),一旦non-const operator[]被调用就将该flag设为false,并可能永远不许再更改(除非重新为StringValue分配更大内存而导致指针失效),StringValue的修改版像这样:

class String {
private:
    struct StringValue {
        int refCount;
        bool shareable; 
        char *data;
        StringValue(const char *initValue);
        ~StringValue();
    };
    ...
};
String::StringValue::StringValue(const char *initValue): refCount(1),shareable(true) 
{
    data = new char[strlen(initValue) + 1];
    strcpy(data, initValue);
}
String::StringValue::~StringValue()
{
    delete [] data;
}

View Code
String的member function在企图使用共享内存前,就必须测试内存是否允许被共享:

String::String(const String& rhs)
{
    if (rhs.value->shareable) {
        value = rhs.value;
        ++value->refCount;
    }
    else {
        value = new StringValue(rhs.value->data);
    }
}

View Code
其他返回引用的member function(对于String只有operator[])都涉及到对flag的修改,而其他可能需要共享内存的member function都涉及到对flag的检测.

条款30的proxy class技术可以将operator[]的读和写用途加以区分,从而降低"需被标记为不可共享"之StringValue对象的个数.

1. 一个Reference-Counting(引用计数)基类

任何要支持内存共享的class都可以使用reference-counting,因此可以考虑把它抽象为一个类,任何需要reference-counting功能的class只要使用这个类即可.

第一步就是产生一个base class RCObject,执行引用计数的功能并标记对象是否可被共享,像这样:

class RCObject {
public:
    RCObject();
    RCObject(const RCObject& rhs);
    RCObject& operator=(const RCObject& rhs);
    virtual ~RCObject() = 0;
    void addReference();
    void removeReference();
    void markUnshareable();
    bool isShareable() const;
    bool isShared() const;
private:
    int refCount;
    bool shareable;
};

View Code
由于RCObject的作用只是实现引用计数的辅助功能,然后让StringValue继承它,因此StringValue被设为一个抽象基类——通过将析构函数设为纯虚函数,但仍需要为析构函数提供定义.RCObject的实现像这样:

RCObject::RCObject(): refCount(0), shareable(true) {}
RCObject::RCObject(const RCObject&):refCount(0),shareable(true) {}
RCObject& RCObject::operator=(const RCObject&)
{ return *this; }
RCObject::~RCObject() {} // virtual dtors must always
void RCObject::addReference() { ++refCount; }
void RCObject::removeReference()
{ if (--refCount == 0) delete this; }
void RCObject::markUnshareable()
{ shareable = false; }
bool RCObject::isShareable() const
{ return shareable; }
bool RCObject::isShared() const
{ return refCount > 1; }

View Code
RCObject的实现非常简单,但是其拷贝构造函数和赋值操作符有些特殊——它们的参数没有名字,也就是说参数没有作用,其拷贝构造函数和赋值操作符都只是形式上的:

RCObjetc拷贝构造函数与RCObject的作用相对应——RCObject一旦被构造,就说明一个新的对象被产生出来,那么RCObject对象本身的初始值和默认构造函数相同,至于refCount设为0而不是1,这要求对象创建者自行将refCount设为1.

RCObject的赋值操作符什么也不做,仅仅返回*this,因为它不应该被调用,正如之前的StringValue,如果对String对象赋值,那么或者StringValue被共享,或者拷贝构造一个新的StringValue,实际上StringValue的赋值操作永远不会被调用.即使要对StringValue做赋值操作,像这样:

sv1=sv2;//sv1和sv2是StringValue型对象

指向sv1和sv2的对象数目实际上并未改变,因此sv1的基类部分RCObject什么也不做仍然是正确的.

removeReference的责任不仅在于将refCount减1,实际上还承担了析构函数的作用——在refCount=1的时候delete销毁对象,从这里可以看出RCObject必须被产生于heap中.

StringValue要直接使用RCObject,像这样:

class String {
private:
    struct StringValue: public RCObject {
        char *data;
        StringValue(const char *initValue);
        ~StringValue();
    };
    ...
};
String::StringValue::StringValue(const char *initValue)
{
    data = new char[strlen(initValue) + 1];
    strcpy(data, initValue);
}
String::StringValue::~StringValue()
{
    delete [] data;
}

View Code
StringValue类public继承自RCObject,因此它继承了RCObject的接口并供String使用,StringValue也必须构造在heap中.

1. 自动操作Reference Count(引用计数)

RCObject提供了一定程度的代码复用功能,但还远远不够——String类仍然需要手动调用RCObject的成员函数来对引用计数进行更改.解决方法就是"计算机科学领域中大部分问题得以解决的原理"——在中间加一层,也就是在String和StringValue中间加一层智能指针类对引用计数进行管理,像这样:

//管理引用计数的智能指针类
template<class T>
class RCPtr {
public:
    RCPtr(T* realPtr = 0);
    RCPtr(const RCPtr& rhs);
    ~RCPtr();
    RCPtr& operator=(const RCPtr& rhs);
    T* operator->() const; // see Item 28
    T& operator*() const; // see Item 28
private:
    T *pointee; 
    void init(); //将构造函数中的重复操作提取成一个函数
};

View Code
之前RCPtr是一个类模板,String之前有一个StringValue*成员,现在只要将它替换为RCPtr即可.

RCPtr的构造函数像这样:

template<class T>
RCPtr<T>::RCPtr(T* realPtr): pointee(realPtr)
{
    init();
}
template<class T>
RCPtr<T>::RCPtr(const RCPtr& rhs): pointee(rhs.pointee)
{
    init();
}
template<class T>
void RCPtr<T>::init()
{
    if (pointee == 0) {
        return; 
    }
    if (pointee->isShareable() == false) { 
        pointee = new T(*pointee); 
    } 
    pointee->addReference();//引用计数的更改负担转移到这里
}

View Code
init中使用了new关键字,它调用T的拷贝构造函数,为防止编译器为StringValue合成的拷贝构造函数执行浅复制,需要为StringValue定义执行深度复制的拷贝构造函数,像这样:

String::StringValue::StringValue(const StringValue& rhs)
{
    data = new char[strlen(rhs.data) + 1];
    strcpy(data, rhs.data);
}

View Code
此外,由于多态性的存在,尽管pointee是T*类型,但它实际可能指向T类型的派生类,在此情况下new调用的却是T的拷贝构造函数,要防止这种现象,可以使用virtual copy constructor(见条款25),这里不再讨论.

RCPrt的其余实现像这样:

template<class T>
RCPtr<T>& RCPtr<T>::operator=(const RCPtr& rhs)
{
    if (pointee != rhs.pointee) {
        if (pointee) {
            pointee->removeReference();
        } 
        pointee = rhs.pointee; 
        init(); 
    } 
    return *this;
}
template<class T>
RCPtr<T>::~RCPtr()
{
    if (pointee)pointee->removeReference();
}
template<class T>
T* RCPtr<T>::operator->() const { return pointee; }
template<class T>
T& RCPtr<T>::operator*() const { return *pointee; }

View Code
7. 把所有努力放到这里

String,StringValue,RCObject的关系像这样:

各个类的定义如下:

//用于产生智能指针的类模板，T必须继承自RCObject
template<class T> 
class RCPtr {
public: 
    RCPtr(T* realPtr = 0);
    RCPtr(const RCPtr& rhs);
    ~RCPtr();
    RCPtr& operator=(const RCPtr& rhs);
    T* operator->() const;
    T& operator*() const;
private:
    T *pointee;
    void init();
};
//抽象基类用于引用计数
class RCObject { 
    void addReference();
    void removeReference();
    void markUnshareable();
    bool isShareable() const;
    bool isShared() const;
protected:
    RCObject();
    RCObject(const RCObject& rhs);
    RCObject& operator=(const RCObject& rhs);
    virtual ~RCObject() = 0;
private:
    int refCount;
    bool shareable;
};
//应用性class
class String { 
public:
    String(const char *value = "");
    const char& operator[](int index) const;
    char& operator[](int index);
private:
    //勇于表现字符串值
    struct StringValue: public RCObject {
        char *data;
        StringValue(const char *initValue);
        StringValue(const StringValue& rhs);
        //
        void init(const char *initValue);
        ~StringValue();
    };
    RCPtr<StringValue> value;
};

View Code
RCObject的实现:

RCObject::RCObject(): refCount(0), shareable(true) {}
RCObject::RCObject(const RCObject&): refCount(0), shareable(true) {}
RCObject& RCObject::operator=(const RCObject&)
{ return *this; }
RCObject::~RCObject() {}
void RCObject::addReference() { ++refCount; }
void RCObject::removeReference()
{ if (--refCount == 0) delete this; }
void RCObject::markUnshareable()
{ shareable = false; }
bool RCObject::isShareable() const
{ return shareable; }
bool RCObject::isShared() const
{ return refCount > 1; }

View Code
RCPtr的实现:

template<class T>
void RCPtr<T>::init()
{
    if (pointee == 0) return;
    if (pointee->isShareable() == false) {
        pointee = new T(*pointee);
    }
    pointee->addReference();
}
template<class T>
RCPtr<T>::RCPtr(T* realPtr): pointee(realPtr)
{ init(); }
template<class T>
RCPtr<T>::RCPtr(const RCPtr& rhs): pointee(rhs.pointee)
{ init(); }
template<class T>
RCPtr<T>::~RCPtr()
{ if (pointee)pointee->removeReference(); }
template<class T>
RCPtr<T>& RCPtr<T>::operator=(const RCPtr& rhs)
{
    if (pointee != rhs.pointee) {
        if (pointee) pointee->removeReference();
        pointee = rhs.pointee;
        init();
    }
    return *this;
}
template<class T>
T* RCPtr<T>::operator->() const { return pointee; }
template<class T>
T& RCPtr<T>::operator*() const { return *pointee; }

View Code
StringValue的实现:

void String::StringValue::init(const char *initValue)
{
    data = new char[strlen(initValue) + 1];
    strcpy(data, initValue);
}
String::StringValue::StringValue(const char *initValue)
{ init(initValue); }
String::StringValue::StringValue(const StringValue& rhs)
{ init(rhs.data); }
String::StringValue::~StringValue()
{ delete [] data; }

View Code
String的实现:

String::String(const char *initValue): value(new StringValue(initValue)) {}
const char& String::operator[](int index) const
{ return value->data[index]; }
char& String::operator[](int index)
{
    //String类唯一需要接触底层成员的负担
    if (value->isShared()) { value = new StringValue(value->data); }             
    value->markUnshareable(); return value->data[index]; 
}

View Code
可以看出String的实现异常简单,因为所有的引用计数任务全部交由其他可移植性类实现,也就是说,任何其他需要引用计数的类只要像String类一样使用RCPtr,RCObject类即可.

1. 将Reference Counting加到既有的Classes身上

有了以上设计,就可以使任何需要引用计数功能的类只要继承RCObject,并作为已有的RCPtr模板的类型参数即可.但程序库中的类却无法更改:假设程序库中存在一个名为Widget的类,我们无法修改它,因此也就无法使它继承RCObject.但只要采取之前所用的"中间加一层的方法,这种目标仍可以达成":

首先假设我们可以修改Widget,那么就可以使Widget继承RCObject,来充当StringValue的角色,像这样:

由于不能修改Widget,采用中间加一层的方法,增加一个新的CountHolder class,继承自RCObject并持有Widget指针,然后把RCPtr类模板用具有相同功能但内部定义了CountHolder的RCIPtr取代(I指indirect,间接),像这样:

RCIPtr和CountHolder的实现如下:

template<class T>
class RCIPtr {
public:
    RCIPtr(T* realPtr = 0);
    RCIPtr(const RCIPtr& rhs);
    ~RCIPtr();
    RCIPtr& operator=(const RCIPtr& rhs);
    const T* operator->() const; 
    T* operator->(); 
    const T& operator*() const; 
    T& operator*(); 
private:
    struct CountHolder: public RCObject {
        ~CountHolder() { delete pointee; }
        T *pointee;
    };
    CountHolder *counter;
    void init();
    void makeCopy(); 
};
template<class T>
void RCIPtr<T>::init()
{
    if (counter->isShareable() == false) {
        T *oldValue = counter->pointee;
        counter = new CountHolder;
        counter->pointee = new T(*oldValue);
    }
    counter->addReference();
}
template<class T>
RCIPtr<T>::RCIPtr(T* realPtr): counter(new CountHolder)
{
    counter->pointee = realPtr;
    init();
}
template<class T>
RCIPtr<T>::RCIPtr(const RCIPtr& rhs): counter(rhs.counter)
{ init(); }
template<class T>
RCIPtr<T>::~RCIPtr()
{ counter->removeReference(); }
template<class T>
RCIPtr<T>& RCIPtr<T>::operator=(const RCIPtr& rhs)
{
    if (counter != rhs.counter) {
        counter->removeReference();
        counter = rhs.counter;
        init();
    }
    return *this;
}
template<class T> 
void RCIPtr<T>::makeCopy()
{ 
    if (counter->isShared()) {
        T *oldValue = counter->pointee;
        counter->removeReference();
        counter = new CountHolder;
        counter->pointee = new T(*oldValue);
        counter->addReference();
    }
}
template<class T>
const T* RCIPtr<T>::operator->() const 
{ return counter->pointee; }
template<class T> 
T* RCIPtr<T>::operator->() 
{ 
    makeCopy();
    return counter->pointee; 
}
template<class T>
const T& RCIPtr<T>::operator*() const 
{ return *(counter->pointee); }
template<class T>
T& RCIPtr<T>::operator*() 
{ 
    makeCopy(); 
    return *(counter->pointee); 
}

View Code
CountHolder只对RCIPter可见,因此设为private,此外,RCIPtr提供了non-const版本的operator->和operator*,只要有non-const 函数被调用,copy-on-write就被执行.

有引用计数功能的RCWidget只要通过底层的RCIPtr调用对应的Widget函数即可,如果Widget的接口像这样:

class Widget {
public:
    Widget(int size);
    Widget(const Widget& rhs);
    ~Widget();
    Widget& operator=(const Widget& rhs);
    void doThis();
    int showThat() const;
    ...
};

View Code
那么RCWidget只要被定义成这样:

class RCWidget {
public:
    RCWidget(int size): value(new Widget(size)) {}
    void doThis() { value->doThis(); }
    int showThat() const { return value->showThat(); }
private:
    RCIPtr<Widget> value;
};

View Code
9. 引用计数的代码复杂的多,因此只有在以下情况下才会发挥它的优化功能:

1). 相对多的对象共享相对少的内存

2). 对象实值的产生和销毁成本太高,或者使用太多内存

如果引用计数使用不当,反而会降低程序效率.
原文链接: https://www.cnblogs.com/reasno/p/4857432.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍