STEP BY STEP

引用计数

发表于 分类于 ， 阅读次数： Valine：
本文字数： 28k 阅读时长 ≈ 25 分钟

引用计数说得直接点就是不同的对象内部共享同样的内容(内存)，同时对象能够自己跟踪自己被引用多少次，能够在没有被继续引用的时候删除自己，保证了没有内存泄漏的出现。看起来貌似java里面的垃圾回收机制了。很多事物都有两面性，引用计数也不例外。看起来牛逼的东西必然有它的弱点，总有一些地方它比不过最原始的东西。

书上说了两种极端的情况，一种是大量的对象共享少数的相同的内容，一种是同样的内容只被共享少数几次，也就是基本没多少共享。显然前者是利用引用计数的典型情况。一般来说，下面的一些条件有利于引用计数的使用。比如说，目标对象消耗大量的资源;资源的分配和释放很昂贵;高度共享:由于使用复制构造函数和赋值操作符,所以引用计数可能比较大;引用的创建和清除相对低廉。如果程序中出现大量的对象创建和释放的操作，使用引用计数的效果反而会更差，而出现大量的对象的赋值操作则适合于引用计数的使用。

一般来说主要有两种实现方式。一种是你能够修改目标类的代码的情况，一种是你不能够得到目标类代码的情况。另外，还有给这些实现加上线程同步的情况。我分别实现了相关的代码，你也可以从提高c++性能的编程计数上面找到相关的代码。

情况1的类设计图如下，

从类设计图中可以看到要实现一个引用计数需要额外的三个类。RCObject是存储引用计数变量的基类，RCPtr是一个智能指针类，RCBigInt类里面包含一个RCPtr成员，该类相当于BigInt的代理类，和BigInt向外提供同样的接口。BigInt的实现稍微复杂了点，你也可以用任何简单的类替换它。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <iostream>
using namespace std;

class RCObject
{
public:
    void addReference()
    {
        ++refCount;
    }
    void removeReference()
    {
        if(--refCount == 0) delete this;
    }
    void markUnshareable()
    {
        shareable = false;
    }
    bool isShareable() const
    {
        return shareable;
    }
    bool isShared() const
    {
        return refCount > 1;
    }

private:
    int refCount;
    bool shareable;
};

class BigInt : public RCObject
{
    friend BigInt operator+(const BigInt, const BigInt);
public:
    BigInt(const char*);
    BigInt(unsigned u = 0);
    BigInt(const BigInt);
    BigInt operator=(const BigInt);
    BigInt operator+=(const BigInt);
    ~BigInt()
    {
        delete [] digits;
    }

    char* getDigits() const
    {
        return digits;
    }
    unsigned getNdigits() const
    {
        return ndigits;
    }

private:
    char* digits;
    unsigned ndigits;
    unsigned size;
    BigInt(const BigInt, const BigInt);
    char fetch(unsigned i) const
    {
        return i < ndigits ? digits[i] : 0;
    }
};

BigInt::BigInt(const char* s)
{
    if (s[0] == '\0')
    {
        s = "0";
    }

    size = ndigits = strlen(s);
    digits = new char[size];
    for (unsigned i = 0; i < ndigits; ++i)
    {
        digits[i] = s[ndigits - 1 - i] - '0';
    }
}

BigInt::BigInt(unsigned u)
{
    unsigned v = u;

    for (ndigits = 1; v /= 10; ++ndigits);
    digits = new char[size = ndigits];
    for (unsigned i = 0; i < ndigits; ++i)
    {
        digits[i] = u % 10;
        u /= 10;
    }
}

BigInt::BigInt(const BigInt copyFrom)
{
    size = ndigits = copyFrom.ndigits;
    digits = new char[size];
    for (unsigned i = 0; i < ndigits; ++i)
    {
        digits[i] = copyFrom.digits[i];
    }
}

BigInt BigInt::operator+=(const BigInt rhs)
{
    unsigned max = 1 + (rhs.ndigits > ndigits ? rhs.ndigits : ndigits);

    if (size < max)
    {
        char* d = new char[size = max];
        for (unsigned i = 0; i < ndigits; ++i)
        {
            d[i] = digits[i];
        }
        delete [] digits;
        d = digits;
    }

    while (ndigits < max)
    {
        digits[ndigits++] = 0;
    }

    for (unsigned i = 0; i < ndigits; ++i)
    {
        digits[i] += rhs.fetch(i);
        if (digits[i] >= 10)
        {
            digits[i] -= 10;
            digits[i + 1]++;
        }
    }

    if (digits[ndigits - 1] == 0)
    {
        --ndigits;
    }

    return *this;
}

