【C++】深度剖析string类的底层结构及其模拟实现（一）

前言

在上两篇中，我们已经学习了string类的一个使用，并且做了一些相关的OJ练习，相信大家现在对于string的使用已经没什么问题了。

那我们这篇文章呢，就来带大家对string进行一个模拟实现，这篇文章过后，有些地方大家或许就可以理解的更深刻一点。

1. string的结构

那通过之前文章的学习我们已经对string有了一些了解了：

我们知道，string的底层其实就是一个支持动态增长的字符数组，就像我们数据结构里面学的动态的顺序表。

那确定了它的结构，接下来我们就开始模拟实现它。

我们来新建一个头文件string.h，定义一个string类：

class string
{
public:
//成员函数
private:
  char* _str;
  size_t _size;
  size_t _capacity;
};

string类的成员变量有3个，一个字符指针_str指向开辟的动态数组，_size标识有效数据个数，_capacity记录容量的大小（不包含'\0'）。

相信经过之前数据结构的学习，大家很容易就能明白它们的含义。

但是：

我们现在是要自己实现一个string类，而标准库里面已经有string类了。

所以，为了避免冲突，我们可以定义一个命名空间，把我们自己实现的string放到我们自己的命名空间里面。

namespace yin
{
  class string
  {
  public:
  private:
    char* _str;
    size_t _size;
    size_t _capacity;
  };
}

命名空间的名字，大家可以自己起。

2. 构造、析构

接下来我们来模拟实现一个构造函数：

2.1 无参构造

首先我们提供一个无参的默认构造函数：

string()
  :_str(nullptr)
  ,_size(0)
  ,_capacity(0)
{}

可以直接在初始化列表初始化。

2.2 带参构造

那我们再来写一个带参的构造函数：

string(const char* str)
  :_str(str)
    ,_size(strlen(str))
    ,_capacity(strlen(str))
  {}

2.3 问题发现及修改

这里是用一个常量字符串去初始化我们的string对象。

但是呢？

我们发现这里报错了，为什么？

🆗，是不是一个权限放大的问题啊。

char* str被const修饰，不能被修改，但是赋给_str，_str是char* 类型的，可以修改，所以这里存在权限放大，是不行的。

那怎么办呢？

是不是可以把_str也变成const char* 类型的：

这样就可以了。

那我们来测试一下：

我们可以用构造函数构造一些string对象，然后打印一下。

但是呢，我们现在是自己写的string，还没有重载流插入和流提取<< 和>>，所以不能直接打印string对象。

我们暂且先不实现<< 和>>的重载：

大家想一下，我们在string的使用里学过，string是不是有一个接口叫做c_str啊：

它返回的是一个指向当前string对象对应的字符数组的指针，类型为const char*，那指针是内置类型我们是可以直接用<<打印的。

c_str

那我们可以先来实现一下c_str：

那不是很简单嘛，直接返回_str就行了嘛

试一下：

int main()
{
  yin::string s;
  yin::string s2("hello world");
  cout << s.c_str() << endl;
  cout << s2.c_str() << endl;
  return 0;
}

运行程序：

这里呢？

程序是挂掉了。

我们调式会发现程序在跑到第10行的时候挂了：

我们来分析一下：

首先我们的构造函数好像是没什么问题了                                              

那问题呢其实就出现在打印上面。

那为什么第10行这里打印就崩了呢，不是返回一个空指针吗？那就打印空指针啊。

🆗，这里不是这样的，这里程序挂掉的原因就在于对返回的空指针解引用了。

为什么会解引用？

这里返回的是const char*类型的指针，我们说cout是会自动识别类型，它这里会以字符串的形式去打印，也就是说它不是打印这个指针，而是去解引用打印它指向的字符串，遇到\0，停止，而这里返回的是空指针，所以就挂了。

哎，那如果我们用标准库里的string，这里会挂掉吗？

我们看到这里就没事了，只是第一个什么都没打印，因为s本身就是构造了一个空字符串对象。

所以这个地方是第一个问题，需要我们解决。

operator []

我们先往下看：

对于string我们还会重载[]，那[]就是去返回指定位置的字符的引用，我们实现一下：

