标准库中string的底层实现方式介绍

前言

在之前的学习中，我们都知道 std::string 的一些基本功能和用法了，但它底层到底是如何实现的呢?
其实在std::string的历史中，出现过几种不同的方式，下面我们来一一揭晓。

我们可以从一个简单的问题来探索，一个std::string对象占据的内存空间有多大，即sizeof(std::string)的
值为多大？

如果我们在不同的编译器（VC++, GNU, Clang++）上去测试，可能会发现其值并不相同；即
使是GNU，不同的版本，获取的值也是不同的。

虽然历史上的实现有多种，但基本上有三种方式：

Eager Copy(深拷贝)
COW（Copy-On-Write 写时复制）
SSO(Short String Optimization-短字符串优化)

而每种实现，std::string都包含了下面相同的信息：

字符串的大小
能够容纳的字符数量
字符串内容本身

Eager Copy（深拷贝方式）

最简单的就是深拷贝了。无论什么情况，都是采用拷贝字符串内容的方式解决，这也是我们之前已经实
现过的方式。这种实现方式，在需要对字符串进行频繁复制而又并不改变字符串内容时，效率比较低
下。所以需要对其实现进行优化，之后便出现了本文要介绍的COW的实现方式。

深拷贝方式的空间布局：

写时复制的空间布局：

上图中 strn 的箭头原先也是指向堆空间的第一个“hello world”地址的，在发生了写时复制时 strn 就使用深拷贝的技术从而使得上图箭头指向了第二个 “hello world” 字符串，这样就大大减少了系统的时空开销。

COW(Copy-On-Write)（写时复制方式）

当两个 std::string 发生复制构造或者赋值时，不会复制字符串内容，而是增加一个引用计数，然后字符
串指针进行浅拷贝，其执行效率为O(1)。只有当需要修改其中一个字符串内容时，才执行真正的复制。
其实现的示意图，有下面两种形式：

std::string的数据成员就是:

class string{
private:
	Allocator _allocator;
	size_t size;
	size_t capacity;
	char * pointer;
};

第二种形式为：

std::string的数据成员就只有一个了:

class string{
private:
	char * _pointer;
};

为了实现的简单，在GNU4.8.4的中，采用的是实现2的形式。从上面的实现，我们看到引用计数并没有
与std::string的数据成员放在一起，为什么呢？大家可以思考一下。

当执行复制构造或赋值时，引用计数加1，std::string对象共享字符串内容；当std::string对象销毁时，
并不直接释放字符串所在的空间，而是先将引用计数减1，直到引用计数为0时，则真正释放字符串内容
所在的空间。根据这个思路，大家可以自己动手实现一下。

大家再思考一下，既然涉及到了引用计数，那么在多线程环境下，涉及到修改引用计数的操作，是否是
线程安全的呢？为了解决这个问题，GNU4.8.4的实现中，采用了原子操作。

写时复制技术的一个测试实例

一个测试实例，在Ubuntu的历史版本中（如14.04版本）有过写实复制的实现：

上图中可以看到，s1和s2的地址是一样的，s3是不一样的字符串，所以地址与s1和s2不一样。

当把 s3 的字符串用 s1 的内容进行赋值时，因为并没有更改原来 s1 的字符串内容，所以直接进行了浅拷贝，时空复杂度此时就比深拷贝低，同时还地址相同（ s3 指向了和 s1、s2 相同的地址空间）。

我们将 s3 的字符内容进行修改：

从上图可以看到，当我们将 s3 字符串的第一个字符进行了修改时，此时因为写时复制的机制存在，修改时会进行深拷贝，即申请了新的内存空间，所以内存地址与 s1 和 s2 又不相同了。

写时复制技术实现

#include <iostream>
#include <string.h>
using namespace std;

