【C++从0到王者】第十站:手撕string(上)

简介: 【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次。这样我们九获取了我们希望获得的子串,我们现在返回它即可

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

  1. 我们在定义这个空串的时候,不能将其设置为静态的。因为静态的串只会定义一次。以后再次调用这个函数是会出现问题的
  2. 我们的返回值不可以是引用返回,因为我们返回的串出了作用域就不在了
  3. 这个函数必须得有拷贝构造函数,因为其必须为传值返回。且该串涉及到开空间的问题,我们必须得自己写一个深拷贝构造。否则会对同一块空间调用两次析构函数而产生错误
//提取出指定位置的串
    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,然后结束的时候如果还有数据,那么也将他给放进去即可。这样的代价就很小了

相关文章
|
2月前
|
C++ 容器
【c++】string类的模拟实现--1
【c++】string类的模拟实现--1
|
2月前
|
C++
c++:string相关的oj题(把字符串转换成整数、344.反转字符串、387. 字符串中的第一个唯一字符、917. 仅仅反转字母)
c++:string相关的oj题(把字符串转换成整数、344.反转字符串、387. 字符串中的第一个唯一字符、917. 仅仅反转字母)
47 0
|
2月前
|
C++ 索引
c++:string相关的oj题(415. 字符串相加、125. 验证回文串、541. 反转字符串 II、557. 反转字符串中的单词 III)
c++:string相关的oj题(415. 字符串相加、125. 验证回文串、541. 反转字符串 II、557. 反转字符串中的单词 III)
38 0
|
1天前
|
算法 Linux C语言
【c++】string
【c++】string
6 1
|
10天前
|
存储 编译器 C++
C++:STL - string
C++:STL - string
48 1
|
2月前
|
存储 Linux C语言
C++STL——string类详解及其模拟实现
C++STL——string类详解及其模拟实现
|
2月前
|
存储 算法 C++
【C++入门到精通】C++入门 —— string类(STL)
前面我们讲了C语言的基础知识,也了解了一些数据结构,并且讲了有关C++的命名空间的一些知识点以及关于C++的缺省参数、函数重载,引用 和 内联函数也认识了什么是类和对象以及怎么去new一个‘对象’,也相信大家都掌握的不错,接下来博主将会带领大家继续学习有关C++比较重要的知识点——STL(string类)
56 0
|
2月前
|
C语言 C++ 容器
【C++学习手札】模拟实现string
【C++学习手札】模拟实现string
|
2月前
|
C++ 容器
【c++】string类的模拟实现--2
【c++】string类的模拟实现--2
|
2月前
|
存储 C语言 C++
【C++】string类的接口综合运用--2
【C++】string类的接口综合运用--2