BigInt::BigInt(const BigInt left, const BigInt right)
{
    size = 1 + (left.ndigits > right.ndigits ? left.ndigits : right.ndigits);
    digits = new char[size];
    ndigits = left.ndigits;
    for (unsigned i = 0; i < ndigits; ++i)
    {
        digits[i] = left.digits[i];
    }
    *this += right;
}

inline BigInt operator+(const BigInt left, const BigInt right)
{
    return BigInt(left, right);
}

BigInt BigInt::operator=(const BigInt rhs)
{
    if (this == rhs) return *this;

    ndigits = rhs.ndigits;
    if (ndigits > size)
    {
        delete [] this;
        digits = new char[size = ndigits];
    }

    for (unsigned i = 0; i < ndigits; ++i)
    {
        digits[i] = rhs.digits[i];
    }

    return *this;
}

ostream operator<<(ostream os, BigInt bi)
{
    char c;
    const char* d = bi.getDigits();

    for (int i = bi.getNdigits() - 1; i >= 0; --i)
    {
        c = d[i] + '0';
        os << c;
    }
    os << endl;

    return os;
}

template <typename T> class RCPtr
{
public:
    RCPtr(T* realPtr = NULL) : pointee(realPtr) { Init(); }
    RCPtr(const RCPtr rhs) : pointee(rhs.pointee) { Init(); }
    ~RCPtr() { if (pointee) pointee->removeReference(); }
    T* operator->() const { return pointee; }
    T operator*() const { return * pointee; }
    RCPtr operator=(const RCPtr rhs);

private:
    T* pointee;
    void Init();
};

template <typename T> void RCPtr<T>::Init()
{
    if (pointee == 0) return;

    if (pointee->isShareable() == false)
    {
        pointee = new T(*pointee);
    }
    pointee->addReference();
}

template <typename T> RCPtr<T> RCPtr<T>::operator=(const RCPtr rhs)
{
    if (pointee != rhs.pointee)
    {
        if (pointee) pointee->removeReference();
        pointee = rhs.pointee;
        Init();
    }

    return *this;
}

class RCBigInt
{
    friend RCBigInt operator+(const RCBigInt, const RCBigInt);
public:
    RCBigInt(const char* p) : value(new BigInt(p)) {}
    RCBigInt(unsigned u = 0) : value(new BigInt(u)) {}
    RCBigInt(const BigInt bi) : value(new BigInt(bi)) {}

private:
    RCPtr<BigInt> value;
};

inline RCBigInt operator+(const RCBigInt left, const RCBigInt right)
{
    return RCBigInt(*(left.value) + *(right.value));
}