//引用计数的存储位置应该在内存的哪个地方？
//1、引用计数位于栈上 error
//2、全局静态区域 error
//3、只能放在堆区，并且与数据放在一起，最好在数据的前面
//这样做就不会因为数据的变化（字符串长度的变化）而一直让引用计数的位置发生偏移
class String{
	public:
		//无参构造
		String()
		//这里申请了五个字节然后从数组名开始向后偏移四个字节
		//是为了直接略过引用计数的内容来到真正存储数据的位置
		: _pstr(new char[5]()+4)//1个存 '\0'，另外4个存引用计数
		{
			cout << "String()" << endl;
			//这里是为了将数组的前四个字节的内容初始化为1
			//减4是为了让数组从头开始，转成int*是为了直接操作数组的前四个字节
			*(int*)(_pstr-4) = 1;
		}
		//有参构造
		String (const char* pstr)
		//strlen(pstr)+5的原因是要预留引用计数与'\0'的位置
		//数组名+4的原因和上面无参构造处相同
		:_pstr(new char[strlen(pstr)+5]() + 4)
		{
			cout << "String(const char*)" << endl;
			strcpy(_pstr,pstr);
			*(int*)(_pstr-4) = 1;
		}
		//拷贝构造
		//String s2(s1);
		String(const String& rhs)
		:_pstr(rhs._pstr) //浅拷贝
		{
			cout << "String(const String&)" << endl;
			//让引用计数器自增
			++*(int*)(_pstr-4);
		}
		//赋值运算符重载
		//s3 = s1;
		String& operator=(const String& rhs){
			//1、防止自复制问题
			if(this != &rhs){
				//2、如果不是自己复制自己，那么释放左操作数
				//这里是减少引用计数
				--*(int*)(_pstr-4);
				//判断引用计数是否为0了
				if(0 == *(int*)(_pstr-4)){
					delete[] (_pstr-4);
				}
				//3、浅拷贝
				_pstr = rhs._pstr;
				++*(int*)(_pstr-4);
			}
			//4、返回 *this
			return *this;
		}
		//重载下标访问运算符
		//s3[0] = 'H'
		char& operator[](size_t idx){
			if(idx < size()){
				if(getRefCount() > 1){
					char* ptmp = new char[size()+5]() + 4;
					strcpy(ptmp,_pstr);
					--*(int*)(_pstr-4);

					_pstr = ptmp;
					*(int*)(_pstr - 4) = 1;
				}
				return _pstr[idx];
			}else{
				static char charnull = '\0';
				return charnull;
			}
		}
		//析构函数
		~String(){
			cout << "~String()" << endl;
			--*(int*)(_pstr-4);
			//判断引用计数是否为0了
			if(0 == *(int*)(_pstr-4)){
				delete[] (_pstr-4);
			}
		}
	public:
		const char* c_str() const{
			return _pstr;
		}
		int getRefCount() const{
			return *(int*)(_pstr - 4);
		}
		
	private:
		size_t size() const {
			return strlen(_pstr);
		}

		friend ostream& operator<<(ostream& os,const String& rhs);

	private:
		char* _pstr;
};

ostream& operator<<(ostream& os,const String& rhs){
	if(rhs._pstr){
		os << rhs._pstr;
	}
	return os;
}

