29.引用计数

前言

 
引用计数允许多个具有相同值的对象共享这个值的实现，其作用大致有二：

1. 简化跟踪堆中对象。
   在使用引用计数后，对象明确自己拥有自己的资源，当没人使用时自动销毁，可以算是一个简单的垃圾回收。
2. Lazy evaluation
   如果很多对象拥有相同的值，我们不应该存储这个值，而是让所有对象共享其实现。

---

引用计数实例

 
我们首先复习一下Lazy evaluation。

class String {//自定义string类
public:
    String(const char *value = "");
    String& operator=(const String& rhs);
    ...
private:
    char *data;
};
String a, b, c, d, e;
a = b = c = d = e = "Hello";

a到e的具体值形态其实取决于string类的实现。如果不作特殊化处理，每一个string对象均应具有一个值的拷贝，此时有赋值操作符实现如下：

String& String::operator=(const String& rhs){
    if (this == &rhs) return *this;
    delete [] data;
    data = new char[strlen(rhs.data) + 1];
    strcpy(data, rhs.data);
    return *this;
}

显然，在这种实现下，abcde如下所示：

​这无疑是冗余的，我们希望的理想情况是这样：

但这种情况是不现实的，我们至少应该记录当前有多少对象在使用该资源，增设计数器之后的效果如下：

---

实现引用计数

 
仍以String为例。首先我们应当明确需要空间来存储计数值。该空间不可能存在于string内部，因为引用计数的本质是每一个资源一个计数，而非一个对象一个计数，这也表明了资源和引用计数之间存在一种耦合关系。
我们使用一个名为StringValue的struct帮助我们实现上述功能。它不仅仅保存计数器，同时也保存资源。我们将其置于String的private部分(将一个struct内嵌在类的私有区内，能便于这个类的所有成员访问这个结构，但阻止了其它任何人对它的访问)其设计与实现如下所示：

class String {
public:
    ...
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类提供。StringValue的功能主要就是：将一个特殊的值与共享此值的对象的数目联系起来。

---

String的构造

class String {
public:
    String(const char *initValue = "");
    ...
};
String::String(const char *initValue)
: value(new StringValue(initValue)){}

可以看出，String对象是独立构造的，有同样初始化值的对象并不共享数据：

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

产生的数据结构如下所示：
消除这样的副本是可能的：通过让String或StringValue对象跟踪已存在的StringValue对象，并只在不同串时才创建新的对象。

---

String的拷贝

String 的拷贝构造函数效率很高，新生成的String对象与被拷贝的对象共享相同的StringValue对象：

String::String(const String& rhs)
: value(rhs.value){
    ++value->refCount;//需要注意value在heap中，为对象所共有
}

如下代码产生的数据结构如图所示：

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

这必然比值拷贝系列效率要高，在本次拷贝中，我们只不过是拷贝了一个指针并增加了一次引用计数。

---

String的析构

析构函数实现较为容易：只要引用计数值不为0，也就是当前至少存在一个String对象使用这个值，这个值就不可以被销毁：

class String {
public:
    ~String();
    ...
};
String::~String(){
    if (--value->refCount == 0) delete value;//先执行自减
}

---

String的赋值

当用户写下这样的代码：

s1 = s2;

其结果应该是s1和s2指向相同的StringValue对象,对象的引用计数在赋值时被增加。并且，s1原来指向的 StringValue对象的引用计数应该减少，如果s1是拥有原来的值的唯一对象，这个值销毁。上述功能实现如下：

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

---

写时拷贝

 
数组下标操作符[]允许字符串中的单个字符被读或写:

class String {
public:
    const char& operator[](int index) const; // for const Strings
    char& operator[](int index); // for non-const Strings
    ...
};

const成员函数很容易实现，因为它仅仅提供读操作。但non-const则较为繁琐，因为它需要分别处理读和写的情况：

String s;
...
cout << s[3];//read
s[5] = 'x';//write

当我们试图修改一个String对象的值时，必须确保没有修改和它共享StringValue的对象。但我们无法确定operator[]执行的是何种操作（proxy class可以帮助区分读写，详见More Effective C++ 30），所以我们必须假设所有operator[]都在执行写操作。
为了安全地实现non-const operator[]，我们必须确保资源被当前String对象独占。简而言之，当我们返回StringValue对象中的一个字符的引用时，必须确保这个StringValue的引用计数是1：

char& String::operator[](int index){
    if (value->refCount > 1) {
        --value->refCount;//脱离当前资源共享阶段
        value = new StringValue(value->data);//生成一个新资源
    }
    return value->data[index];
}

写时拷贝是这么一种情况：一个对象永远与其他等值对象共享资源，直到它需要修改自身时才迅速拷贝一份资源，你可以把它视为lazy-evacuation的一个应用特例。

---

指针、引用与写时拷贝

 
多数情况下上文所实现的写时拷贝兼具正确性与高效性，但加入了指针后正确性可能会因此失效：

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

其数据结构如下所示：
现增加一条语句：

String s2 = s1;

由于资源共享的原因，当前数据结构如下所示：
如果我们试图通过p去更改s1，就会发现s2也遭到了更改。并非只有指针会造成这种情况，non-conts-reference也是如此。
解决方案不难实现，但我们付出了代价：降低一个值共享于对象间的次数。解决方案原理是：在每个StringValue对象中增加一个标志以指出它是否具备共享性，一开始标志位设置为可共享，一旦有operator[]被调用，标志位翻转为不可共享状态，并且永久保持为不可共享：

class String {
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){
    data = new char[strlen(initValue) + 1];
    strcpy(data, initValue);
}
String::StringValue::~StringValue(){
    delete [] data;
}

在标志位增加后，String的成员函数也需要修改保持配合：

String::String(const String& rhs){//以拷贝构造举例
    if (rhs.value->shareable) {
        value = rhs.value;
        ++value->refCount;
    }
    else {
        value = new StringValue(rhs.value->data);
    }
}

non-const operator[]是唯一一个可以更改标志位的函数：

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

---

引用计数与mixin class

 
不仅仅只有String需要引用计数，但我们不可能为所有需要引用计数的类都添加对应的struct，为了把引用计数功能抽象到与运行环境无关，我们想到了mixin class。

RCObject

首先构建一个基类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::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，因为我们会在构造完毕后把构造它的这个对象的count设为1。赋值操作也很奇怪，它什么都没做，因为我们不可能把计数对象从一个赋予另外一个。就算真的被赋值，它也什么都没变。removeReference函数不仅仅负责减少count值，还负责析构对象，因此这里我们必须要保证对象只被构建于堆中。（More Effective C++ 27）

---

使用实例

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

现在的StringValue什么都不用管，其基类接管了所有行为。

---

引用计数自动化处理

 
RCObject并没有提供自动化操作，一切关于refcount的行为都必须手动完成，比如在String的拷贝构造函数和赋值运算函数中，我们需要调用StringValue的addReference和removeReference函数。我们寄希望于某种操作，能够将大部分与引用计数相关的工作从所有具象类中移出。确实存在这种东西：智能指针。

计数对象所使用的智能指针

以下是计数对象所使用的智能指针模版：

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

该模板允许了我们自定义构造、赋值、析构时执行的操作。当这些事件发生时，智能指针对象可以自动执行正确的操作来处理它们指向的对象（引用计数对象）的refCount字段。其具体实现如下：

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 == nullptr) {
        return;
    }
    if (pointee->isShareable() == false) {//如果计数对象所指向的资源不可共享
        pointee = new T(*pointee);
    }
    pointee->addReference();
}

