More Effective C++: 05技术(29)

29：引用计数

         本章首先实现一个带引用计数String，然后逐步优化，介绍引用计数的常规实现。

         实现引用计数的String，首先需要考虑：引用计数在哪存储。这个地方不能在String对象内部，因为需要的是每个String值一个引用计数值，这意味着String值和引用计数间是一一对应的关系，因此需要创建一个类来保存引用计数及其跟踪的值。我们叫这个类StringValue。下面就是一个引用计数String的最简单实现：

class String {
public:
    String(const char *initValue = "");
    String(const String& rhs);
    ~String();
String& operator=(const String& rhs);

    const char& operator[](int index) const; // for const Strings
    char& operator[](int index); // for non-const Strings

private:
    struct StringValue {
        int refCount;
        char *data;
        StringValue(const char *initValue);
        ~StringValue();
    };
    StringValue *value;
};

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

String::String(const char *initValue):value(new StringValue(initValue)){}
String::String(const String& rhs):value(rhs.value){
    ++value->refCount;
}
String::~String(){
    if (--value->refCount == 0) delete value;
}
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;
}

         下面重点看下operator[]的实现。const版本的实现很容易，因为它是一个只读操作，String对象的值不受影响：

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

         非const的operator[]版本，它被调用可能用来读一个字符，也可能写一个字符。因此我们希望以不同的方式处理读和写，但C++编译器没有办法告诉我们一个特定的operator[]是用作读的还是写，所以我们必须保守地假设所有调用非const operator[]的行为都是为了写操作。为了安全地实现非const的operator[]，必须确保没有其它String对象在共享这个可能被修改的StringValue对象。简而言之，当我们返回StringValue对象中的一个字符的引用时，必须确保这个StringValue的引用计数是1：

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

这个"与其它对象共享一个值直到写操作时才拥有自己的拷贝"的想法在计算机科学中已经有了悠久而著名的历史了，尤其是在操作系统中：进程共享内存页直到它们想在自己的页拷贝中修改数据为止。这个技巧如此常用，以至于有一个名字：写时拷贝。它是提高效率的一个更通用方法－－Lazy原则－－的特例。

大部分情况下，写时拷贝可以同时保证效率和正确性。只有一个挥之不去的问题：

String s1 = "Hello";
char *p = &s1[1];
String s2 = s1;
*p = 'x'; // 将同时修改s1和s2

有三种方法来应付这个问题。第一个是忽略它，假装它不存在；第二种方法稍微好些，明确说明它的存在，通常是将它写入文档，或多或少地说明“别这么做。如果你这么做了，结果为未定义”；第三个方法是排除这个问题。它不难实现，但它将降低一个值共享于对象间的次数。它的本质是这样的：在每个StringValue对象中增加一个标志以指出它是否为可共享的。在最初（对象可共享时）将标志打开，在非const的operator[]被调用时将它关闭。一旦标志被设为false，它将永远保持在这个状态：

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

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

所有其它的成员函数也都必须以类似的方法检查这个共享标志。非const的operator[]版本是唯一将共享标志设为false的地方：

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

         借助String/StringValue的实现，现在来考虑通用引用计数的实现。首先，将StringValue中的refCount和shareable部分独立出来：定义一个基类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;
};

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; }

         在构造函数中，将refCount置为0，RCObject的创建者负责调用addReference增加其引用计数。

operator=运算符实际上什么也没做。这个运算符不太可能被调用。RCObject是针对“实值可共享”之对象而设计的一个基类，在一个拥有引用计数能力的系统中，此等对象并不会被赋值给另一个对象。比如，StringValue对象不会被赋值，只有String对象会被赋值，这样的赋值动作中，StringValue的实值不会有任何改变，只有StringValue的引用次数会被改变。

RCObject::removeReference的代码负责减少对象的refCount值，还负责当refCount值降到0时析构对象。这通过delete this来实现的，这只当*this是一个堆对象时才安全。要让这个类正确，必须确保RCObject只能被构建在堆中。实现这一点的常用方法见条款27，但我们这次采用一个特别的方法，这将在本条款最后讨论。

下面是使用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;
}

RCObject仅仅提供了操作refCount和shareable的能力，继承该类的StringValue的代码改动不大，RCObject操作refCount的动作还需要在其他类（String）中手动完成。我们希望这些调用动作也被封装起来，这样诸如String这样的类就无需操心引用计数的任何细节了。

