C++（9）——引用计数实现写时拷贝（包含String类的实现）

在之前的学习中，
我们谈到了字符串的深拷贝与浅拷贝，在浅拷贝中，由于多个对象共用同一块内存空间，导致同一块空间被释放多次而出现问题，那能否保证：当多个对象共享一块空间时，该空间最终只释放一次呢？

这就是我们接下来要谈的问题：
使用浅拷贝不浪费内存空间却容易发生内存泄漏问题，使用深拷贝不会发生内存泄漏但是会不断开辟新的空间，内存利用率低。因此结合深浅拷贝的特点产生了写时拷贝。

一、什么是写时拷贝？

当你在读取一片空间时，系统并不会为你开辟一个一模一样的空间给你；只有在当你真正修改的时候，才会开辟一片空间给你。

二、怎么实现写时拷贝呢？

1. 使用引用计数来实现。所以我们在分配空间时需要多分配4个字节，来记录有多少个指针指向这个空间。
2. 有新的指针指向这篇空间时，那么引用计数就加一；当有一个指针要释放该空间时，那么引用计数就减一。
3. 当有指针要修改这片空间时，则为该指针重新分配自己的空间，原空间的引用计数减一，新空间的引用计数加一。

自己实现的String类

引用计数

对于我们之前所写的String类，在拷贝构造时，深拷贝方式使得使得各个对象都指向了独立的堆区空间，造成了内存和资源的浪费。因此，我们引入引用计数：
其原理如下：原理：，当多个对象共享一块资源时，要保证该资源只释放一次， 只需记录有多少个对象在使用该资源即可，每减少(增加)一个对象使用， 给该计数减一(加一)，当最后一个对象不使用时，该对象负责将资源释放掉即可 。

class String
{
protected:
	struct StrNode
	{
		int ref;//对象的引用计数
		int len;//字符串长度
		int size;//字符串占据的空间大小
		char data[];//或char data[0]
	};
private:
	StrNode* pstr;
	String(StrNode *p):pstr(p){}
public:
	String(const char* p = NULL) :pstr(NULL)
	{
		if (p != NULL)
		{
			int len = strlen(p);
			pstr = (StrNode*)malloc(sizeof(StrNode) + len * 2 + 1);
			pstr->ref = 1;
			pstr->len = len;
			pstr->size = len * 2;
			strcpy(pstr->data, p);
		}
	}
	String(const String& s) :pstr(NULL)
	{
		if (s.pstr != NULL)
		{
			pstr = s.pstr;
			pstr->ref += 1;
		}
	}
	String & operator=(const String &s)
	{
		if(this == &s)return *this;
		
		if(this->pstr != NULL && --this->pstr->ref == 0) 
		{
			free(this->pstr);
		}

		this->pstr = s.pstr;
		if(this->pstr != NULL)
		{
			this->pstr->ref += 1;
		}
		return *this;
	}
	~String()
	{
		if (pstr != NULL && --pstr->ref == 0)
		{
			free(pstr);
		}
		pstr = NULL;
	}
	char operator[](const int index) const//这里不以引用返回也是为了减少内存访问次数
	{
		if(pstr == NULL) exit(1);
		assert(index >= 0 && index <= pstr->len-1);//hello len-5
		return pstr->data[index];
	}
	void modify(const int index,const char ch)
	{
		if(pstr == NULL) exit(1);
		assert(index >= 0 && index <= pstr->len-1); 

		if(pstr->ref > 1)//写时拷贝
		{
			int total = sizeof(StrNode) + pstr->size + 1;
			StrNode *newnode = (StrNode *)malloc(total);
			memmove(newnode,pstr->data,total);
			newnode->ref = 1;
			pstr->ref -= 1;
			pstr = newnode;
		} 

		pstr->data[index] = ch;
	}
	// const char & operator[](const int index) const
	// { 
	// 	//return (*this)[index];
	// 	//此时不能够成功调用，因为此方法是常方法
	// 	return (*const_cast<String*>(this))[index];//去除this指针的常性，这样写可读性较强
	// 	//等同于return (*(String*)this)[index]
	// }
	 