char& operator[](size_t pos)
{
  assert(pos < _size);
  return _str[pos];
}

逻辑也很简单，但是呢？

我们会发现现在又出来一个问题：

我们用[]访问到string对象的某个字符是不是可以修改它啊，所以这里返回它的引用，但是，由于前面我们为了解决那个权限放大的问题，把_str的类型修改成了const char* _str，所以现在它指向的内容就不能被修改了。

大家思考一下这里问题的根源在哪里？

是不是就出在我们的构造函数啊，上面带参的构造函数我们用一个常量字符串去初始化我们的string对象，由于存在权限放大的问题不能传过去，所以我们把_str的类型改成const char*，但是我们的string对象是可以被修改的，而现在_str指向一个常量字符串，它有可能直接就是在常量区的，那我们后面扩容是不是也没法搞啊，而且这里还加了const，所以就修改不成了。

那大家思考一些，对于这写问题，我们应该怎么解决呢？

是不是还得去修改一下构造函数啊，对于string对象的这块空间，我们是不是要能够去修改这块空间的内容啊，并且我们如果我们再向里面插入数据空间不够的话是不是还要扩容啊。

所以，我们这里还能这样搞吗？用一个常量字符串构造的时候，直接让我们的_str指向这个常量字符串，是不是不行啊。

我们是不是可以自己去new空间啊，然后把常量字符串的内容拷贝过来。

我们来写一下：

string(const char* str)
  :_size(strlen(str))
{
  _capacity = _size;
  _str = new char[_capacity + 1];
  strcpy(_str, str);
}

这里new的空间大小是_capacity + 1，因为这里_capacity是不包含\0的空间的。

当然这样的话我们_str的也就不要再加const了。

🆗，那这个构造函数修改好了，无参的那个呢？

是不是也存在一些问题啊，我们上面打印无参构造函数构造的对象是不是导致程序崩溃了啊，原因是打印的时候对空指针解引用了。

那要怎么修改呢？

我们这里就不能给空指针了：

怎么做呢？

我们也去new，在这里New一个char的空间，并且用New []，

为什么要用new[]呢？

这里我们就要结合析构函数来看了，我们带参的构造函数用了new【】，所以析构必然要用delete【】，那我们要匹配起来啊，所以这里即使只new一个空间，我们也用new []

析构

那这里我们New一个空间，给它什么值呢？

🆗，我们给一个\0

那这下我们就跟库里面的实现一样了，再来测试：

就没有问题了。

当然这下我们想修改也可以了：

2.4 合二为一 ——全缺省

🆗，那大家再来想一下：

现在我们提供了两个构造函数，一个无参的，一个带参的。

但是，它们两个是不是可以合二为一啊，我们不是学了缺省参数嘛，给个缺省参数不就行了嘛。

那现在问题又来了，缺省参数要怎么给？

首先这里肯定是不能给空指针了：

因为下面strlen是会对str解引用的，如果是空指针就崩了。

那给个\0吗？

肯定也不行，首先类型是不匹配的，不过这里在有些地方也有可能发生类型转换，勉强能赋过去，因为我们之前学过char也是属于整型家族的嘛，但是\0的ASCII码值是0，0转换未指针类型还是空指针。所以不行。

而且在我们当前用的vs2022上直接编译就不通过。

那要怎么给？

🆗，我们这里给一个空串是不是就行啊。

那下面_capacity 和_size都是0嘛，然后开一个空间，把\0拷贝过来。

没有问题。

3. 拷贝构造

我们现在写这样一段代码：

int main()
{
  yin::string s1("hello world");
  yin::string s2(s1);
  cout << s1.c_str() << endl;
  cout << s2.c_str() << endl;
  return 0;
}

很容易看出来这里有一个拷贝构造，s2是s1拷贝构造出来的。

3.1 浅拷贝的默认拷贝构造

但是呢？

我们现在还并没有自己实现拷贝构造，那上面的代码可以运行吗？

🆗，经过前面类和对象的学习，我们知道，拷贝构造函数我们自己不行编译器是不是会默认生成啊。

所以我们可以直接运行上面的代码：

但是我们看到程序出错了，为什么呢？

