【C++从0到王者】第十站：手撕string（上）-阿里云开发者社区

一、String的基本结构

string在库里面实现的是比较冗余的，我们这里就实现一个最基本的string，该string采用类似顺序表的方式来进行实现，总体来说比较简单。

我们使用三个私有成员变量，一个指向string内容的指针，一个记录当前有效字符个数的变量size，一个记录当前容量的变量capacity，如下所示

char* _str;
size_t _size;
size_t _capacity;

二、String的构造函数

对于string的构造函数，在库里面有很多个写法。里面的显得过于冗余，我们采用比较简单的方式来实现。

1.string(const char* str)

如下代码所示，在这个构造函数中，我们使用了初始化列表来为_str开空间，_size和_capacity赋初值，然后再使用strcpy函数即可将字符串的内容放入数据中。

这里值得注意的是我们的size是记录的有效字符个数，他是不包括\0字符的。所以我们给_size赋初值的时候要切记注意不要加1。同样的，对于_capacity这个变量而言，它代表的的容量也是不能考虑\0字符的，所以它也是相比实际容量要少一个的，而在开容量的时候，一定要多开一个这个是用来存放字符\0的

//给一个字符串去构造一个string
    string(const char* str)
      :_str(new char[strlen(str) + 1])
      , _size(strlen(str))
      , _capacity(strlen(str))
    {
      strcpy(_str, str);
    }

2.string()

这是一个无参的默认构造函数，由于我们一开始不知道要方多少个字符，不妨我们就一开始给16个空间，0个有效字符，15个容量即可。初始化的时候，我们直接初始化一些\0字符即可

//无参的默认构造函数
    string()
      :_str(new char[16])
      ,_size(0)
      ,_capacity(15)
    {
      memcpy(_str, "\0\0\0\0", 4);
    }

3.string(const char* str = " ")

这个构造函数实际上是不能与前面的重合的。因为他是一个默认构造函数。不过是带了缺省参数的缘故。它的思路与前面的都是一致的

//以上合二为一的构造函数写法
    string(const char* str = "")
      :_str(new char[strlen(str) + 1])
      , _size(strlen(str))
      , _capacity(strlen(str))
    {
      strcpy(_str, str);
    }

4.string(const string& s)

显然这是一个拷贝构造函数，我们的串中涉及到了开空间的问题，必须得需要深拷贝，所以我们需要自己写一个拷贝构造，而不能依赖于编译器自己生成的拷贝构造函数

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

二、String的析构函数

这个函数就比较简单了，我们直接去delete掉字符串，然后置空，清空数据即可

//析构函数
    ~string()
    {
      delete[] _str;
      _str = nullptr;
      _size = 0;
      _capacity = 0;
    }

三、获取String中的字符串

这个接口我们也是比较熟悉的，它可以直接获取string中的字符串，注意它需要加上const进行修饰，因为我们是不会破坏对象里面的数据的，所以需要后置const，并且我们返回这个字符串的时候，它也是肯定不会被修改的，所以也需要加上const

//获取string中的字符串
    const char* c_str() const 
    {
      return _str;
    }

四、获取有效元素个数

这个接口的意思也比较直白，就是获取_size的值，直接返回即可

//获取当前有效元素个数
    size_t size() const 
    {
      return _size;
    }

五、operator[]运算符重载

这个运算符重载，我们需要实现两个，一个是针对普通对象的，一个是针对于const的对象的。我们注意到[]这个的特性，它既可以作为右值（读取），又可以作为左值（修改），我们想要去修改读或者修改某一处的值，那么我们应该是得知道该处的地址的，我们可以直接用引用，将该处空间的别名返回，这样一来，即可避免更大的开销，因为传引用返回可以节省开销，又可直接根据该处的别名去访问该处。从而达到读写的目的。

对于const修饰的对象而言，由于它不可能被修改，只能读写。但为了节省开销，我们还是采用传引用返回，这样我们就得采用const来进行一次修饰，缩小权限。使之只能读，不能写

//读写接口
    char& operator[](size_t pos)
    {
      assert(pos < _size);
      return _str[pos];
    }
    //只读接口
    const char& operator[](size_t pos) const
    {
      assert(pos < _size);
      return _str[pos];
    }

六、增删查改之增

1.reserve()

我们首先需要知道的就是这个函数了，这个函数的功能就是扩容，但凡涉及到增的时候，必然就需要进行扩容了。它的具体实现如下

这个函数它接收一个参数n，也就是需要扩到多大，注意到最好不要进行缩容，所以我们为了简洁，默认使他只能扩容。我们先扩充n+1个空间，这多出来的一个是为\0字符做出打算的

扩容的具体逻辑是这样的，首先先开辟n+1个空间，然后将原来的字符内容交给这个新空间，最好在修改容量，和释放之前的空间。

