std::string的底层实现

面试重要

void test(){
    string s1("hello");
    cout << sizeof(string) << endl;//结果是32，说明string的底层实现也是类似于vector使用了几个指针
}

stirng实现的三种方式:

Eager Copy(深拷贝)

COW(Copy_On_Write)(写时复制)

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

目前是根据SSO的思想实现的

写时复制的原理

当字符串对象进行复制控制时，可以优化为指向同一个堆空间的字符串，但是有一个问题是回收堆空间字符串内容的时候会出现double free的问题，如何解决？

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

优化点在于进行复制的时候才使用引用计数，单独创建对象没有优化空间，即使对象的内容完全一样也不行，每个对象都要单独存放

方案一：如果引用计数是一个普通的数据成员行不行？

发生复制的时候，除了本身的引用计数要被改变，复制的那个对象引用计数也要改变，但是拷贝时候，使用的是const string &rhs,是不能改变rhs本身的内容的，这样导致的结果就是拷贝的两个对象的引用计数不一样

方案二：那使用静态成员行不行？

确实可以修改发生拷贝的两个对象的引用计数了，但是这个引用计数是被所有成员所共享的，如果这俩发生拷贝，引用计数设置为2，那其他的该类的对象该设置为几？所以也是不可行的

方案三：用堆空间来保存引用计数

除了搞一个_pstr指针指向stirng,再搞一个__pref来指向堆上的引用计数

优化：

按上面的思路需要用两次new表达式（字符串，引用计数），其实可以优化为只是用一次，因为申请堆空间的行为一定涉及系统调用，系统调用很消耗性能，所以可以把引用计数和字符串放在同一片空间，

引用计数放字符串前面还是后面？

应该放前面，因为放后面的话每次都要找字符串的末尾才能找到引用计数

char * 指针也应该放在字符串的首地址

COWString的实现

class CowString{
public:    
CowString();
CowString(const char *pstr);
CowString(const CowString &rhs);
CowString & operator=(const CowString & rhs);
~CowString();

int size() const{
  return string(_pstr);
}
const char * c_str(){
  return _pstr;
}
friend ostream & operator<<(ostream & os,const CowString &rhs);
private:
char *_pstr;

};

ostream & operator<<(ostream & os,const CowString &rhs){
os << rhs._pstr;
return os;
}
CowString::CowString()
:_pstr(new char[1+4]()+4)//前面的+的4代表的引用计数的空间，后面的+4代表的是偏移_pstr让其指向字符串的首地址，但是可读性很差，可以给两个4整一个static const int的数据成员放在私有区域
{}

class CowString{
public:    
CowString();
CowString(const char *pstr);
CowString(const CowString &rhs);
CowString & operator=(const CowString & rhs);
~CowString();

int size() const{
  return string(_pstr);
}
const char * c_str(){
  return _pstr;
}
friend ostream & operator<<(ostream & os,const CowString &rhs);
private:
static const_int kRefcountLength = 4;
char *_pstr;

};

ostream & operator<<(ostream & os,const CowString &rhs){
os << rhs._pstr;
return os;
}
CowString::CowString()
:_pstr(new char[1+kRefCountLength]()+kRefCountLength)
{
//初始化引用计数指针
//要把前四个空字符数组初始化
*(int*)(_pstr - KRefCounntLength)=1;
//解释 先将_pstr偏移到申请的整的数组的头部（其实就是引用计数该指向的位置），但是此时_pstr是个char*指针 只能管理一个字节的空间，所以强转化为int*类型，然后解引用赋上初值，这一步可以封装为一个函数


}