void TestBigIntCreate(int n)
{
    printf("TestBigIntCreate:%d\n", n);
    clock_t beg = clock();
    for (int i = 0; i < n; ++i)
    {
        BigInt a = i;
        BigInt b = i + 1;
        BigInt c = i + 2;
        BigInt d = i + 3;
    }
    clock_t end = clock();
    printf("use %f second(s).\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
}

void TestRCBigIntCreate(int n)
{
    printf("TestRCBigIntCreate:%d\n", n);
    clock_t beg = clock();
    for (int i = 0; i < n; ++i)
    {
        RCBigInt a = i;
        RCBigInt b = i + 1;
        RCBigInt c = i + 2;
        RCBigInt d = i + 3;
    }
    clock_t end = clock();
    printf("use %f second(s).\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
}

void TestBigIntAssign(int n)
{
    printf("TestBigIntAssign:%d\n", n);
    BigInt a, b, c, d;
    clock_t beg = clock();
    for (int i = 0; i < n; ++i)
    {
        a = b = c = d;
    }
    clock_t end = clock();
    printf("use %f second(s).\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
}

void TestRCBigIntAssign(int n)
{
    printf("TestRCBigIntAssign:%d\n", n);
    RCBigInt a, b, c, d;
    clock_t beg = clock();
    for (int i = 0; i < n; ++i)
    {
        a = b = c = d;
    }
    clock_t end = clock();
    printf("use %f second(s).\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
}

int main()
{
    const int NUM = 1000000;

    TestBigIntCreate(NUM);
    TestRCBigIntCreate(NUM);
    TestBigIntAssign(NUM);
    TestRCBigIntAssign(NUM);

    return 0;
}

运行结果:

情况2的类设计图如下所示，

从图中可以看到，由于无法修改BigInt的实现，引入了一个新类CounterHolder作为引用计数的中间类。该类继承自RCObject，智能指针类RCIPtr包含一个CounterHolder的指针，而CounterHolder里面才包含一个BigInt的指针。
这就相当于多了一次间接操作，因此在RCIBigInt的创建和删除操作中会增加时间，这可以从运行结果中可以看到。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <iostream>
using namespace std;

class RCObject
{
public:
    void addReference()
    {
        ++refCount;
    }
    void removeReference()
    {
        if(--refCount == 0) delete this;
    }
    void markUnshareable()
    {
        shareable = false;
    }
    bool isShareable() const
    {
        return shareable;
    }
    bool isShared() const
    {
        return refCount > 1;
    }

private:
    int refCount;
    bool shareable;
};

class BigInt
{
    friend BigInt operator+(const BigInt, const BigInt);
public:
    BigInt(const char*);
    BigInt(unsigned u = 0);
    BigInt(const BigInt);
    BigInt operator=(const BigInt);
    BigInt operator+=(const BigInt);
    ~BigInt()
    {
        delete [] digits;
    }

    char* getDigits() const
    {
        return digits;
    }
    unsigned getNdigits() const
    {
        return ndigits;
    }

private:
    char* digits;
    unsigned ndigits;
    unsigned size;
    BigInt(const BigInt, const BigInt);
    char fetch(unsigned i) const
    {
        return i < ndigits ? digits[i] : 0;
    }
};

BigInt::BigInt(const char* s)
{
    if (s[0] == '\0')
    {
        s = "0";
    }

    size = ndigits = strlen(s);
    digits = new char[size];
    for (unsigned i = 0; i < ndigits; ++i)
    {
        digits[i] = s[ndigits - 1 - i] - '0';
    }
}

BigInt::BigInt(unsigned u)
{
    unsigned v = u;

    for (ndigits = 1; v /= 10; ++ndigits);
    digits = new char[size = ndigits];
    for (unsigned i = 0; i < ndigits; ++i)
    {
        digits[i] = u % 10;
        u /= 10;
    }
}

BigInt::BigInt(const BigInt copyFrom)
{
    size = ndigits = copyFrom.ndigits;
    digits = new char[size];
    for (unsigned i = 0; i < ndigits; ++i)
    {
        digits[i] = copyFrom.digits[i];
    }
}

BigInt BigInt::operator+=(const BigInt rhs)
{
    unsigned max = 1 + (rhs.ndigits > ndigits ? rhs.ndigits : ndigits);

    if (size < max)
    {
        char* d = new char[size = max];
        for (unsigned i = 0; i < ndigits; ++i)
        {
            d[i] = digits[i];
        }
        delete [] digits;
        d = digits;
    }

    while (ndigits < max)
    {
        digits[ndigits++] = 0;
    }

    for (unsigned i = 0; i < ndigits; ++i)
    {
        digits[i] += rhs.fetch(i);
        if (digits[i] >= 10)
        {
            digits[i] -= 10;
            digits[i + 1]++;
        }
    }

    if (digits[ndigits - 1] == 0)
    {
        --ndigits;
    }

    return *this;
}

BigInt::BigInt(const BigInt left, const BigInt right)
{
    size = 1 + (left.ndigits > right.ndigits ? left.ndigits : right.ndigits);
    digits = new char[size];
    ndigits = left.ndigits;
    for (unsigned i = 0; i < ndigits; ++i)
    {
        digits[i] = left.digits[i];
    }
    *this += right;
}

inline BigInt operator+(const BigInt left, const BigInt right)
{
    return BigInt(left, right);
}

BigInt BigInt::operator=(const BigInt rhs)
{
    if (this == rhs) return *this;

    ndigits = rhs.ndigits;
    if (ndigits > size)
    {
        delete [] this;
        digits = new char[size = ndigits];
    }

    for (unsigned i = 0; i < ndigits; ++i)
    {
        digits[i] = rhs.digits[i];
    }

    return *this;
}

ostream operator<<(ostream os, BigInt bi)
{
    char c;
    const char* d = bi.getDigits();

    for (int i = bi.getNdigits() - 1; i >= 0; --i)
    {
        c = d[i] + '0';
        os << c;
    }
    os << endl;

    return os;
}

template <typename T> class RCIPtr
{
public:
    RCIPtr(T* realPtr = NULL) : counter(new CountHolder)
    {
        counter->pointee = realPtr;
        Init();
    }
    RCIPtr(const RCIPtr rhs) : counter(rhs.counter) { Init(); }
    ~RCIPtr() { if (counter) counter->removeReference(); }
    T* operator->() const { return counter->pointee; }
    T operator*() const { return *(counter->pointee); }
    RCIPtr operator=(const RCIPtr rhs);

private:
    struct CountHolder : public RCObject
    {
        ~CountHolder() { delete pointee; }
        T* pointee;
    };

    CountHolder* counter;
    void Init();
};

template <typename T> void RCIPtr<T>::Init()
{
    if (counter == 0) return;

    if (counter->isShareable() == false)
    {
        counter = new CountHolder;
        counter->pointee = new T(*counter->pointee);

    }
    counter->addReference();
}

template <typename T> RCIPtr<T> RCIPtr<T>::operator=(const RCIPtr rhs)
{
    if (counter != rhs.counter)
    {
        if (counter) counter->removeReference();
        counter = rhs.counter;
        Init();
    }

    return *this;
}

class RCBigInt
{
    friend RCBigInt operator+(const RCBigInt, const RCBigInt);
public:
    RCBigInt(const char* p) : value(new BigInt(p)) {}
    RCBigInt(unsigned u = 0) : value(new BigInt(u)) {}
    RCBigInt(const BigInt bi) : value(new BigInt(bi)) {}

private:
    RCIPtr<BigInt> value;
};

inline RCBigInt operator+(const RCBigInt left, const RCBigInt right)
{
    return RCBigInt(*(left.value) + *(right.value));
}

void TestBigIntCreate(int n)
{
    printf("TestBigIntCreate:%d\n", n);
    clock_t beg = clock();
    for (int i = 0; i < n; ++i)
    {
        BigInt a = i;
        BigInt b = i + 1;
        BigInt c = i + 2;
        BigInt d = i + 3;
    }
    clock_t end = clock();
    printf("use %f second(s).\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
}

void TestRCBigIntCreate(int n)
{
    printf("TestRCBigIntCreate:%d\n", n);
    clock_t beg = clock();
    for (int i = 0; i < n; ++i)
    {
        RCBigInt a = i;
        RCBigInt b = i + 1;
        RCBigInt c = i + 2;
        RCBigInt d = i + 3;
    }
    clock_t end = clock();
    printf("use %f second(s).\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
}

void TestBigIntAssign(int n)
{
    printf("TestBigIntAssign:%d\n", n);
    BigInt a, b, c, d;
    clock_t beg = clock();
    for (int i = 0; i < n; ++i)
    {
        a = b = c = d;
    }
    clock_t end = clock();
    printf("use %f second(s).\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
}

void TestRCBigIntAssign(int n)
{
    printf("TestRCBigIntAssign:%d\n", n);
    RCBigInt a, b, c, d;
    clock_t beg = clock();
    for (int i = 0; i < n; ++i)
    {
        a = b = c = d;
    }
    clock_t end = clock();
    printf("use %f second(s).\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
}

int main()
{
    const int NUM = 1000000;

    TestBigIntCreate(NUM);
    TestRCBigIntCreate(NUM);
    TestBigIntAssign(NUM);
    TestRCBigIntAssign(NUM);

    return 0;
}

运行结果：

最后给出的是多线程版本的代码，在Windows下可以用临界区或者互斥体实现。互斥体实现的版本比较慢，但是临界区的版本为什么在gcc的release版本中运行出现内存错误了，而debug版本中没有问题，在vc6下运行也没有问题。

临界区版本代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <iostream>
#include <windows.h>
using namespace std;

class RCObject
{
public:
    void addReference()
    {
        ++refCount;
    }
    void removeReference()
    {
        if(--refCount == 0) delete this;
    }
    void markUnshareable()
    {
        shareable = false;
    }
    bool isShareable() const
    {
        return shareable;
    }
    bool isShared() const
    {
        return refCount > 1;
    }

private:
    int refCount;
    bool shareable;
};

class BigInt
{
    friend BigInt operator+(const BigInt, const BigInt);
public:
    BigInt(const char*);
    BigInt(unsigned u = 0);
    BigInt(const BigInt);
    BigInt operator=(const BigInt);
    BigInt operator+=(const BigInt);
    ~BigInt()
    {
        delete [] digits;
    }

    char* getDigits() const
    {
        return digits;
    }
    unsigned getNdigits() const
    {
        return ndigits;
    }

private:
    char* digits;
    unsigned ndigits;
    unsigned size;
    BigInt(const BigInt, const BigInt);
    char fetch(unsigned i) const
    {
        return i < ndigits ? digits[i] : 0;
    }
};

BigInt::BigInt(const char* s)
{
    if (s[0] == '\0')
    {
        s = "0";
    }

    size = ndigits = strlen(s);
    digits = new char[size];
    for (unsigned i = 0; i < ndigits; ++i)
    {
        digits[i] = s[ndigits - 1 - i] - '0';
    }
}

BigInt::BigInt(unsigned u)
{
    unsigned v = u;

    for (ndigits = 1; v /= 10; ++ndigits);
    digits = new char[size = ndigits];
    for (unsigned i = 0; i < ndigits; ++i)
    {
        digits[i] = u % 10;
        u /= 10;
    }
}

BigInt::BigInt(const BigInt copyFrom)
{
    size = ndigits = copyFrom.ndigits;
    digits = new char[size];
    for (unsigned i = 0; i < ndigits; ++i)
    {
        digits[i] = copyFrom.digits[i];
    }
}

BigInt BigInt::operator+=(const BigInt rhs)
{
    unsigned max = 1 + (rhs.ndigits > ndigits ? rhs.ndigits : ndigits);

    if (size < max)
    {
        char* d = new char[size = max];
        for (unsigned i = 0; i < ndigits; ++i)
        {
            d[i] = digits[i];
        }
        delete [] digits;
        d = digits;
    }

    while (ndigits < max)
    {
        digits[ndigits++] = 0;
    }

    for (unsigned i = 0; i < ndigits; ++i)
    {
        digits[i] += rhs.fetch(i);
        if (digits[i] >= 10)
        {
            digits[i] -= 10;
            digits[i + 1]++;
        }
    }

    if (digits[ndigits - 1] == 0)
    {
        --ndigits;
    }

    return *this;
}

BigInt::BigInt(const BigInt left, const BigInt right)
{
    size = 1 + (left.ndigits > right.ndigits ? left.ndigits : right.ndigits);
    digits = new char[size];
    ndigits = left.ndigits;
    for (unsigned i = 0; i < ndigits; ++i)
    {
        digits[i] = left.digits[i];
    }
    *this += right;
}

inline BigInt operator+(const BigInt left, const BigInt right)
{
    return BigInt(left, right);
}

BigInt BigInt::operator=(const BigInt rhs)
{
    if (this == rhs) return *this;

    ndigits = rhs.ndigits;
    if (ndigits > size)
    {
        delete [] this;
        digits = new char[size = ndigits];
    }

    for (unsigned i = 0; i < ndigits; ++i)
    {
        digits[i] = rhs.digits[i];
    }

    return *this;
}

ostream operator<<(ostream os, BigInt bi)
{
    char c;
    const char* d = bi.getDigits();

    for (int i = bi.getNdigits() - 1; i >= 0; --i)
    {
        c = d[i] + '0';
        os << c;
    }
    os << endl;

    return os;
}

class CriticalSectionLock
{
public:
    CriticalSectionLock()
    {
        InitializeCriticalSection(csMyCriticalSection);
    }
    ~CriticalSectionLock()
    {
        DeleteCriticalSection(csMyCriticalSection);
    }
    void lock()
    {
        EnterCriticalSection(csMyCriticalSection);
    }
    void unlock()
    {
        LeaveCriticalSection(csMyCriticalSection);
    }
private:
    CRITICAL_SECTION csMyCriticalSection;
};

template <typename T, typename LOCK> class RCIPtr
{
public:
    RCIPtr(T* realPtr = NULL) : counter(new CountHolder)
    {
        counter->pointee = realPtr;
        Init();
    }
    RCIPtr(const RCIPtr rhs) : counter(rhs.counter)
    {
        if (rhs.counter) rhs.counter->key.lock();
        Init();
        if (rhs.counter) rhs.counter->key.unlock();
    }
    ~RCIPtr()
    {
        if (counter)
        {
            counter->key.lock();
            counter->removeReference();
            counter->key.unlock();
        }
    }
    T* operator->() const { return counter->pointee; }
    T operator*() const { return *(counter->pointee); }
    RCIPtr operator=(const RCIPtr rhs);

private:
    struct CountHolder : public RCObject
    {
        ~CountHolder() { delete pointee; }
        T* pointee;
        LOCK key;
    };

    CountHolder* counter;
    void Init();
};

template <typename T, typename LOCK> void RCIPtr<T, LOCK>::Init()
{
    if (counter == 0) return;

    if (counter->isShareable() == false)
    {
        counter = new CountHolder;
        counter->pointee = new T(*counter->pointee);

    }
    counter->addReference();
}

template <typename T, typename LOCK>
RCIPtr<T, LOCK> RCIPtr<T, LOCK>::operator=(const RCIPtr rhs)
{
    if (counter != rhs.counter)
    {
        if (counter)
        {
            counter->key.lock();
            counter->removeReference();
            counter->key.unlock();
        }
        counter = rhs.counter;
        if (rhs.counter) rhs.counter->key.lock();
        Init();
        if (rhs.counter) rhs.counter->key.unlock();
    }

    return *this;
}

class RCBigInt
{
    friend RCBigInt operator+(const RCBigInt, const RCBigInt);
public:
    RCBigInt(const char* p) : value(new BigInt(p)) {}
    RCBigInt(unsigned u = 0) : value(new BigInt(u)) {}
    RCBigInt(const BigInt bi) : value(new BigInt(bi)) {}

private:
    RCIPtr<BigInt, CriticalSectionLock> value;
};

inline RCBigInt operator+(const RCBigInt left, const RCBigInt right)
{
    return RCBigInt(*(left.value) + *(right.value));
}

void TestBigIntCreate(int n)
{
    printf("TestBigIntCreate:%d\n", n);
    clock_t beg = clock();
    for (int i = 0; i < n; ++i)
    {
        BigInt a = i;
        BigInt b = i + 1;
        BigInt c = i + 2;
        BigInt d = i + 3;
    }
    clock_t end = clock();
    printf("use %f second(s).\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
}

void TestRCBigIntCreate(int n)
{
    printf("TestRCBigIntCreate:%d\n", n);
    clock_t beg = clock();
    for (int i = 0; i < n; ++i)
    {
        RCBigInt a = i;
        RCBigInt b = i + 1;
        RCBigInt c = i + 2;
        RCBigInt d = i + 3;
    }
    clock_t end = clock();
    printf("use %f second(s).\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
}

void TestBigIntAssign(int n)
{
    printf("TestBigIntAssign:%d\n", n);
    BigInt a, b, c, d;
    clock_t beg = clock();
    for (int i = 0; i < n; ++i)
    {
        a = b = c = d;
    }
    clock_t end = clock();
    printf("use %f second(s).\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
}

void TestRCBigIntAssign(int n)
{
    printf("TestRCBigIntAssign:%d\n", n);
    RCBigInt a, b, c, d;
    clock_t beg = clock();
    for (int i = 0; i < n; ++i)
    {
        a = b = c = d;
    }
    clock_t end = clock();
    printf("use %f second(s).\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
}

int main()
{
    const int NUM = 1000000;

    TestBigIntCreate(NUM);
    TestRCBigIntCreate(NUM);
    TestBigIntAssign(NUM);
    TestRCBigIntAssign(NUM);

    return 0;
}

在vc6下的运行结果,

从结果中可以看出RCIBigInt的赋值操作情况在性能上已经没有多少优势了，在vc6下反而更慢，这主要是因为线程同步操作的原因。

互斥体版本代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <iostream>
#include <windows.h>
using namespace std;

class RCObject
{
public:
    void addReference()
    {
        ++refCount;
    }
    void removeReference()
    {
        if(--refCount == 0) delete this;
    }
    void markUnshareable()
    {
        shareable = false;
    }
    bool isShareable() const
    {
        return shareable;
    }
    bool isShared() const
    {
        return refCount > 1;
    }

private:
    int refCount;
    bool shareable;
};

class BigInt
{
    friend BigInt operator+(const BigInt, const BigInt);
public:
    BigInt(const char*);
    BigInt(unsigned u = 0);
    BigInt(const BigInt);
    BigInt operator=(const BigInt);
    BigInt operator+=(const BigInt);
    ~BigInt()
    {
        delete [] digits;
    }

    char* getDigits() const
    {
        return digits;
    }
    unsigned getNdigits() const
    {
        return ndigits;
    }

private:
    char* digits;
    unsigned ndigits;
    unsigned size;
    BigInt(const BigInt, const BigInt);
    char fetch(unsigned i) const
    {
        return i < ndigits ? digits[i] : 0;
    }
};

BigInt::BigInt(const char* s)
{
    if (s[0] == '\0')
    {
        s = "0";
    }

    size = ndigits = strlen(s);
    digits = new char[size];
    for (unsigned i = 0; i < ndigits; ++i)
    {
        digits[i] = s[ndigits - 1 - i] - '0';
    }
}

BigInt::BigInt(unsigned u)
{
    unsigned v = u;

    for (ndigits = 1; v /= 10; ++ndigits);
    digits = new char[size = ndigits];
    for (unsigned i = 0; i < ndigits; ++i)
    {
        digits[i] = u % 10;
        u /= 10;
    }
}

BigInt::BigInt(const BigInt copyFrom)
{
    size = ndigits = copyFrom.ndigits;
    digits = new char[size];
    for (unsigned i = 0; i < ndigits; ++i)
    {
        digits[i] = copyFrom.digits[i];
    }
}

BigInt BigInt::operator+=(const BigInt rhs)
{
    unsigned max = 1 + (rhs.ndigits > ndigits ? rhs.ndigits : ndigits);

    if (size < max)
    {
        char* d = new char[size = max];
        for (unsigned i = 0; i < ndigits; ++i)
        {
            d[i] = digits[i];
        }
        delete [] digits;
        d = digits;
    }

    while (ndigits < max)
    {
        digits[ndigits++] = 0;
    }

    for (unsigned i = 0; i < ndigits; ++i)
    {
        digits[i] += rhs.fetch(i);
        if (digits[i] >= 10)
        {
            digits[i] -= 10;
            digits[i + 1]++;
        }
    }

    if (digits[ndigits - 1] == 0)
    {
        --ndigits;
    }

    return *this;
}

BigInt::BigInt(const BigInt left, const BigInt right)
{
    size = 1 + (left.ndigits > right.ndigits ? left.ndigits : right.ndigits);
    digits = new char[size];
    ndigits = left.ndigits;
    for (unsigned i = 0; i < ndigits; ++i)
    {
        digits[i] = left.digits[i];
    }
    *this += right;
}

inline BigInt operator+(const BigInt left, const BigInt right)
{
    return BigInt(left, right);
}

BigInt BigInt::operator=(const BigInt rhs)
{
    if (this == rhs) return *this;

    ndigits = rhs.ndigits;
    if (ndigits > size)
    {
        delete [] this;
        digits = new char[size = ndigits];
    }

    for (unsigned i = 0; i < ndigits; ++i)
    {
        digits[i] = rhs.digits[i];
    }

    return *this;
}

ostream operator<<(ostream os, BigInt bi)
{
    char c;
    const char* d = bi.getDigits();

    for (int i = bi.getNdigits() - 1; i >= 0; --i)
    {
        c = d[i] + '0';
        os << c;
    }
    os << endl;

    return os;
}

class MutexLock
{
public:
    MutexLock()
    {
        hMutex = CreateMutex(NULL, FALSE, NULL);
    }
    ~MutexLock()
    {
        CloseHandle(hMutex);
    }
    void lock()
    {
        WaitForSingleObject(hMutex, INFINITE);
    }
    void unlock()
    {
        ReleaseMutex(hMutex);
    }
private:
    HANDLE hMutex;
};

template <typename T, typename LOCK> class RCIPtr
{
public:
    RCIPtr(T* realPtr = NULL) : counter(new CountHolder)
    {
        counter->pointee = realPtr;
        Init();
    }
    RCIPtr(const RCIPtr rhs) : counter(rhs.counter)
    {
        if (rhs.counter) rhs.counter->key.lock();
        Init();
        if (rhs.counter) rhs.counter->key.unlock();
    }
    ~RCIPtr()
    {
        if (counter)
        {
            counter->key.lock();
            counter->removeReference();
            counter->key.unlock();
        }
    }
    T* operator->() const { return counter->pointee; }
    T operator*() const { return *(counter->pointee); }
    RCIPtr operator=(const RCIPtr rhs);

private:
    struct CountHolder : public RCObject
    {
        ~CountHolder() { delete pointee; }
        T* pointee;
        LOCK key;
    };

    CountHolder* counter;
    void Init();
};

template <typename T, typename LOCK> void RCIPtr<T, LOCK>::Init()
{
    if (counter == 0) return;

    if (counter->isShareable() == false)
    {
        counter = new CountHolder;
        counter->pointee = new T(*counter->pointee);

    }
    counter->addReference();
}

template <typename T, typename LOCK>
RCIPtr<T, LOCK> RCIPtr<T, LOCK>::operator=(const RCIPtr rhs)
{
    if (counter != rhs.counter)
    {
        if (counter)
        {
            counter->key.lock();
            counter->removeReference();
            counter->key.unlock();
        }
        counter = rhs.counter;
        if (rhs.counter) rhs.counter->key.lock();
        Init();
        if (rhs.counter) rhs.counter->key.unlock();
    }

    return *this;
}

class RCBigInt
{
    friend RCBigInt operator+(const RCBigInt, const RCBigInt);
public:
    RCBigInt(const char* p) : value(new BigInt(p)) {}
    RCBigInt(unsigned u = 0) : value(new BigInt(u)) {}
    RCBigInt(const BigInt bi) : value(new BigInt(bi)) {}

private:
    RCIPtr<BigInt, MutexLock> value;
};

inline RCBigInt operator+(const RCBigInt left, const RCBigInt right)
{
    return RCBigInt(*(left.value) + *(right.value));
}

void TestBigIntCreate(int n)
{
    printf("TestBigIntCreate:%d\n", n);
    clock_t beg = clock();
    for (int i = 0; i < n; ++i)
    {
        BigInt a = i;
        BigInt b = i + 1;
        BigInt c = i + 2;
        BigInt d = i + 3;
    }
    clock_t end = clock();
    printf("use %f second(s).\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
}

void TestRCBigIntCreate(int n)
{
    printf("TestRCBigIntCreate:%d\n", n);
    clock_t beg = clock();
    for (int i = 0; i < n; ++i)
    {
        RCBigInt a = i;
        RCBigInt b = i + 1;
        RCBigInt c = i + 2;
        RCBigInt d = i + 3;
    }
    clock_t end = clock();
    printf("use %f second(s).\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
}

void TestBigIntAssign(int n)
{
    printf("TestBigIntAssign:%d\n", n);
    BigInt a, b, c, d;
    clock_t beg = clock();
    for (int i = 0; i < n; ++i)
    {
        a = b = c = d;
    }
    clock_t end = clock();
    printf("use %f second(s).\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
}

void TestRCBigIntAssign(int n)
{
    printf("TestRCBigIntAssign:%d\n", n);
    RCBigInt a, b, c, d;
    clock_t beg = clock();
    for (int i = 0; i < n; ++i)
    {
        a = b = c = d;
    }
    clock_t end = clock();
    printf("use %f second(s).\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
}

int main()
{
    const int NUM = 1000000;

    TestBigIntCreate(NUM);
    TestRCBigIntCreate(NUM);
    TestBigIntAssign(NUM);
    TestRCBigIntAssign(NUM);

    return 0;
}

在codeblocks配gcc的环境下的运行结果，

从图里面还是能看到，在Windows下用互斥体同步确实比较慢。