void reserve(size_t n)
    {
      if (n > _capacity)
      {
        char* tmp = new char[n + 1];
        strcpy(tmp, _str);
        _capacity = n;
        delete[] _str;
        _str = tmp;
      }
    }

2.pushback(char ch)

这段代码是这样的，我们首先检查容量是否足够，如果不足够，那么我们就扩容，然后就是类似顺序表的操作进行插入数据。不要忘记最后添加一个\0字符

void pushback(char ch)
    {
      if (_size == _capacity)
      {
        int newcapacity = _capacity == 0 ? 4 : _capacity * 2;
        reserve(newcapacity);
      }
      _str[_size++] = ch;
      _str[_size] = '\0';
    }

3.append(const char* str)

这个函数的逻辑和上一个是差不多的，我们需要做的就是注意扩容多大空间，我们是扩容到len+_size个大小即可。最后直接字符串拷贝即可

void append(const char* str)
    {
      int len = strlen(str);
      if (len + _size > _capacity)
      {
        int newcapacity = (len+_size) ;
        reserve(newcapacity);
      }
      //while (len--)
      //{
      //  _str[_size++] = *str++;
      //}
      //_str[_size] = '\0';
      strcpy(_str + _size, str);
      _size += len;
    }

4.operator+=

这是一个运算符重载，我们有两种形式，一种是加字符，一种是加字符串。注意我们需要一个返回值了，因为我们+=之后其实是有一个返回值的，这个返回值就是我们这个被修改后的对象。我们可以直接复用接口，然后返回this指针即可

string& operator+=(char ch)
    {
      pushback(ch);
      return *this;
    }
    string& operator+=(const char* str)
    {
      append(str);
      return *this;
    }

5.insert

对于insert这个接口，他是在某个位置处插入n个字符或者插入一个字符串。那么这样的话我们首先需要做的就是扩容，然后就是移动原来的数据，最后就是插入数据。这里的移动数据我们下面这两个接口采用的是计数的方式来实现的

void insert(size_t pos, size_t n, char ch)
    {
      assert(pos <= _size);
      if (_size + n > _capacity)
      {
        int newcapacity = _size + n;
        reserve(newcapacity);
      }
      int count = _size - pos + 1;
      int size = _size;
      while (count--)
      {
        _str[size + n] = _str[size];
        size--;
      }
      int i = pos;
      for (i = pos; i < pos + n; i++)
      {
        _str[i] = ch;
      }
      _size += n;
    }
    void insert(size_t pos, const char* str)
    {
      assert(pos <= _size);
      int len = strlen(str);
      if (_size + len > _capacity)
      {
        int newcapacity = _size + len;
        reserve(newcapacity);
      }
      int count = _size - pos + 1;
      int size = _size;
      while (count--)
      {
        _str[size + len] = _str[size];
        size--;
      }
      int i = pos;
      for (i = pos; i < pos + len; i++)
      {
        _str[i] = *str;
        str++;
      }
      _size += len;
    }

上面的两种方法是最容易理解的方法，但是我们来看一下这个写法

上面这种写法看似正确，实际上也有一些问题，当pos为0的时候，由于pos为size_t类型，导致end也被强制类型转化了，故代码崩溃。

为了进行修改，我们可以这样做，进行一次强制类型转换

我们还可以这样做，定义一个静态成员变量npos，使之不可以等于npos

注意上面这种写法我们需要注意的一点是，c++中虽然上面的是正确的，但是我们还可以这样写，但是不建议这样写：

这样写编译器是可以通过的，但是要记住只有整型类型可以这样写，浮点类型都不可以，这是一个特殊的语法。我们一般不会这样使用的

七、增删查改之删

1.erase

这段代码我们的思想就是挪动数据即可，当长度超出剩余的字符串长度时候直接将后面全部删完即可，也就是给该位置加上一个\0字符。其余情况直接将后面的挪动到前面即可。

//增删查改之删
    void erase(int pos, size_t len = npos)
    {
      assert(pos <= _size);
      if (len == npos || pos + len > _size)
      {
        _str[pos] = '\0';
        _size = pos;
      }
      else
      {
        int end = pos + len;
        while (end <= _size)
        {
          _str[pos++] = _str[end++];
        }
        _size -= len;
      }
    }

2.clear

void clear()
    {
      _str[0] = '\0';
      _size = 0;
    }

八、增删查改之查

查找我们一般是查找一个字符或者查找一个字符串，找字符简单，找字符串的话我们可以直接调用strstr这个函数，暴力匹配即可。或者kmp算法和BM算法也是可以的