🆗，这里是不是一个经典的浅拷贝的问题啊。

经过之前的学习我们知道：

若未显式定义，编译器会生成默认的拷贝构造函数。 默认的拷贝构造函数 拷贝对象 按内存存储字节序完成拷贝，这种拷贝叫做浅拷贝，或者值拷贝。

类中如果没有涉及资源申请时，拷贝构造函数我们自己写不写都可以（因为默认生成的就可以搞定）；一旦涉及到资源申请时，则拷贝构造函数是一定要写的，否则就是浅拷贝，就会出现问题。

而我们的string类，底层是一个动态顺序表，空间是我们从堆上new出来的，所以string类的拷贝构造必须是深拷贝，而默认生成的完成浅拷贝，所以这里就出问题了。

我们通过调式来观察一下：

我们可以看到s1和s2的_str指针指向的是同一块空间，那这样析构的时候就会对同一块空间析构两次，所以程序才会崩溃。

另外，除了会析构两次，这种浅拷贝的情况如果我们修改一个string对象是不是也会影响另一个啊，因为它们指向同一块空间。

3.2 深拷贝拷贝构造的实现

所以这里的拷贝构造就需要我们自己实现：

怎么实现呢？

当然就需要我们去完成深拷贝。

那也很简单嘛，我们给s2开一个同样大小的空间，然后把s1的内容拷贝过来就行了。

实现一下：

//拷贝构造
string(const string& s)
  :_size(s._size)
  ,_capacity(s._capacity)
{
  _str = new char[s._capacity + 1];
  strcpy(_str, s._str);
}

那这下是不是就好了啊，我们看一下：

这下两个string对象就拥有独立的空间了。

程序运行就没问题了。

而且，现在我们修改一个对象，对另一个也不会产生影响了：

4. 赋值重载

4.1 浅拷贝的默认赋值重载

然后我们看赋值重载：

赋值重载作为类的6个默认成员函数之一，我们不写编译器是不是也会默认生成啊。

但是：

默认生成的赋值重载是不是也是浅拷贝啊，

所以：

和拷贝构造一样，如果类中未涉及到资源管理，赋值运算符是否实现都可以；一旦涉及到资源管理则必须要自己实现。

4.2 深拷贝赋值重载的实现

那对于string类来说，我们也需要自己实现一个深拷贝的赋值重载：

那深拷贝的赋值重载要怎么搞呢？大家可以先自己尝试写一下。

🆗，我们来分析一下：

对于我们这个赋值的这个场景：

s3 = s1;

是不是会有这样几种情况：

那我们还要分情况去处理吗？好像太麻烦了。

所以，基于这样的原因，我们干脆统一处理，不管哪种情况，我们都直接释放旧空间，然后开新空间拷贝数据：

那这样写就可以了吗？还有没有什么问题？

🆗，如果是一个对象自己给自己赋值，是不是旧出问题了啊。

怎么回事？

随机值？

因为如果是自己给自己赋值的话，_str和 s._str都是指向自己的空间，我们上来delete[] _str直接把自己的空间释放掉了，然后又开新空间拷贝数据，那拷贝的当然是随机值了。

所以我们这里加一个判断：

如果是自己赋值给自己，直接返回就行了。

这下就可以了。

但是：

其实现在我们写成这个样子，还存在一些隐患：

我们这里上来是直接把_str的空间释放掉了，然后去new开新空间，但是new是不是也有可能失败啊（失败抛异常，关于异常我们后面会讲）。

那这样的话，我们直接把原空间释放了，但是开新空间失败了，后面又去拷贝数据这样肯定不行的（当然如果我们去try catch捕获的话就直接跳到catch的地方了，所以其实也没有什么大问题，不过是把原来的string对象破坏了，但是破坏也就破坏了，反正都抛异常了）。

不过我们可以稍微改一下，这样写：

这样即使开空间失败了，我们也没有把原对象破坏掉。

5. string对象的遍历

那如果现在我们想要遍历我们创建的string对象：

5.1 【】（const版本和非const版本）

我们上面是不是已经重载了[ ]了，那首先我们就可以使用[ ]借助for循环去遍历：

当然遍历的同时我们也可以修改。