class CowString{
public:    
CowString();
CowString(const char *pstr);
CowString(const CowString &rhs);
CowString & operator=(const CowString & rhs);
~CowString();

int size() const{
  return string(_pstr);
}
const char * c_str(){
  return _pstr;
}
int use_count(){
  return *(int*)(_pstr-kRefCountLength)
}
friend ostream & operator<<(ostream & os,const CowString &rhs);
private:
void initRefcount(){
  *(int*)(_pstr - KRefCountLength)=1;
}
//增加或者减少引用计数也可以封装成函数
void increaseRefcount(){
  ++*(int*)(_pstr - KRefCounntLength)
}
void decreaseRefcount(){
  --*(int*)(_pstr - KRefCountLength)
}
private:
static const_int kRefcountLength = 4;
char *_pstr;

};

ostream & operator<<(ostream & os,const CowString &rhs){
os << rhs._pstr;
return os;
}
CowString::CowString()
:_pstr(new char[1+kRefCountLength]()+kRefCountLength)
{
//初始化引用计数指针
//要把前四个空字符数组初始化
initRefcount();   
}

CowString::~CowString(){
decreaseRefcount();
if(use_count() == 0){
  delete [] (_pstr-kRefCountLength);//不能直接释放_pstr，因为_pstr指向的是字符串的首地址，还有前面的引用计数的空间没释放呢所以要偏移回去把申请的所有空间都给释放掉
}
}

//拷贝构造
CowString::CowString(const CowString &rhs)
:_pstr(rhs._pstr)//浅拷贝
{
increaseRefCount();
}

CowString::CowString(const char *pstr)
:    
{}//这个开辟空间的代码也很冗余，所以可以考虑结合成一个函数

class CowString{
public:    
CowString();
CowString(const char *pstr);
CowString(const CowString &rhs);
CowString & operator=(const CowString & rhs);
~CowString();

int size() const{
  return string(_pstr);
}
const char * c_str(){
  return _pstr;
}
int use_count(){
  return *(int*)(_pstr-kRefCountLength)
}
friend ostream & operator<<(ostream & os,const CowString &rhs);
private:
void initRefcount(){
  *(int*)(_pstr - KRefCountLength)=1;
}
//增加或者减少引用计数也可以封装成函数
void increaseRefcount(){
  ++*(int*)(_pstr - KRefCounntLength)
}
void decreaseRefcount(){
  --*(int*)(_pstr - KRefCountLength)
}

char *malloc(const char * pstr = nullptr){
  //给pstr一个默认值，如果pstr不是默认值说明是有参，否则是无参
  if(pstr){
      return new char[strlen(pstr)+1+kRefCountLength]()+kRefCountLength;
  }
  else{
      return new char[1+kRefCountLength])()+kRefCountLengt
  }
}

private:
static const_int kRefcountLength = 4;
char *_pstr;

};

ostream & operator<<(ostream & os,const CowString &rhs){
os << rhs._pstr;
return os;
}
CowString::CowString()
:_pstr(malloc())
{
//初始化引用计数指针
//要把前四个空字符数组初始化
initRefcount();   
}

CowString::~CowString(){
decreaseRefcount();
if(use_count() == 0){
  delete [] (_pstr-kRefCountLength);//不能直接释放_pstr，因为_pstr指向的是字符串的首地址，还有前面的引用计数的空间没释放呢所以要偏移回去把申请的所有空间都给释放掉
}
}

//拷贝构造
CowString::CowString(const CowString &rhs)
:_pstr(rhs._pstr)//浅拷贝
{
increaseRefCount();
}

CowString::CowString(const char *pstr)
:_pstr(malloc(pstr)) //这个开辟空间的代码也很冗余，所以可以考虑结合成一个函数   
{
initRefCount();
strcpy(_pstr,pstr);//将字符串内容复制到开辟的空间中
}
CowString & CowString::operator=(const CowString &rhs){
if(this != &rhs){
  decreaseRefcount();//这里回收又有一段与析构相同的操作，所以可以封装为函数
  if(use_count() == 0){
     
  }
}
return *this;
}