//查
    size_t find(char ch, size_t pos = 0)
    {
      assert(pos < _size);
      for (int i = pos; i < _size; i++)
      {
        if (_str[i] == ch)
        {
          return i;
        }
      }
      return npos;
    }
    size_t find(const char* str, size_t pos = 0)
    {
      assert(pos < _size);
      char* ptr = strstr(_str + pos, str);
      if (ptr)
      {
        return (ptr - str);
      }
      else
      {
        return npos;
      }
    }

九、获取子串

如下代码所示，我们想要获取一部分串，思路是这样的，先看len是否已经超出了串的长度，如果没有超出，那么可以，如果超出了，那就意味着从pos开始全部截取，那么修改len的值直至合适为止。然后我们定义一个空串。我们对这个串的容量刚好就是这个修改后的len的大小，我们从pos位置开始，一直加len次。这样我们九获取了我们希望获得的子串，我们现在返回它即可

在这里我们需要注意两点：

我们在定义这个空串的时候，不能将其设置为静态的。因为静态的串只会定义一次。以后再次调用这个函数是会出现问题的
我们的返回值不可以是引用返回，因为我们返回的串出了作用域就不在了
这个函数必须得有拷贝构造函数，因为其必须为传值返回。且该串涉及到开空间的问题，我们必须得自己写一个深拷贝构造。否则会对同一块空间调用两次析构函数而产生错误

//提取出指定位置的串
    string substr(size_t pos = 0, size_t len = npos)
    {
      assert(pos < _size);
      size_t n = len;
      if (len == npos || pos + len > _size)
      {
        n = _size - pos;
      }
      string tmp;
      tmp.reserve(n);
      for (size_t i = pos; i < pos + n; i++)
      {
        tmp += _str[i];
      }
      return tmp;
    }

十、resize

resize的功能是扩充size,当容量足够的时候，若新的size小于原来的size，那么就相当于删除数据，如果容量足够且size大于原来的数据，那么就为其补充数据直至size。如果容量不够size的值，那么就先扩容，然后再填数据

//调整size
    void resize(size_t n, char ch = '\0')
    {
      if (n <= _size)
      {
        _size = n;
        _str[_size] = '\0';
      }
      else
      {
        reserve(n);
        for (int i = _size; i < n; i++)
        {
          _str[i] = ch;
        }
        _size = n;
        _str[_size] = '\0';
      }
    }

十一、流插入

1.流插入

首先我们在之前写日期类的时候，我们就知道了流插入的样子大概是这样写的

这里必须在类外进行定义，这是为了改变变量顺序，符合使用习惯

其次必须加上引用，因为ostream有防拷贝设计

对于流插入，我们有几种方式可以去实现，要么直接定义友元函数，然后直接访问s里面的字符串

要么就是不适用友元，使用循环逐个打印

ostream& operator<<(ostream& out, const string& s)
  {
    for (size_t i = 0; i < s.size(); i++)
    {
      out << s[i];
    }
    return out;
  }

甚至我们还可以使用范围for

2. s.c_str()与cout<<s的区别

这两个我们在打印的时候，看似没有什么太大区别，其实还是差距蛮大的。

首先c_str()它是一个字符串，它遇到’\0’就结束了。而直接打印s的话看的并非是’\0’字符,而是size的大小。有多少size打印多少个字符。这样一来有可能在存储的字符串里面恰巧有一个是’\0’的话，那么这两者打印的结果是不一样的。

如下面所示，是我们自己写的string演示

下方是库里面的string演示

需要注意到’\0’这个字符vs2022中是不会被打印出来的，而在2013下是可以打印出来的

这样一想确实挺合理。我们自己写的与库里面的一样是我们基于循环写出来的。但是倘若我们将这个循环换位范围for，那么我们发现全乱了。

那么这是为什么呢？为什么范围for不符合我们的期望呢？我们想要知道答案，那么我们就得去看迭代器是如何实现了

注意到我们的迭代器事实上都是通过字符串的长度来实现的。这样一来的话，就无形之中将’\0’之后的数据没有给考虑进去。所以事实上我们的迭代器有bug。其实在我们的string类中，只要涉及到string.h相关的函数中，大部分都需要重新修改一下了

十二、修改由于字符函数导致的bug

我们在上面中，发现前面的大部分代码事实上是存在很大的问题的，存在很大的隐患。我们现在就先来进行修改，我们可以将原来的str系列的函数全部替换为mem系列的函数，这样就能解决掉这个问题了

1.修改构造函数

1>string(const char* str = “”)

这是我们原来的构造函数

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

其实这个代码使用memcpy和strcpy都是可以的，但是我们为了统一以下，我们现在使用memcpy来进行修改

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

需要特殊注意的是，这里是size+1

2>string(const string& s)

前面那个其实还好，但是对于拷贝构造函数就要小心了。它必须得换了

下面是我们之前写的

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