那现在我们要写一个打印string对象的函数：

首先大家思考一下这里我们要如何传参？

传值可不可以，当然是可以的，我们已经自己实现了拷贝构造了。

但是这里我们会选择传值吗？

是不是不会啊，传值的话还要拷贝构造，那直接传引用不就行了嘛。

那传引用的话，我们这里只是打印，不想它被修改，所以我们一班还会加const：

但是这样写我们会发现它报错了。

为什么会报错？

🆗 ，这个东西我们之前类和对象里面在讲const成员函数的时候是不是说过啊。

这里s是const对象，它去调size和operator[]这些非const成员函数的时候，this指针的传参发生了权限放大（大家不是很清楚的话可以复习一下之前的文章）。

那我们也说了：

对于类的成员函数，如果在成员函数内部不需要改变调用它的对象，最好呢都可以把它写成const成员函数。

这样普通对象可以调，const对象是不是也可以调了。

那const对象调[ ]的话，const对象不能修改，所以我们返回引用也返回const引用。

但是现在有一个新的问题：

现在普通对象和const对象都可以调[]了，这没问题，但是由于返回的const引用，而普通对象可以被修改的，那现在返回的const引用普通对象还能通过[]修改吗？

不行了：

那怎么解决这个问题？

我们是不是要提供两个版本的[]啊。

我们看到标准库里的string就是这样给的：

所以呢？

这样就行了：

5.2 迭代器模拟实现（普通）

那除了[]可以遍历访问string对象，还有什么方法？

🆗，是不是还可以用迭代器啊。

那我们接下来就来实现一下迭代器。

怎么实现呢？

那迭代器我们说了大家可以理解成一个像指针一样的东西，但是不一定是指针。

我们最开始介绍了STL有好几个版本，不同的版本实现可能是不一样的。

那其实vs下string的迭代器呢就不是使用指针实现的，而G++下使用的SGI版本是指针实现的。

那这里我们模拟实现就使用指针来实现。

那其实很简单：

相信这段代码不用给大家过多解释了。

那我们的迭代器就实现好了。

我们来试一下：

int main()
{
  yin::string s1("hello world");
  for (yin::string::iterator it = s1.begin(); it != s1.end(); it++)
  {
    cout << *it << " ";
  }
  cout << endl;
  return 0;
}

可以。

那在访问的同时我们还可以修改它：

那至于反向迭代器呢，就稍微复杂一点，我们后面一点再讲。

那用范围for可以遍历吗？

当然也可以。

因为我们自己实现了迭代器，我们之前提过，范围for的底层就是用的迭代器。

大家可以理解成范围for的语法其实就跟我们之前学过的宏有点类似，它会被替换成迭代器，相当于把*it赋值给e。

我们可以简单验证一下：

我们把迭代器的实现稍微做一点变动，比如，我们把begin的b改成大写B。

我们发现范围for就用不了了。

5.3 const迭代器模拟实现

我们继续来看：

如果我们再这里面使用范围for：

会发现用不了了。

为什么呢？

🆗，我们说了范围for底层是用的迭代器，而我们现在只实现了普通迭代器，那范围for替换成调用迭代器，这里的s是const对象，去调用普通迭代器（非const成员函数），是不是又是权限放大啊。

所以不行。

那怎么解决呢？

是不是就需要我们实现const迭代器了。

就这样。

这下就可以了。

6. 常见关系运算符重载

我们看到标准库里的string还重载了很多关系运算符。

那我们也来模拟实现几个：

那大家思考一下，字符串之间的比较，要怎么做？

我们这里是不是可以考虑直接复用strcmp啊。

写一下：

我们实现两个，剩下的就可以直接复用了。

那大家思考一下，我们上面写的有没有什么问题？

来看：

这里换一下位置就不行了，为什么呢？

因为这样的话就是s去调==了，而s是const对象，调的是非const成员函数，就不行了。

所以，我们说过好几遍了：

对于类的成员函数，如果在成员函数内部不需要改变调用它的对象，最好呢都可以把它写成const成员函数。

全加上const，这样就行了。

🆗，那我们来简单测试一下：

注意这里要加个括号由于优先级的问题。