class CowString{
public:    
CowString();
CowString(const char *pstr);
CowString(const CowString &rhs);
CowString & operator=(const CowString & rhs);
~CowString();

int size() const{
  return string(_pstr);
}
const char * c_str(){
  return _pstr;
}
int use_count(){
  return *(int*)(_pstr-kRefCountLength)
}
friend ostream & operator<<(ostream & os,const CowString &rhs);
private:
void initRefcount(){
  *(int*)(_pstr - KRefCountLength)=1;
}
//增加或者减少引用计数也可以封装成函数
void increaseRefcount(){
  ++*(int*)(_pstr - KRefCounntLength)
}
void decreaseRefcount(){
  --*(int*)(_pstr - KRefCountLength)
}

char *malloc(const char * pstr = nullptr){
  //给pstr一个默认值，如果pstr不是默认值说明是有参，否则是无参
  if(pstr){
      return new char[strlen(pstr)+1+kRefCountLength]()+kRefCountLength;
  }
  else{
      return new char[1+kRefCountLength])()+kRefCountLengt
  }
}
void release(){
  decreaseRefCount();
  if(use_count == 0){
      delete [] (_pstr-kRefCountLength);
  }
}

private:
static const_int kRefcountLength = 4;
char *_pstr;

};

ostream & operator<<(ostream & os,const CowString &rhs){
os << rhs._pstr;
return os;
}
CowString::CowString()
:_pstr(malloc())
{
//初始化引用计数指针
//要把前四个空字符数组初始化
initRefcount();   
}

CowString::~CowString(){

release();
}

//拷贝构造
CowString::CowString(const CowString &rhs)
:_pstr(rhs._pstr)//浅拷贝
{
increaseRefCount();
}

CowString::CowString(const char *pstr)
:_pstr(malloc(pstr)) //这个开辟空间的代码也很冗余，所以可以考虑结合成一个函数   
{
initRefCount();
strcpy(_pstr,pstr);//将字符串内容复制到开辟的空间中
}
CowString & CowString::operator=(const CowString &rhs){
if(this != &rhs){//考虑自复制，因为如果不判断，发生自复制的时候，先减少引用计数，然后把空间释放了，然后在发生复制，就出问题了,因为此时该指针已经指向空了
  release();//这里回收又有一段与析构相同的操作，所以可以封装为函数
  _pstr = rhs._pstr;//发生浅拷贝
  increaseRefCount();
}
return *this;
}

增加下标访问运算符的重载函数

class CowString{
public:    
CowString();
CowString(const char *pstr);
CowString(const CowString &rhs);
CowString & operator=(const CowString & rhs);
~CowString();

int size() const{
  return string(_pstr);
}
const char * c_str(){
  return _pstr;
}
int use_count(){
  return *(int*)(_pstr-kRefCountLength)
}
friend ostream & operator<<(ostream & os,const CowString &rhs);
private:
void initRefcount(){
  *(int*)(_pstr - KRefCountLength)=1;
}
//增加或者减少引用计数也可以封装成函数
void increaseRefcount(){
  ++*(int*)(_pstr - KRefCounntLength)
}
void decreaseRefcount(){
  --*(int*)(_pstr - KRefCountLength)
}

char *malloc(const char * pstr = nullptr){
  //给pstr一个默认值，如果pstr不是默认值说明是有参，否则是无参
  if(pstr){
      return new char[strlen(pstr)+1+kRefCountLength]()+kRefCountLength;
  }
  else{
      return new char[1+kRefCountLength])()+kRefCountLengt
  }
}
void release(){
  decreaseRefCount();
  if(use_count == 0){
      delete [] (_pstr-kRefCountLength);
  }
}

private:
static const_int kRefcountLength = 4;
char *_pstr;

};

ostream & operator<<(ostream & os,const CowString &rhs){
os << rhs._pstr;
return os;
}
CowString::CowString()
:_pstr(malloc())
{
//初始化引用计数指针
//要把前四个空字符数组初始化
initRefcount();   
}

CowString::~CowString(){

release();
}

//拷贝构造
CowString::CowString(const CowString &rhs)
:_pstr(rhs._pstr)//浅拷贝
{
increaseRefCount();
}