我们试想一下，如果不换的话，一旦出现’\0’字符，那么后面的一部分全都出现问题了。

所以我们得用memcpy

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

2.对reserve的修改

下面是我们之前的函数，可见实际上是存在很多问题的

void reserve(size_t n)
    {
      if (n > _capacity)
      {
        char* tmp = new char[n + 1];
        strcpy(tmp, _str);
        _capacity = n;
        delete[] _str;
        _str = tmp;
      }
    }

我们修改后的为

void reserve(size_t n)
    {
      if (n > _capacity)
      {
        char* tmp = new char[n + 1];
        //strcpy(tmp, _str);
        memcpy(tmp, _str, _size + 1);
        _capacity = n;
        delete[] _str;
        _str = tmp;
      }
    }

3.append的修改

这是原来的，虽然确实没有什么太大的影响，但是我们为了统一还是进行处理一下

void append(const char* str)
    {
      int len = strlen(str);
      if (len + _size > _capacity)
      {
        int newcapacity = (len+_size) ;
        reserve(newcapacity);
      }
      //while (len--)
      //{
      //  _str[_size++] = *str++;
      //}
      //_str[_size] = '\0';
      strcpy(_str + _size, str);
      _size += len;
    }

处理后为

void append(const char* str)
    {
      int len = strlen(str);
      if (len + _size > _capacity)
      {
        int newcapacity = (len+_size) ;
        reserve(newcapacity);
      }
      //while (len--)
      //{
      //  _str[_size++] = *str++;
      //}
      //_str[_size] = '\0';
      //strcpy(_str + _size, str);
      memcpy(_str + _size, str, len+1);
      _size += len;
    }

4.对于迭代器的修改

这是我们原来的迭代器代码

//迭代器
    typedef char* iterator;
    iterator begin()
    {
      return _str;
    }
    iterator end()
    {
      return _str + strlen(_str);
    }
    //const 迭代器
    typedef const char* const_iterator;
    const_iterator begin() const
    {
      return _str;
    }
    const_iterator end() const
    {
      return _str + strlen(_str);
    }

修改后为

typedef char* iterator;
    iterator begin()
    {
      return _str;
    }
    iterator end()
    {
      //return _str + strlen(_str);
      return _str + _size;
    }
    //const 迭代器
    typedef const char* const_iterator;
    const_iterator begin() const
    {
      return _str;
    }
    const_iterator end() const
    {
      //return _str + strlen(_str);
      return _str + _size;
    }

十三、流提取

经历了前面修改后的bug以后，我们在回过头来继续实现流提取

我们先看如下代码

istream& operator>>(istream& in, string& s)
  {
    s.clear();
    char ch = in.get();
    while (ch == ' ' || ch == '\n')
    {
      ch = in.get();
    }
    while (ch != ' ' && ch != '\n')
    {
      s += ch;
      ch = in.get();
    }
    return in;
  }

这段代码是可以实现我们的目的，首先我们知道我们得先清楚之前s中的数据，否则插入就有问题。会保留原来的数据

其次，我们输入的时候需要用in.get()这个函数，必须用这个，如果我们使用的是in的话，它本身就是无法读取空格和‘\n’的，因为这两个字符被用作分隔符，分割读取的数据。故后面的条件恒成立或恒不成立。而get是可以读取这两个字符的

然后我们用一个循环，先清除一开始可能会输入的分隔符。清楚了一开始的分隔符以后，我们就开始读取数据，我们可以直接调用+=这个运算符重载。当遇到分隔符的时候结束读取即可

同样的这个代码假如我们想要改为getline也是很容易的，我们直接将空格这个标识符删掉即可。

上面的代码虽然也确实可以解决问题，但由于我们连续的使用+=这个函数，我们需要不断的进行扩容，这是一种极大的消耗。我们也不能一开始直接对其扩容很大，这样是伤敌一千自损八百的策略

为了解决这个问题，我们可以这样做

istream& operator>>(istream& in, string& s)
  {
    s.clear();
    char ch = in.get();
    while (ch == ' ' || ch == '\n')
    {
      ch = in.get();
    }
    char buff[128] = { 0 };
    int i = 0;
    while (ch != ' ' && ch != '\n')
    {
      //s += ch;
      buff[i++] = ch;
      if (i == 127)
      {
        buff[i] = '\0';
        s += buff;
        i = 0;
      }
      ch = in.get();
    }
    if (i != 0)
    {
      buff[i] = '\0';
      s += buff;
    }
    return in;
  }

在栈上运用一个buff数组，这个数组它起到一个缓冲的作用，先将数据都存到这个数组里面，当这个数组存满的时候，一次性将数据全部给s，然后结束的时候如果还有数据，那么也将他给放进去即可。这样的代价就很小了

【C++从0到王者】第十站：手撕string（上）