	String(String &&s):pstr(NULL)
	{
		pstr = s.pstr;
		s.pstr = NULL;
	}
	String &operator=(String &&s)
	{
		if(this == &s)
		{
			return *this;
		}
		if(pstr != NULL && --pstr->ref == 0)
		{
			free(pstr);
		}
		pstr = s.pstr;
		s.pstr = NULL;
		return *this;
	}
	String operator+(const String &s)const
	{
		if (pstr == NULL && s.pstr == NULL)
		 {
			 return String();
		 }
		 else if (pstr != NULL && s.pstr == NULL)
		 {
			 return *this;
		 }
		 else if (pstr == NULL && s.pstr != NULL)
		 {
			 return s;
		 }
		 else
		 {
			 int total = (pstr->len + s.pstr->len)*2;
			 StrNode* newsp = (StrNode*)malloc(sizeof(StrNode) + total + 1);
			 strcpy(newsp->data, pstr->data);
			 strcat(newsp->data, s.pstr->data);
			 newsp->ref = 1;
			 newsp->len = pstr->len + s.pstr->len ;
			 newsp->size = total;
			 return String(newsp);
		 }
	}
	String & operator+=(const String & s)
	{
		if(this->pstr != NULL && s.pstr != NULL)
		{
			if(this->pstr->ref > 1)//此时考虑建立一个副本，然后重新+=，原来的字符串引用计数减一
			{
				//同时建立副本时还需要考虑加进来的字符串的大小，空间一定要足够
				int total = pstr->len + s.pstr->len;
				this->pstr->ref -= 1;
				char *tmp = this->pstr->data;
				this->pstr = (StrNode*)malloc(sizeof(StrNode)+total*2);
				strcpy(this->pstr->data,tmp);
				strcat(this->pstr->data,s.pstr->data);
				this->pstr->ref = 1;
				this->pstr->len = total;
				this->pstr->size = total * 2;
			}
		}
		else if (this->pstr == NULL && s.pstr != NULL)
		 {
			 this->pstr = s.pstr;
			 this->pstr->ref += 1;
		 }
		//只有一个对象独占时，空间不足时扩容，否则无需对空间大小进行操作
		else 
		{
			int total = this->pstr->len + s.pstr->len;
			//空间不足
			if(this->pstr->size < total)
			{
				this->pstr = (StrNode*)realloc(this->pstr,sizeof(StrNode)+total*2+1);
				this->pstr->size = total * 2;
			}
				strcat(this->pstr->data,s.pstr->data);//此处s1 += s1时会引发异常
				this->pstr->len = total;
		}
		return *this;
	}
	ostream & operator<<(ostream & out) const
	{
		if(pstr != NULL)
		{
			out<<pstr->data;
		}
		return out;
	}
};
ostream & operator<<(ostream & out,const String &s)
{
	s<<out;
	return out;
}

这里的data[]是一个柔性数组，也是C99、C11标准中给出的新的设计方法，数组的大小声明为0，或者不给出大小，称之为柔性数组，**注意，全局数组和局部数组不能这样定义，**这种定义只在结构体或者类中可以定义。

比如一个struct node{int a;int b;char data[];}
在主函数申请空间时，我们可以这样写struct node *sp = (struct node *)malloc(sizeof(struct node) + 50),一共58个字节的空间，前八个为a,sizeof计算的结果就是8，因为data作为标识符不占据空间，后面50个字节动态分配给了data。

在如下的代码块中，内存分布是这样的：
String s1(“hello”);
String s2(s1);
String s3(s1);
String s4(s1);

之后，我们再来写赋值语句，需要考虑如下的几个问题：

• 自赋值判断
• 当前字符串无人引用是要自动销毁

String & operator=(const String &s)
	{
		if(this == &s)return *this;
		
		if(this->pstr != NULL && --this->pstr->ref == 0) 
		{
			free(this->pstr);
		}

		this->pstr = s.pstr;
		if(this->pstr != NULL)
		{
			this->pstr->ref += 1;
		}
		return *this;
	}

下一个问题：在修改字符串的内容时，如果有多个对象指向同一个字符串，那么在修改字符串的某一位时，另外的对象也要修改，这里考虑到共享性的问题，所以需要写时拷贝

char & operator[](const int index) 
	{
		if(pstr == NULL) exit(1);
		assert(index > 0 && index <= pstr->len-1);//hello
												//01234  len-5
		if(pstr->ref > 1)
		{
			int total = sizeof(StrNode) + pstr->size + 1;
			StrNode *newnode = (StrNode *)malloc(total);
			memmove(newnode,pstr->data,total);
			newnode->ref = 1;
			pstr->ref -= 1;
			pstr = newnode;
		}
		return pstr->data[index];
	}
	const char & operator[](const int index) const
	{
		return (*this)[index];
	}
int main()
{
	String s1("hello");
	String(s1);
	s1[0] = 'H';
	cout<<s2<<endl;
}