init存在的问题

当init()函数中发现拷贝构造的rhs处于不可共享状态，它会构建一个新的T型的对象，并且使用T对象的拷贝构造完成了初始化。对于一个String来说，T型对象是StringValue，我们没有对它声明拷贝构造函数，因此编译器选择调用默认版本，只拷贝了StringValue的数据pointer，而没有拷贝所指向的char*字符串。
正确的做法是令T含有正确的值拷贝行为(如深拷贝），以StringValue举例：

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

深copy并非唯一选择，我们应该将具体拷贝实现类型写于文档，告知用户。

智能指针的指向对象

RCPtr假设智能指针永远指向T型对象，但实际上我们知道可以指向T的派生类，为了防止一些奇怪的问题，建议使用虚拷贝构造等手段（More Effective C++ 25）。

智能指针的赋值与析构

//赋值操作
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; }

---

最终实现

 
将之前提到的所有东西合在一起，真正的带有引用计数的String对象数据结构如下：

String类有定义如下：

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 {
public:
    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 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;
};

String class没有声明拷贝构造、赋值运算、析构函数，但这并不是因为操作失误，而是这些函数均可以使用编译器自动生成的版本，真正本质上的上述操作均已在智能指针类及引用计数类中实现。
通过完美的封装，我们在没有更改String接口的同时增加了功能。

---

在现存类上增加引用计数

 
假设我们有一个不可更改的class Widget（不该更改的原因可能是其位于支持库中），如何给它添加引用计数功能？
首先从刚才已实现的思路入手，我们应该会建立一个RCWidget class，内部嵌套有一个struct public继承自RCObject，RCWidget内持有一个智能指针RCPtr指向Count对象：

我们当前自然无法修改Widget内部，但我们可以试图构造一个中间层，然后完成这份任务：
其中，CountHolder是人为构造的class，其内部有一个指针指向了Widget资源，我们用一个智能指针指向CountHolder。

PCIPtr与CountHolder

我们可以认为CountHolder是RCIPtr的实现细节，所以将其嵌套在该类中：

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> // non-constT* 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); 
}

---

RCwidget

有了RCIPtr，RCWidget很容易实现，因为RCWidget的每个函数都是将操作RCIPtr以完成对Widget对象的操作。若有Widget class有实例如下：

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

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

需要注意的是，RcWidget没有拷贝，析构，赋值函数，因为RCIPtr将自动地执行这些行为。