CowString::CowString(const char *pstr)
:_pstr(malloc(pstr)) //这个开辟空间的代码也很冗余，所以可以考虑结合成一个函数   
{
initRefCount();
strcpy(_pstr,pstr);//将字符串内容复制到开辟的空间中
}
CowString & CowString::operator=(const CowString &rhs){
if(this != &rhs){//考虑自复制，因为如果不判断，发生自复制的时候，先减少引用计数，然后把空间释放了，然后在发生复制，就出问题了,因为此时该指针已经指向空了
  release();//这里回收又有一段与析构相同的操作，所以可以封装为函数
  _pstr = rhs._pstr;//发生浅拷贝
  increaseRefCount();
}
return *this;
}
//这里有一个问题是赋值和输出分离不开，如果操作时 <<str[0]那么就又复制出来一份数据，但是实际上并不需要复制，所以碰见问题解决不了就加一层，可以加一个charProxy代理类，用这个类把两个操作给切开
char & CowString::operator[](int idx){
    if(idx >= 0 && idx < size()){
        if(use_count() > 1){
            //原本空间的引用计数-1
            decreaseRefcount();
            //进行深拷贝
            char * ptemp = malloc(_pstr);
            strcpy(ptemp,_pstr);
            //改变指向
            _pstr = ptemp;
            //新的空间初始化引用计数
            initRefcount();
        }
        return _pstr[idx];
    }else{
        cout << "out of range" << endl;
        static char nullchar = '\0';
        return nullchar;
    }
}

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

如果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[]函数返回是这个新类型的对象，然后在这个新类型中对<<和=进行重载，让这两个运算符能够处理新类型对象，从而分开了处理逻辑。

具体实现

class CowString{
 
    //通过它来把读写操作给分开
    class CharPorxy{
    public:
        CharProxy(CowStriing &self,int idx)
        :_self(self)
        ,_idx(idx)
        {}
        char operator=(char ch);
        friend ostream & operator<<(ostram &os,const CharProxy &rhs);
   	private:
        CowString & _self;
        int _idx;
    };
    
public:   
 CowString();
 CowString(const char *pstr);
 CowString(const CowString &rhs);
 CowString & operator=(const CowString & rhs);
 ~CowString();
 
 int size() const{
     return string(_pstr);
 }
 const char * c_str(){
     return _pstr;
 }
 int use_count(){
     return *(int*)(_pstr-kRefCountLength)
 }
    //返回一个charProxy对象，CharProxy对象可能会经历赋值这样的操作，还可能经历输出的操作即
    //CharProxy对象 = 'k'
    //cout << CharProxy对象
    CharProxy operator[](int idx);
 friend ostream & operator<<(ostream & os,const CowString &rhs);
friend ostream & operator<<(ostram &os,const CharProxy &rhs);
private:
 void initRefcount(){
     *(int*)(_pstr - KRefCountLength)=1;
 }
 //增加或者减少引用计数也可以封装成函数
 void increaseRefcount(){
     ++*(int*)(_pstr - KRefCounntLength)
 }
 void decreaseRefcount(){
     --*(int*)(_pstr - KRefCountLength)
 }
 
 char *malloc(const char * pstr = nullptr){
     //给pstr一个默认值，如果pstr不是默认值说明是有参，否则是无参
     if(pstr){
         return new char[strlen(pstr)+1+kRefCountLength]()+kRefCountLength;
     }
     else{
         return new char[1+kRefCountLength])()+kRefCountLengt
     }
 }
 void release(){
     decreaseRefCount();
     if(use_count == 0){
         delete [] (_pstr-kRefCountLength);
     }
 }
 
private:
 static const_int kRefcountLength = 4;
 char *_pstr;
 
};

ostream & operator<<(ostream & os,const CowString &rhs){
 os << rhs._pstr;
 return os;
}
CowString::CowString()
:_pstr(malloc())
{
 //初始化引用计数指针
 //要把前四个空字符数组初始化
 initRefcount();   
}

