std::string的底层实现 （详解）

目录

std::string的底层实现*

写时复制原理探究

CowString代码初步实现

短字符串优化（SSO）

最佳策略

---

std::string的底层实现*

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

我们可以从一个简单的问题来探索，一个std::string对象占据的内存空间有多大，即sizeof(std::string)的值为多大？如果我们在不同的编译器（VC++, GCC, Clang++）上去测试，可能会发现其值并不相同；即使是GCC，不同的版本，获取的值也是不同的。

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

• Eager Copy(深拷贝)

• COW（Copy-On-Write 写时复制）

• SSO(Short String Optimization 短字符串优化)

  std::string的底层实现是一个高频考点，虽然目前std::string是根据SSO的思想实现的，但是我们最好能够掌握其发展过程中的不同设计思想，在回答时会是一个非常精彩的加分项。

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

  //如果string的实现直接用深拷贝
  String str1("hello,world");
  String str2 = str1;

  如上，str2保存的字符串内容与str1完全相同，但是根据深拷贝的思想，一定要重新申请空间、复制内容，这样效率较低、开销较大。

写时复制原理探究

Q1: 当字符串对象进行复制控制时，可以优化为指向同一个堆空间的字符串，接下来的问题就是何时回收堆空间的字符串内容呢？

引用计数 refcount当字符串对象进行复制操作时，引用计数+1；当字符串对象被销毁时，引用计数-1；只有当引用计数减为0时，才真正回收堆空间上字符串

string str2("hello,wuhan");
string str3 = str2;

补充：如果是如下创建对象，能不能共用空间，存放"hello"

—— 单独创建对象没有优化的空间，每一个string对象需要一片独立的空间存放自己的字符串

string s1("hello");
//在创建s2之前可能有很多String对象
//不可能遍历这些对象
//看看哪个对象保存的内容是hello
//s2再去共用空间 —— 只有确保内容一致时，才能共用空间 —— 复制或赋值时
string s2("hello");

Q2: 引用计数应该放到哪里？

—— 需要改变str1的数据成员，不合理。

—— 静态数据成员被该类所有对象共享，但此时str1和str2的引用计数应该都是2，但是str3的引用计数应该是1.

方案三可行，还可以优化一下

按常规的思路，需要使用两次new表达式（字符串、引用计数）；可以优化成只用一次new表达式，因为申请堆空间的行为一定会涉及系统调用，程序员要尽量少使用系统调用，提高程序的执行效率。

—— 优化方向：把引用计数和字符串内容保存到一起。

引用计数保存到字符串内容的前面，方便访问。

除了复制操作，赋值操作也可以确定两个string对象保存的字符串内容是相同的，也可以复用空间，引用计数随之改变。

但相比复制操作，还需要考虑string对象原本用来保存字符串的堆空间是否需要回收。

（1）原本空间的引用计数-1，引用计数减到0，才真正回收堆空间

（2）让自己的指针指向新的空间，并将新空间的引用计数+1

CowString代码初步实现

根据写时复制的思想来模拟字符串对象的实现，这是一个非常有难度的任务（源码级），理解了COW的思想后可以尝试实现一下

重点关注一下赋值运算符函数，赋值运算符函数此时也需要考虑要不要回收空间了。

下标访问运算符函数也不能沿用以前的做法，直接返回对应位置的字符

这就是写时复制的意义。

在我们建立了基本的写时复制字符串类的框架后，发现了一个遗留的问题。

如果str1和str3共享一片空间存放字符串内容。如果进行读操作，那么直接进行就可以了，不用进行复制，也不用改变引用计数；如果进行写操作，那么应该让str1重新申请一片空间去进行修改，不应该改变str3的内容。

cout << str1[0] << endl; //读操作 str1[0] = 'H'; //写操作 cout << str3[0] << endl;//发现str3的内容也被改变了

我们首先会想到运算符重载的方式去解决。但是str1[0]返回值是一个char类型变量。

读操作 cout << char字符 << endl;

写操作 char字符 = char字符；

无论是输出流运算符还是赋值运算符，操作数中没有自定义类型对象，无法重载。而CowString的下标访问运算符的操作数是CowString对象和size_t类型的下标，也没办法判断取出来的内容接下来要进行读操作还是写操作。

—— 思路：创建一个CowString类的内部类，让CowString的operator[]函数返回是这个新类型的对象，然后在这个新类型中对<<和=进行重载，让这两个运算符能够处理新类型对象，从而分开了处理逻辑。