void test(){
	String s1("hello");
	String s2(s1);
	cout << "s1=" << s1 << endl;
	cout << "s2=" << s2 << endl;
	cout << "s1.getRefCount()=" << s1.getRefCount() << endl;
	cout << "s2.getRefCount()=" << s2.getRefCount() << endl;
	printf("s1 address : %p\n",s1.c_str());
	printf("s2 address : %p\n",s2.c_str());

	cout << endl;

	String s3("world");
	
	cout << "s3=" << s3 << endl;
	cout << "s3.getRefCount()=" << s3.getRefCount() << endl;
	printf("s3 address : %p\n",s3.c_str());

	cout << endl << "使用s3 = s1进行赋值操作" << endl;
	s3 = s1;
	
	cout << "s1=" << s1 << endl;
	cout << "s2=" << s2 << endl;
	cout << "s3=" << s3 << endl;
	cout << "s1.getRefCount()=" << s1.getRefCount() << endl;
	cout << "s2.getRefCount()=" << s2.getRefCount() << endl;
	cout << "s3.getRefCount()=" << s3.getRefCount() << endl;
	printf("s1 address : %p\n",s1.c_str());
	printf("s2 address : %p\n",s2.c_str());
	printf("s3 address : %p\n",s3.c_str());

	cout << endl << "对s3[0]进行写操作" << endl;
	s3[0] = 'H';
	cout << "s1=" << s1 << endl;
	cout << "s2=" << s2 << endl;
	cout << "s3=" << s3 << endl;
	cout << "s1.getRefCount()=" << s1.getRefCount() << endl;
	cout << "s2.getRefCount()=" << s2.getRefCount() << endl;
	cout << "s3.getRefCount()=" << s3.getRefCount() << endl;
	printf("s1 address : %p\n",s1.c_str());
	printf("s2 address : %p\n",s2.c_str());
	printf("s3 address : %p\n",s3.c_str());
}

int main(){

	test();
	return 0;
}

运行截图：

SSO（Short String Optimization）（短字符串优化）

目前，在VC++、GNU5.x.x以上、Clang++上，std::string实现均采用了SSO的实现。

通常来说，一个程序里用到的字符串大部分都很短小，而在64位机器上，一个char*指针就占用了8个字
节，所以SSO就出现了，其核心思想是：发生拷贝时要复制一个指针，对小字符串来说，为啥不直接复
制整个字符串呢，说不定还没有复制一个指针的代价大。其实现示意图如下：

std::string的数据成员就是：

class string
{
	union Buffer
	{
		char * _pointer;
		char _local[16];
	};
	Buffer _buffer;
	size_t _size;
	size_t _capacity;
};

当字符串的长度小于等于15个字节时，buffer直接存放整个字符串；当字符串大于15个字节时，buffer
存放的就是一个指针，指向堆空间的区域。这样做的好处是，当字符串较小时，直接拷贝字符串，放在
string内部，不用获取堆空间，开销小。

短字符串优化技术的一个测试实例

从图中可以看出，因为 pInt 的指向与字符串 s3 是相似的，且上面提过当字符串大于15个字节时，其存放是一个指向堆空间区域的指针（pInt是使用的new关键字申请的空间，众所周知new申请的是堆空间的内容）；当字符串的长度小于等于15个字节时，buffer直接存放整个字符串（从上图可以看到&pInt的值和s1、s2的地址都是位于栈空间上的），所以可以从侧面印证现在系统的 string 的底层实现是 SSO 的说法。

最佳策略总结

以上三种方式，都不能解决所有可能遇到的字符串的情况，各有所长，又各有缺陷。综合考虑所有情况
之后，facebook开源的folly库中，实现了一个fbstring, 它根据字符串的不同长度使用不同的拷贝策略，
最终每个fbstring对象占据的空间大小都是24字节。

1. 很短的（0~22）字符串用SSO，23字节表示字符串（包括’\0’）,1字节表示长度
2. 中等长度的（23~255）字符串用eager copy，8字节字符串指针，8字节size，8字节capacity.
3. 很长的(大于255)字符串用COW, 8字节指针（字符串和引用计数），8字节size，8字节capacity.

线程安全考虑

两个线程同时对同一个字符串进行操作的话, 是不可能线程安全的, 出于性能考虑, C++并没有为string实
现线程安全, 毕竟不是所有程序都要用到多线程。

但是两个线程同时对独立的两个string操作时, 必须是安全的. COW技术实现这一点是通过原子的对引用
计数进行+1或-1操作。

CPU的原子操作虽然比mutex锁好多了, 但是仍然会带来性能损失, 原因如下:

阻止了CPU的乱性执行.
两个CPU对同一个地址进行原子操作, 会导致cache失效, 从而重新从内存中读数据.
系统通常会lock住比目标地址更大的一片区域，影响逻辑上不相关的地址访问

这也是在多核时代，各大编译器厂商都选择了SS0实现的原因吧。