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

2024-01-02 21:29:54

前言

在之前的学习中,我们都知道 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实现的原因吧。

文章来源:https://blog.csdn.net/qq_53324833/article/details/135343916
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。