CowString::~CowString(){
 
 release();
}

//拷贝构造
CowString::CowString(const CowString &rhs)
:_pstr(rhs._pstr)//浅拷贝
{
 increaseRefCount();
}

CowString::CowString(const char *pstr)
:_pstr(malloc(pstr)) //这个开辟空间的代码也很冗余，所以可以考虑结合成一个函数   
{
 initRefCount();
 strcpy(_pstr,pstr);//将字符串内容复制到开辟的空间中
}
CowString & CowString::operator=(const CowString &rhs){
 if(this != &rhs){//考虑自复制，因为如果不判断，发生自复制的时候，先减少引用计数，然后把空间释放了，然后在发生复制，就出问题了,因为此时该指针已经指向空了
     release();//这里回收又有一段与析构相同的操作，所以可以封装为函数
     _pstr = rhs._pstr;//发生浅拷贝
     increaseRefCount();
 }
 return *this;
}

CowString::CharProxy  CowString::operator[](int idx){
	//if(idx>=0 && idx < size()){
    return CharPorxy(*this,idx); 
	//}else{
        //这里没法返回值了所以还要把这个操作分下去
    //}
}

char CowString::CharProxy::operator=(char ch){
    //把上面判断是否越界的操作分到这里来这里的CowString的成员函数和数据成员都要使用对象来调用
    if(_idx>=0&&_idx<_self.size()){
        if(_self.use_count() > 1){
            _self.decreaseRefCount();
            char *ptemp = _self.malloc();
            strcpy(ptemp,_self._pstr);
            _self.initRefCount();
        }
        //执行写操作
        _self._pstr[_idx]=ch;
        return _self._pstr[_idx];
    }else{
        static char nullchar='\0';
        return nullchar;
    }
}
ostream & operator<<(ostram &os,const CowString::CharProxy &rhs){
    //越界判断
    if(rhs._idx>=0 && rhs._idx < rhs._self.size()){
    	os << rhs._self._pstr[rhs._idx];//这里还要做一次友元声明，因为第一次是在CharProxy做的友元声明，而现在访问的是CowString的私有成员，所以需要在CowString里面再做一次友元声明
    }else{
        os << "访问越界";
    	return os;
    }
}

优化空间（最后输出流运算符重载能否去掉双友元）

使用类型转化函数

目的是cout << str1[0]

str1[0]返回的是一个CharProxy对象能否用类型转换函数转换为char类型

class CharPorxy{
    public:
        CharProxy(CowStriing &self,int idx)
        :_self(self)
        ,_idx(idx)
        {}
    
        char operator=(char ch);
    //类型转化函数返回的一定是一个副本   
    operator char(){
            return _self._pstr[_idx];
        }
   	private:
        CowString & _self;
        int _idx;
    };

因为类型转换函数返回的一定是一个副本所以

str1[0] = ‘H’；

这样的操作不能使用类型转换函数，这个是右值（因为是一个临时对象），不能被赋值

短字符优化（SSO）

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

union表示共用体，允许在同一内存空间中存储不同类型的数据。共用体的所有成员共享一块内存，但是每次只能使用一个成员。
1
2
3
4
5
6
7
8
9
10
class string {
	union Buffer{
		char * _pointer;
		char _local[16];
	};
	
	size_t _size;
	size_t _capacity;
    Buffer _buffer;
};
小于15个字符就在栈上存，超过15个字符就在堆上放（前提是对象在栈上，如果对象在堆上，那么短字符串就在堆上，不过是和对象放在一起的）

最佳策略

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

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

很短的（0~22）字符串用SSO，23字节表示字符串（包括’\0’）,1字节表示长度

中等长度的（23~255）字符串用eager copy，8字节字符串指针，8字节size，8字节capacity.

很长的(大于255)字符串用COW, 8字节指针（字符串和引用计数），8字节size，8字节capacity.