分类： C/C++
2009-08-26 15:26:15
引用计数是这样一个技巧，它允许多个有相同值的对象共享这个值的实现。这个技巧有两个常用动机。第一个是简化跟踪堆中的对象的过程。一旦一个对象通过调用new被分配出来，最要紧的就是记录谁拥有这个对象，因为其所有者－－并且只有其所有者－－负责对这个对象调用delete。但是，所有权可以被从一个对象传递到另外一个对象（例如通过传递指针型参数），所以跟踪一个对象的所有权是很困难的。象auto_ptr（见Item M9）这样的类可以帮助我们，但经验显示大部分程序还不能正确地得到这样的类。引用计数可以免除跟踪对象所有权的担子，因为当使用引用计数后，对象自己拥有自己。当没人再使用它时，它自己自动销毁自己。因此，引用计数是个简单的垃圾回收体系。
第二个动机是由于一个简单的常识。如果很多对象有相同的值，将这个值存储多次是很无聊的。更好的办法是让所有的对象共享这个值的实现。这么做不但节省内存，而且可以使得程序运行更快，因为不需要构造和析构这个值的拷贝。
和大部分看似简单的主意一样，这个动机也有一个曲折而有趣的细节。在其中必须有一个正确实现的引用计数体系。在开始钻研细节前，让我们掌握一些基础。一个好主意是先着眼于我们将可能如何遇到多个对象有相同的值。这儿有一个：
class String { // the standard string type may
public: // employ the techniques in this
// Item, but that is not required
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都有相同的值“Hello”。其值的形态取决于String类是怎么实现的，但通常的实现是每个string对象有一个这个值的拷贝。例如，String的赋值操作可能实现为这样：
String& String::operator=(const String& rhs)
{
if (this == &rhs) return *this; // see Item E17
delete [] data;
data = new char[strlen(rhs.data) + 1];
strcpy(data, rhs.data);
return *this; // see Item E15
}
根据这个实现，我们可以推测，这5个对象及其值如下：
其冗余是显然的。在一个理想的世界中，我们希望将上图改为这样：
这里，只存储了一个“Hello”的拷贝，所有具有此值的String对象共享其实现。
实际世界中，实现这个主意是不可能的，因为我们需要跟踪多少对象共享同一个值。如果上面的对象a被赋了“Hello”以外的另外一个值，我们不能摧毁值“Hello”，因为还有四个对象需要它。另一方面，如果只有一个对象有“Hello”这个值，当其超出生存空间时，没有对象具有这个值了，我们必须销毁这个值以避免资源泄漏。
保存当前共享/引用同一个值的对象数目的需求意味着我们的那张图必须增加一个计数值（引用计数）：
（有些人将其叫作use count，但我不是其中之一。C++有很多它自己的特性，最后需要的一个是专业名词的派别之争。）
l 实现引用计数
创建一个带引用计数的String类并不困难，但需要注意一些细节，所以我们将略述这样一个类的大部分常用成员函数的实现。然而，在开始之前，认识到“我们需要一个地方来存储这个计数值”是很重要的。这个地方不能在String对象内部，因为需要的是每个String值一个引用计数值，而不是每个String对象一个引用计数。这意味着String值和引用计数间是一一对应的关系，所以我们将创建一个类来保存引用计数及其跟踪的值。我们叫这个类StringValue，又因为它唯一的用处就是帮助我们实现String类，所以我们将它嵌套在String类的私有区内。另外，为了便于Sting的所有成员函数读取其数据区，我们将StringValue申明为struct。需要知道的是：将一个struct内嵌在类的私有区内，能便于这个类的所有成员访问这个结构，但阻止了其它任何人对它的访问（当然，除了友元）。
基本设计是这样的：
class String {
public:
... // the usual String member
// functions go here
private:
struct StringValue { ... }; // holds a reference count
// and a string value
StringValue *value; // value of this String
};
我们可以给这个类起个其它名字（如RCString）以强调它使用了引用计数，但类的实现不该是类的用户必须关心的东西，用户只关心类的公有接口。而我们带引用计数的String版本与不带引用计数的版本，其接口完全相同，所以为什么要用类的名字来把问题搅混呢？真的需要吗？所以我们没有这么做。
这是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;
}
这是其所有的一切，很清楚，这不足以实现带引用计数的String类。一则，没有拷贝构造函数和赋值运算（见Item E11）；二则，没有提供对refCount的操作。别担心，少掉的功能将由String类提供。StringValue的主要目的是提供一个空间将一个特别的值和共享此值的对象的数目联系起来。StringValue给了我们这个，这就足够了。
我们现在开始处理String的成员函数。首先是构造函数：
class String {
public:
String(const char *initValue = "");
String(const String& rhs);
...
};
第一个构造函数被实现得尽可能简单。我们用传入的char *字符串创建了一个新的StringValue对象，并将我们正在构造的string对象指向这个新生成的StringValue：
String::String(const char *initValue)
: value(new StringValue(initValue))
{}
这样的用户代码：
String s("More Effective C++");
生成的数据结构是这样的：
String对象是独立构造的，有同样初始化值的对象并不共享数据，所以，这样的用户代码：
String s1("More Effective C++");
String s2("More Effective C++");
产生这样的数据结构：
消除这样的副本是可能的：通过让String（或StringValue）对象跟踪已存在的StringValue对象，并只在是不同串时才创建新的对象。但这样的改进有些偏离目标。于是，我将它作为习题留给读者。
String的拷贝构造函数很高效：新生成的String对象与被拷贝的对象共享相同的StringValue对象：
String::String(const String& rhs)
: value(rhs.value)
{
++value->refCount;
}
这样的代码：
String s1("More Effective C++");
String s2 = s1;
产生这样的数据结构：
这肯定比通常的（不带引用计数的）string类高效，因为不需要为新生成的string值分配内存、释放内存以及将内容拷贝入这块内存。现在，我们只不过是拷贝了一个指针并增加了一次引用计数。
String类的析构函数同样容易实现，因为大部分情况下它不需要做任何事情。只要引用计数值不是0，也就是至少有一个String对象使用这个值，这个值就不可以被销毁。只有当唯一的使用者被析构了（也就是引用计数在进入函数前已经为1时），String的析构函数才摧毁StringValue对象：
class String {
public:
~String();
...
};
String::~String()
{
if (--value->refCount == 0) delete value;
}
和没有引用计数的版本比较一下效率。那样的函数总调用delete，当然会有一个相当程度的运行时间的代价。现在提供的String对象们实际上有时具有相同的值，上面的这个实现在此时只需要做一下减少引用计数并与0进行比较。
如果在这个问题上引用计数没有向外界表现出来，你就根本不需要花注意力。
这就是String的构造和析构，我们现在转到赋值操作：
class String {
public:
String& operator=(const String& rhs);
...
};
当用户写下这样的代码：
s1 = s2; // s1 and s2 are both String objects
其结果应该是s1和s2指向相同的StringValue对象。对象的引用计数应该在赋值时被增加。并且，s1原来指向的StringValue对象的引用计数应该减少，因为s1不再具有这个值了。如果s1是拥有原来的值的唯一对象，这个值应该被销毁。在C++中，其实现看起来是这样的：
String& String::operator=(const String& rhs)
{
if (value == rhs.value) { // do nothing if the values
return *this; // are already the same; this
} // subsumes the usual test of
// this against &rhs (see Item E17)
if (--value->refCount == 0) { // destroy *this's value if
delete value; // no one else is using it
}
value = rhs.value; // have *this share rhs's
++value->refCount; // value
return *this;
}
l 写时拷贝
围绕我们的带引用计数的String类，考虑一下数组下标操作（[]），它允许字符串中的单个字符被读或写：
class String {
public:
const char&
operator[](int index) const; // for const Strings
char& operator[](int index); // for non-const Strings
...
};
这个函数的const版本的实现很容易，因为它是一个只读操作，String对象的值不受影响：
const char& String::operator[](int index) const
{
return value->data[index];
}
（这个函数实现了C++传统意义上的下标索引（根本不会说“不”）。如果你想加上参数检查，这是非常容易的。）
非const的operator[]版本就是一个完全不同的故事了。它可能是被调用了来读一个字符，也可能被调用了来写一个字符：
String s;
...
cout << s[3]; // this is a read
s[5] = 'x'; // this is a write
我们希望以不同的方式处理读和写。简单的读操作，可以用与const的operator[]类似的方式实现，而写操作必须用完全不同的方式来实现。
当我们修改一个String对象的值时，必须小心防止修改了与它共享相同StringValue对象的其它String对象的值。不幸的是，C++编译器没有办法告诉我们一个特定的operator[]是用作读的还是写的，所以我们必须保守地假设“所有”调用非const operator[]的行为都是为了写操作。（Proxy类可以帮助我们区分读还是写，见Item M30。）
为了安全地实现非const的operator[]，我们必须确保没有其它String对象在共享这个可能被修改的StringValue对象。简而言之，当我们返回StringValue对象中的一个字符的引用时，必须确保这个StringValue的引用计数是1。这儿是我们的实现：
char& String::operator[](int index)
{
// if we're sharing a value with other String objects,
// break off a separate copy of the value for ourselves
if (value->refCount > 1) {
--value->refCount; // decrement current value's
// refCount, because we won't
// be using that value any more
value = // make a copy of the
new StringValue(value->data); // value for ourselves
}
// return a reference to a character inside our
// unshared StringValue object
return value->data[index];
}
这个“与其它对象共享一个值直到写操作时才拥有自己的拷贝”的想法在计算机科学中已经有了悠久而著名的历史了，尤其是在操作系统中：进程共享内存页直到它们想在自己的页拷贝中修改数据为止。这个技巧如此常用，以至于有一个名字：写时拷贝。它是提高效率的一个更通用方法－－Lazy原则－－的特例。
l 指针、引用与写时拷贝
大部分情况下，写时拷贝可以同时保证效率和正确性。只有一个挥之不去的问题。看一下这样的代码：
String s1 = "Hello";
char *p = &s1[1];
数据结构是这样的：
现在看增加一条语句：
String s2 = s1;
String的拷贝构造函数使得s2共享s1的StringValue对象，所以数据结构将是：
下面这样的语句将有不受欢迎的结果：
*p = 'x'; // modifies both s1 and s2!
String的拷贝构造函数没有办法检测这样的问题，因为它不知道指向s1拥有的StringValue对象的指针的存在。并且，这个问题不局限于指针：它同样存在于有人保存了一个String的非const operator[]的返回值的引用的情况下。
至少有三种方法来应付这个问题。第一个是忽略它，假装它不存在。这是实现带引用计数的String类的类库中令人痛苦的常见问题。如果你有带引用计数的String类，试一下上面的例子，看你是否很痛苦。即使你不能确定你操作的是否是带引用计数的String类，也无论如何应该试一下这个例子。由于封装，你可能使用了一个这样的类型而不自知。
不是所以的实现都忽略这个问题。稍微好些的方法是明确说明它的存在。通常是将它写入文档，或多或少地说明“别这么做。如果你这么做了，结果为未定义。”无论你以哪种方式这么做了（有意地或无意地），并抱怨其结果时，他们辩解道：“好了，我们告诉过你别这么做的。”这样的实现通常很方便，但它们在可用性方面留下了太多的期望。
第三个方法是排除这个问题。它不难实现，但它将降低一个值共享于对象间的次数。它的本质是这样的：在每个StringValue对象中增加一个标志以指出它是否为可共享的。在最初（对象可共享时）将标志打开，在非const的operator[]被调用时将它关闭。一旦标志被设为false，它将永远保持在这个状态（注10）。
这是增加了共享标志的修改版本：
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) // add this
{
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);
}
}
所有其它的成员函数也都必须以类似的方法检查这个共享标志。非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];
}