因为CharProxy定义在CowString的私有区域，为了让输出流运算符能够处理CharProxy对象，需要对此operator<<函数进行两次友元声明（内外都需要）。

对于读操作，还可以给CharProxy类定义类型转换函数来进行处理 —— 稍稍实现了一定的简化。

总结：当运算符需要处理自定义类型对象时，先看一看这个自定义类型有没有相应的运算符重载函数，如果有，那么这个运算符就可以处理这个自定义类型对象；

如果没有运算符重载，就无法直接处理，需要进行转换。先看看这个自定义类型中有没有类型转换函数，转换成一个该运算符可以直接处理的类型的数据。如果没有类型转换函数，会再看看有没有隐式转换的途径。（一般，大多数情况谨慎使用隐式转换）

下面为测试代码，可以自行测试

#define _CRT_SECURE_NO_WARNINGS 1;
#include <iostream>
#include <cstring>
using std::cout;
using std::endl;
using std::ostream;class CowString
{class CharProxy {public://先明白charproxy的创造条件就是str1[0] 就是一个str1 和一个下标//就是将引用数据成员绑定到str1本体，本体会一直存在直到对象销毁CharProxy(CowString& self, size_t idx):_self(self), _idx(idx){}//为读操作重载一个输出流运算符函数  //friend ostream& operator<<(ostream& os, const CharProxy& rhs);// 输出流运算符要多次声明友元，既要声明内部类又要声明外部类，// 还有什么方式可以解决这个问题呢// 使用类型转化函数，将自定义类型转化为一个cout输出的类型//将自定义类型转化为char就可以输出了operator char(){cout << "operator char() 被调用" << endl;return _self._pstr[_idx];}//为写操作重载一个赋值运算符函数char& operator=(char ch);private:CowString& _self;size_t _idx;};
public://构造函数CowString();//函数声明的时候可以不给变量名，但是后面定义的时候就要给CowString(const char*);CowString& operator=(const CowString&);~CowString();CowString(const CowString&);//这里不能是charproxy的引用因为，返回的charproxy对象是在这个函数中创建的函数结束生命周期结束，引用本体死亡//传参数也就是一个this指针和一个下标CharProxy operator[](size_t idx);//char& operator[](size_t _idx);const char* c_str() const {return _pstr;}size_t size() const {//strlen()传递的参数是指针类型和cout输出流的原理相同return (int)strlen(_pstr);}int use_count(){return *(int*)(_pstr - KRefCountLength);}friendostream& operator<<(ostream& os, const CowString& rhs);//friend //ostream& operator<<(ostream& os, const CharProxy& rhs);private://初始化引用计数的数据void initRefCount(){//先指向第4个字节向前移动初始化引用计数的数据*(int*)(_pstr - KRefCountLength) = 1;}void increaseRefCount(){++* (int*)(_pstr - KRefCountLength);}void decreaseRefCount() {--* (int*)(_pstr - KRefCountLength);}char* malloc(const char* pstr = nullptr){if (pstr){return new char[1 + KRefCountLength + strlen(pstr)]() + KRefCountLength;}else//没有传参数，就是无参构造{return new char[KRefCountLength + 1]() + KRefCountLength;}}void release(){decreaseRefCount();if (use_count() == 0){delete[](_pstr - KRefCountLength);_pstr = nullptr;cout << ">>delete heap" << endl;}}
private:char* _pstr;//静态常量数据成员static const int KRefCountLength = 4;};ostream& operator<<(ostream& os, const CowString& rhs)
{if (rhs._pstr){//当输出流对象拿到一个char*指针之后他会一直向后寻找直到'\0'结束os << rhs._pstr;}else{os << endl;}return os;
}CowString::CowString()
//new 返回的是申请空间的首地址，但是我不能是指针指向首地址，因为前面是用来记录引用计数的，所以返回的位置向后偏移4:_pstr(malloc())
{cout << "CowString()" << endl;initRefCount();
}//有参构造
CowString::CowString(const char* pstr):_pstr(malloc(pstr))
{//字符串拷贝strcpy(_pstr, pstr);//初始化计数initRefCount();
}
CowString:: ~CowString()
{release();
}
CowString::CowString(const CowString& rhs):_pstr(rhs._pstr) //浅拷贝
{increaseRefCount();
}CowString& CowString::operator=(const CowString& rhs)
{if (this != &rhs)//判断自复制{release();//尝试回收堆空间_pstr = rhs._pstr;//浅拷贝改变指针指向increaseRefCount();//数值++}return *this;
}
//str1[0]需要返回一个charproxy对象
//只有利用str1对象和下标0来进行创建
// 所以charproxy的构造函数写成如下形式//str1[0] = 'H'需要给charproxy定义一个赋值运算符函数
//cout << str1[0] << endl;  需要为charproxy重载一个输出流运算符函数// charproxy类需要设计一个cowstring引用向上绑定str1对象
//以及一个size_t的数据成员保存下标值
CowString::CharProxy CowString::operator[](size_t idx) {//外部类不能访问内部类，要把函数声明为友元return CharProxy(*this, idx);
}//还是会有this指针
char& CowString ::CharProxy::operator=(char ch)
{if (_idx < _self.size()){//如果引用计数大于1，就进行深拷贝申请一块新的空间if (_self.use_count() > 1){//原本空间引用计数减1_self.decreaseRefCount();//深拷贝char* tmp = _self.malloc(_self._pstr);strcpy(tmp, _self._pstr);//改变指向_self._pstr = tmp;//初始化新空间的引用计数_self.increaseRefCount();} //进行写操作_self._pstr[_idx] = ch;//没有直接返回下标引用return _self._pstr[_idx];}else//越界访问 {cout << "out of range" << endl;//不能返回局部变量，不能返回右值，所以创建了一个nullcharstatic char nullchar = '\0';return nullchar;}
}
//不会修改数据成员的以友元的形式进行重载，这个函数要在两个类中都进行友元函数的声明因为在charproxy中声明允许访问
//charproxy的私有的数据成员，而charproxy是cowstring的私有类（私有数据类型），所以在外部类中也要声明友元
//ostream& operator<<(ostream& os, const CowString::CharProxy& rhs)
//{
//	if (rhs._idx < rhs._self.size())
//	{
//		os << rhs._self._pstr[rhs._idx];
//	}
//	else
//	{
//		cout << "out of range" << endl;
//	}
//	return os;
//}//读操作的处理逻辑
//一种方法通过下标访问进行读操作但是都会对数据进行更改
//char& CowString::operator[](size_t idx)
//{
//	if (idx < size())
//	{
//		return _pstr[idx];
//	}
//	else//越界访问 
//	{
//		cout << "out of range" << endl;
//		//不能返回局部变量，不能返回右值，所以创建了一个nullchar
//		static char nullchar = '\0';
//		return nullchar;
//	}
//}//写操作的处理逻辑
//一种方法通过下标访问进行写操作，进行读操作也会进行深拷贝所以会造成效率下降
//char& CowString::operator[](size_t idx)
//{
//	if (idx < size())
//	{
//		//如果引用计数大于1，就进行深拷贝申请一块新的空间
//		if (use_count() > 1)
//		{
//			//原本空间引用计数减1
//			decreaseRefCount();
//			//深拷贝
//			char* tmp = malloc(_pstr);
//			strcpy(tmp, _pstr);
//			//改变指向
//			_pstr = tmp;
//			//初始化新空间的引用计数
//			increaseRefCount();
//		}
//		//没有直接返回下标引用
//		return _pstr[idx];
//	}
//	else//越界访问 
//	{
//		cout << "out of range" << endl;
//		//不能返回局部变量，不能返回右值，所以创建了一个nullchar
//		static char nullchar = '\0';
//		return nullchar;
//	}
//}void test0()
{CowString str1;CowString str2 = str1;cout << "str1:" << str1 << endl;cout << "str2:" << str2 << endl;cout << str1.use_count() << endl;cout << str2.use_count() << endl;CowString str3 = "hello";CowString str4 = str3;cout << "str3:" << str3 << endl;cout << "str4:" << str4 << endl;cout << str3.use_count() << endl;cout << str4.use_count() << endl;cout << endl;str2 = str3;cout << "str1:" << str1 << endl;cout << "str2:" << str2 << endl;cout << "str3:" << str3 << endl;cout << "str4:" << str4 << endl;cout << str1.use_count() << endl;cout << str2.use_count() << endl;cout << str3.use_count() << endl;cout << str4.use_count() << endl;
}
void test1()
{CowString str1 = "hello";CowString str2 = str1;cout << str1[0] << endl;cout << "str1:" << str1 << endl;cout << "str2:" << str2 << endl;cout << str1.use_count() << endl;cout << str2.use_count() << endl;str2[0] = 'H';cout << "str1:" << str1 << endl;cout << "str2:" << str2 << endl;cout << str1.use_count() << endl;cout << str2.use_count() << endl;
}
int main()
{//test0();test1();return 0;
}

短字符串优化（SSO）

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

union表示共用体，允许在同一内存空间中存储不同类型的数据。共用体的所有成员共享一块内存，但是每次只能使用一个成员。

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

我发现在堆上的时候vs和vscode的编译器的规则好像不太一样，在栈上的规则是一样的，容量就是15，但是在堆上好像规则不太一样

先展示vs的环境：

再展示vscode的环境（G++）：

可以看出g++编译器在堆上的空间的时候，他的空间就是用多少开多少，而vs环境下，他的开空间的规则就和vector动态数组的规则好像当空间满了之后会自动扩容。

短字符串优化的简单实现

#define _CRT_SECURE_NO_WARNINGS 1;
#include <iostream>
#include <string>
using std::endl;
using std::cout;
using std::ostream;
class String{
public://构造函数,使用一个char类型指针进行初始化String(const char* pstr){//strlen(char *) 传的参数是 char *_size = strlen(pstr);//判断使用栈上空间还是堆上空间if (_size <= 15)//使用栈上的空间{//给其他数据成员进行初始化_capacity = 15;//sizeof(数组名本质也是指针)所以sizeof()传的本质也是指针//先将数组进行清理memset(_buffer._local, 0, sizeof(_buffer._local));//进行浅拷贝字符串复制strcpy(_buffer._local, pstr);}else {//使用堆上的空间_capacity = _size;//使用指针申请空间_buffer._pointer = new char[strlen(pstr) + 1]();strcpy(_buffer._pointer, pstr);}}//拷贝构造String(const String& rhs):_size(rhs._size),_capacity(rhs._capacity){//还是要看字符串有多大if (_size <= 15){//sizeof(数组名本质也是指针)所以sizeof()传的本质也是指针//先将数组进行清理memset(_buffer._local, 0, sizeof(_buffer._local));//进行浅拷贝字符串复制strcpy(_buffer._local, rhs._buffer._local);}else{//这里要多申请一个空字符存放 '\0'_buffer._pointer = new char[_capacity +1]();strcpy(_buffer._pointer, rhs._buffer._pointer);}}//析构函数~String(){//对于短字符串，由于是联合体使用的是同一块空间所以_local如果保存了内容//也会导致_pointer不是空指针//这种情况也不应该直接使用pointer这个成员来判空然后回收//if(_buffer._pointer)if (_size > 15){delete[] _buffer._pointer;_buffer._pointer = nullptr;}}//成员访问运算符重载char& operator[](size_t idx){//先判断是否越界访问if (idx > _size - 1){cout << "out of range!" << endl;static char nullchar = '\0';return nullchar;}else{if (_size > 15){return _buffer._pointer[idx];}else{return _buffer._local[idx];}}}//输出运算符重载函数使用友元的形式friend ostream& operator<<(ostream& os, const String& rhs);
private:union Buffer{char* _pointer;char _local[16];};size_t _size;size_t _capacity;//联合体对象Buffer _buffer;
};
ostream& operator<< (ostream& os, const String& rhs)
{if (rhs._size > 15){os << rhs._buffer._pointer;}else {os << rhs._buffer._local;}return os;
}
void test()
{String str1("hello");cout << str1 << endl;cout << &str1 << endl;printf("%p\n", &str1[0]);cout << str1[0] << endl;str1[0] = 'H';cout << str1 << endl;cout << endl;String str2("hello, world!!!!!");cout << str2<< endl;cout << &str2 << endl;printf("%p\n", &str2[0]);cout << str2[0] << endl;str2[0] = 'H';cout << str2 << endl;cout << endl;String str3 = str1;cout << str3 << endl;String str4 = str2;cout << str4 << endl;
}
int main()
{test();return 0;
}

最佳策略

Facebook提出的最佳策略，将三者进行结合：

因为以上三种方式，都不能解决所有可能遇到的字符串的情况，各有所长，又各有缺陷。综合考虑所有情况之后，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.