没有什么轻松的办法可以让所有与引用计数相关的杂务都从应用性类身上移走，但是有一个办法可以为大部份类消除大部份杂务。（某些应用性类可以去除引用计数的所有相关杂务，但是本例的String不是其中一员，因为它有个non-const operator[]函数需要定义） 

查看之前String/StringValue的实现，String内含一个指针指向StringValue对象，StringValue用以表示String的实值。为了能够当指针发生动作（复制、赋值、摧毁）时操作refCount字段，可以使用智能指针。下面就是一个智能指针的实现：

// T 必须支持 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(); //共同的初始化动作
};

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();
}

init函数中，当处于非共享状态时，需要创建value的一个新拷贝：pointee=new T(*pointee); 如果String使用RCPtr，则T将是String::StringValue，因此该语句将会调用StringValue的复制构造函数，但是我们没有定义StringValue的复制构造函数，而StringValue中又包含data数据，因此，编译器定义的默认复制构造函数不符合要求，所以需要定义StringValue的复制构造函数：

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

另外还有一个问题，pointee有可能指向T的一个派生类，比如假设SpecialStringValue继承于StringValue，RCPtr<StringValue>中的pointee实际指向一个SpecialStringValue，所以pointee = new T(*pointee);应该调用SpecialStringValue复制构造函数，而非StringValue的复制构造函数，可以使用虚复制构造函数实现这一点。对于String类而言，不期望从StringValue派生子类，所以这里忽略这个问题。

下面是剩下的代码：

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; }

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;
};

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; }

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){
    if (value->isShared()) {
        value = new StringValue(value->data);
    }
    value->markUnshareable();
    return value->data[index];
}

有了RCPtr，String中无需再声明复制构造函数、赋值操作符和析构函数了，使用编译器默认生成的版本，调用RCPtr相应的函数就能完成引用计数的所有工作。上面的所有代码，形成的结构图如下：

 

 

上面的设计，有一个问题就是，为了实现引用计数功能的String，必须修改String的源码。如果想让引用计数施行与库中的一个Widget类，库中的代码不可更改的，这该怎么办？

计算机科学中的绝大部分问题都可以通过增加一个中间层次来解决。这里需要将Widget视为StringValue，提供给用户一个RCWidget类使用。但是无法使Widget继承RCObject，因此增加一个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>
const T* RCIPtr<T>::operator->() const //const访问，不需要写时复制
{ return counter->pointee; }
template<class T>
const T& RCIPtr<T>::operator*() const //const访问，不需要写时复制
{ return *(counter->pointee); }

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>
T* RCIPtr<T>::operator->() // non-const访问，需要写时复制
{ makeCopy(); return counter->pointee; }

template<class T>
T& RCIPtr<T>::operator*() // non-const访问，需要写时复制
{ makeCopy(); return *(counter->pointee); }


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

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

 

关于引用计数的讨论就可以到此结束了，不过之前还有一个问题没有解决：当  RCObject::removeReference检查新的计数为0时，会以delete this的方式销毁这个对象。只有当对象是以new配置而得时，这才是一个安全的行为。所以需要某种方法确保RCObjects只以new配置的。这一次我们以公约规范来达成目标。RCObject的设计目的是用来做为有引用计数能力之“实值对象”的基类，而那些“实值对象”应该只被RCPtr智能指针取用。此外，应该只有确知“实值对象”共享性的所谓“应用对象”才能将“实值对象”实体化。描述“实值对象”的那些类不应该被外界看到。在我们的例子中，描述“实值对象”者为 StringValue，我们令它成为“应用对象”String内的私有成员，以限制其用途。只有String才能够产生StringValue对象，所以，确保所有StringValue对象皆以new配置而得，是String类作者的责任。

引用计数的设计并非不需成本，增加了引用计数机制，代码比之前复杂的多。引用计数是个优化技术，其适用前提是：对象常常共享实值。如果这个假设失败，引用计数反而会赔上更多内存，执行更多程序代码。以下是使用引用计数改善效率的最佳时机：相对多数的对象共享相对少量的实值；对象实值的产生或销毁成本很高，或是它们使用很多内存。