【C++】深度剖析string类的底层结构及其模拟实现（二）
7. 数据插入删除及扩容操作
然后我们来实现一下push_back()，那就是尾插一个字符嘛。
那大家想插入数据的话是不是要考虑扩容啊。
那插入数据的接口除了push_back() ，是不是还有append()啊，append()可以在string对象后面追加字符串，那也需要考虑扩容。
那大家想一下，如果扩容的话，我们一次扩多少呢？
还像之前写的顺序表一样扩二倍可以吗？
对于push_back()来说一次扩二倍应该没问题，但是append()还一次扩二倍是不是有可能不行啊。
为什么？
你想如果当前的容量是10，现在追加一个长度为25的字符串，你扩容到原来的两倍才20，是不是也不够用啊。
那我们这里可以怎么扩呢？
🆗，string是不是还有一个成员函数叫做reserve啊，它可以改变容量为我们指定的大小，帮助我们扩容。
但是，我们是不是还没实现它。
7.1 reserve
所以：
我们先来实现一下reserve：
注意不能先释放旧空间，因为我们还要把旧空间的数据拷贝到新空间。
这就是我们的reserve。
大家看一下，我们的这个reserve有什么问题没有？
🆗，如果我们参数n的值小于_capacity，这里是不是就真的缩容去了，重新开一块小空间，拷贝原来的数据，释放旧空间。
但是我们说了，一般是不会轻易缩容的，标准库里string的reserve其实就不会缩的，我们可以看一下：
是不是没有啊。
那我们自己实现的这个呢？
我们也来测试一下，当然我们还没有实现capacity()这个接口，实现一下：
来看：
我们的确实缩了，但是程序也崩了。
为什么呢？
那我们通过调式一步步走其实可以推测出它应该是在析构的时候报错了。
那原因出在哪里呢？
来看，如果n小于_capacity的话，这里会缩容，先开一块比原来小的空间，然后把原来的数据拷贝过去，但是，空间变小了，还能放的下原来的内容吗？
是不是就不能了，但是strcpy是遇到\0才停止，所以这里就越界了。
所以这里如果要拷贝的话是不是应该用strncpy，不能全拷，但是我们说了一般不缩容，库里面的就没缩，所以这里我们加一个判断：
n > _capacity才做处理。
小的话我也不缩。
但是其实这里还是有一个问题的，我们后面再说。
7.2 push_back和append
那reverse搞好了，我们就可以继续实现push_back()和append()了：
那在判断之后，需要扩容我们就扩容，然后我们插入数据就行了：
那push_back()我们这里就选择扩两倍。
另外给大家提一下我们这里选择用strcpy而没有用strcat，这里不推荐使用strcat，当然strcat也是可以完成的。
那为什么不推荐呢？
因为strcat追加字符串的时候是需要自己从头去找被追加字符串的
\0，然后从\0开始追加新的串。而我们这里明确知道\0的位置，
_str + _size就是\0的位置，用strcpy就直接把这个位置传给它直接开始追加了。
🆗，那我们来测试一下：
没什么问题。
7.3 +=
虽然有push_back和append，但是我们说了，我们一般不喜欢用它们两个。
因为string还重载了+=，用起来就非常香，尽管+=的底层也是去调push_back和append。
🆗，我们来实现一下：
很简单
来测试一下：
没问题。
7.4 resize
然后我们来实现一下resize：
resize就是扩容加初始化，我们可以自己指定要初始化的字符，不指定默认填\0。
那这里是不是也分几种情况啊：
首先第一种情况n小于_size，那是不是要删除数据啊，只保留前n个，怎么做？
是不是直接把第n个位置置成\0就行了：
当然等于也可以走这里（等于其实可以不做处理）。
然后就是n>_size ，但是大于也分两种情况，n在_size和_capacity之间以及n>_capacity两种：
n在_size和_capacity之间的话，之间插入数据就行了，如果n>_capacity，那就要先扩容，然后再插入数据。
测试一下：
没问题。
7.5 insert
我们先来实现一下insert，当然库里面提供好多个版本，我们不可能全部实现。
首先我们来实现一下在pos位置插入一个字符
怎么写，思考一下：
逻辑是不是很简单啊，首先判断一下，需要扩容的话要进行扩容，然后就去插入数据就行了嘛，如果往中间插的话挪动数据就行了嘛，跟我们之前实现顺序表的insert一样嘛
就写好了，有没有什么问题呢？测试一下：
可以，但是，这样呢？
在下标为0的位置再插入一个*，发现程序挂掉了，怎么回事呢？
大家思考一下，为什么？
当然库里面的肯定是没问题的，不过库里面的跟我们实现的这个还有一点差异：
库里面指定位置插入字符的话还有一个参数n指定插入的个数，直接插入一个的是传迭代器，所以这里我们没有完全跟着标准库走。
那我们这里为什么在下标0位置插入就崩了呢？
当pos为0时，end等于0时还会进入循环,end再- -变成多少？
是-1吗？
这里end的类型是szie_t，无符号整型，所以这里end为0后再- -并不是-1，而是整型最大值，那就越界了，循环也没正常结束，所以程序崩了。
那怎么解决？
把end的类型变成int？
🆗，这里变成int也不行，为什么？
这就用到我们C语言学过的知识了
end和pos比较，就算把end变成int，但是pos是不是size_t类型啊，那这里是不是会发生算术转换啊。
end 还是会变成size_t。
那怎么搞？在参数列表把pos的类型也改成int？
确实可以了，但是我们还是不要这么搞吧！
我们看到表示下标一般都是size_t。
那我们这里呢这样来解决：
刚才是>=，end减到-1才结束，那我们改成>，那到0就结束了，就不会出现刚才的情况了。
但是，这时我们要让end的初始值为_size + 1，然后依次把end - 1位置的元素挪到end。
然后我们测试一下：
就可以了。
那刚才是插入一个字符，现在我们再来实现一个插入字符串的：
那逻辑是不是跟上面插入一个一样啊，只不过上面我们只需要挪出一个空间就可以了，那这里我们是不是需要挪动数据腾出strlen(str)个空间啊。
给大家画个图：
理清思路，代码就简单了：
仔细观察我们会发现把这里的len换成1就和上面那个insert的循环控制一样了。
我们来测试一下：
没问题。
当然这只是一种写法，大家有自己的想法，只要能实现也可以。
当然：
现在我们的insert实现之后，前面的push_back和append是不是就可以复用它了。
7.6 erase
那接着我们来实现一下erase，从pos位置开始删除len个字符：
那这里的len呢我们看到有一个缺省值：
npos，npos是啥呢：
🆗，它是一个const静态成员变量，值为-1，但是呢，因为这里它的类型是size_t（无符号整型），所以它在这里其实是整型的最大值。
那在这里就要给大家提一个东西：
我们知道C++11开始支持类的成员变量在声明的时候给缺省值，但是呢有个前提，必须是非静态成员变量才可以在类中声明的时候可以给缺省值。
静态成员变量是不能在声明时给缺省值的，这个我们在之前类和对象的文章里也有讲解过。
我们说了对于静态成员变量：规定静态成员变量的初始化（定义的时候赋初值）一定要在类外，定义时不添加static关键字，类中只是声明。
正常应该这样写。
不过呢，我们看到库里的npos还加了const：
那加const就加嘛？但是呢，加了const之后：
这样直接给缺省值就可以了，又不报错了。
而且呢，这样的写法，这种语法呢，还只支持整型：
所以，这个地方就感觉有点怪啊。
好吧，那这个大家就了解一下，我们还是按正常的写法好吧：
那我们来实现一下erase：
🆗，那这里是不是也分这样几种情况啊：
首先第一种情况就是pos+len小于字符串的长度，那我们是不是要把pos位置开始的后len个字符删掉，但是后面的还要保留啊。
那这种情况怎么做？
是不是挪动后面的数据，把需要删除的覆盖掉就行了啊。
那其它的情况就是给的len比较大，pos+len直接大于等于字符串的长度了，那就把pos后面的全部删掉。
或者就是没有传pos这个参数，缺省值npos，那也要把后面的全删，所以这两种情况可以统一处理。
怎么做？直接把pos位置置成\0是不是就🆗 了。
我们来写一下代码：
就写好了。
测试一下：
没什么问题。
不过呢：
标准库里string的insert和erase最后都返回了对象的引用，那我们也可以加一下。
8. swap和find
然后我们在来实现一下string的swap：
那我们在之前讲解string使用的文章里也说了，对比算法库里的swap，string：：swap的效率是更高一点的，也给大家简单的解释了原因，那这下我们实现之后相信大家就理解的更透彻了。
来，写一下：
直接使用算法库里的swap去交换成员变量。
简单测试一下：
然后我们实现一下find：
那find是不是也很简单啊，我们去遍历找就行了嘛，找到了就返回下标，找不到返回npos。
当然库里面string的find还有一个参数pos，就是支持从pos位置开始向后找，pos缺省值为0
另外记得加个断言判断pos是否合法。
那这样就行了嘛。
那除此之外find还支持从pos位置开始查找一个字符串：
我们来实现一下，是不是可以考虑直接复用C语言里面的
strstr去找啊。
写一下：
由于strstr返回的是地址，这里我们可以通过指针-指针的方式得到它的位置。
那我们来简单测试一下：
9. 流插入<< 和 流提取>>重载
9.1 流插入<<重载
先来重载一下流插入<<：
那不知道大家还记不记得，之前我们学习类和对象的时候不是练习过一个日期类嘛，日期类里面我们也重载了流插入和流提取，但是我们讲到我们自己重载的如果想像正常cout打印那样用的话，要把流插入<< 和 流提取>>重载到类外面，因为this指针会抢占第一个参数的位置，但正常的话应该是让cout是第一个参数。
那我们来写一下代码，那我们在函数内部是不是直接遍历打印就行了：
这样就行了，参数out接收cout，s接收我们要打印的string对象。
当然这里不能用out<
打印c_str返回的const char*的指针，它是遇到’\0’就停止了。所以大家可以理解成c_str就是返回C格式字符串。
而我们打印string对象应该是看s对应的size 的，size是多大，总共有多少字符，全部打印完。
注意这两种方式的区别。
测试一下：
9.2 reverse修改
然后：
上面我们实现reverse的时候最后不是还留了一个问题嘛，我们说之前的实现还是有点问题的，什么问题呢？
来看，对于我们上面实现的reverse如果是这种情况：
这里怎么出现乱码了呢？
🆗，因为我们之前实现的reverse用的strcpy
它拷贝到\0就结束了，但是我们这里的s1\0后面是不是还有有效字符啊，所以\0后面放的就是随机值，但是打印又是按照size去打印的，所以就打印出了乱码。
所以不能用strcpy，要按照size的大小去拷贝数据：
可以使用memcpy。
这下就可以了。
9.3 流提取>>重载
那接着我们再来重载一下流提取：
那就可以这样搞：
用一个循环，一个字符一个字符的去缓冲区里提取，然后插入到s里，遇到空格或者换行就停止。
试一下：
但是我们发现好像有点不对劲啊，为什么不行啊？
🆗，原因在于cin呢它读不到缓冲区里的空格和换行，为什么读不到呢？
之前也提到过，C语言里的scanf，包括这里的cin，我们在用它们输入的时候是不是有可能输入多个值啊，那当我们输入多个值的时候，它们默认是以空格或者换行来区分我们输入的多个值的。
所以它遇到缓冲区里的空格或者换行的时候，它会认为这是你输入多个值的一个区分，会自动忽略掉它们，不会去提取，所以这里就读不到空格和换行，那循环就不会结束。
那要怎么解决呢？
我们可以用这个：
get是istream类的一个成员函数，它一次读取一个字符，就可以提取到空格和换行。
再来测试一下：
就可以了。
但是如果是这种情况呢：
string对象原来就有数据，看一下库里的实现：
是不是要把之前的数据清掉啊。
那怎么清除一个string对象？
是不是用clear啊
那我们先实现一下clear：
非常简单。
再来试一下：
就好了。
那还有没有什么其它的问题？
🆗，如果我们输入一个特别长的字符串，那这个地方在不断+=字符的过程中是不是可能会频繁扩容啊，那我们有没有什么办法可以解决一下呢？
首先这里解决的方法肯定不是唯一的：
那库里面呢用了一种类似于这样的方式：
这里开了一个数组，每次先把字符一个个放到数组中，满了的话就+=到s里（以字符串的形式），然后把i置成0，后面继续放数组里。
那这样做相对而言扩容就不会那么频繁了。
当然，如果输入结束buff数组没满，那就把里面有多少数据就+=多少。
那buff数组的大小大家也可以自己调整。
🆗，那我们string的模拟实现差不多就到这里：
当然实际库里面string提供的接口是很多的，我们不可能全部实现完，而且有的基本不怎么用，还有的虽然没实现，但是想要实现也很简单，我们带这大家一起实现的都是一些比较重要和常用的。
那这里模拟实现最重要的目的呢，其实还是让大家更好的理解string，同时也作为一个练习。
10. 写时拷贝(了解)
最后我们再来了解一个东西叫做写时拷贝：
大家说这里打印出来的大小是多少？
是28，为什么是28呢？
🆗，这个我们在string的使用那篇文章是不是给大家解释过啊。
vs上在这里做了一个优化，多开了一个大小为16的数组，这样如果字符串比较短的话就不用去堆上申请空间了，直接存到这个数组里。
那大家知不知道G++下面一个string对象的大小是多少？
G++下，string是通过写时拷贝实现的，string对象总共占4个字节（32位平台下，64位下8个字节），内部只包含了一个指针。
那只有一个指针，它具体是怎么实现的呢？
该指针指向一块堆空间，内部包含了如下字段：
空间总大小
字符串有效长度
引用计数
指向堆空间的指针，用来存储字符串
比如我们现在有一个string对象s1，那它大概是这样一个样子：
那写时拷贝又是什么东西呢？
如果现在又有一个s2是s1拷贝构造出来的，我们vs上面是深拷贝。
vs是PJ版本STL，g++是SGI版本STL。
而Linux的G++（采用的是SGI版本）下面是写时拷贝：
写时拷贝就是一种拖延症，是在浅拷贝的基础之上增加了引用计数的方式来实现的。
引用计数：用来记录资源使用者的个数。在构造时，将资源的计数给成1，每增加一个对象使用该资源，就给
计数增加1，当某个对象被销毁时，先给该计数减1，然后再检查是否需要释放资源，如果计数为1，说明该对象是资源的最后一个使用者，将该资源释放；否则就不能释放，因为还有其他对象在使用该资源。
此时只有s1一个对象使用这块资源，引用计数就是1 。
现在如果有s2是s1的拷贝，那这里是一个浅拷贝，只是把引用计数加1，表示现在有两个对象使用这块资源。
那释放的时候怎么办呢？
🆗，释放s2的时候，就把引用计数减1，而不是真的释放这块空间，等到s1释放的时候，引用计数为1，表示只有一个对象使用这块资源，就可以释放了。
那这个地方是不是不拷贝啊？
不是的，写时拷贝，写时拷贝，就是写的时候才拷贝。
还拿上面那个例子来说，如果s2只是拷贝s1，我们并没有修改s2，那它们两个就可以共用一块空间，如果我们去修改了s2的内容，那这个时候才会进行真正的拷贝，为s2开一块独立的空间，然后把s1的内容拷贝下来，然后你要修改数据就在你自己的这块空间上进行修改。
修改数据才会触发写时拷贝（Copy-On-Write），不修改当然就不会改。这就是托延战术的真谛，非到要做的时候才去做。
11. 源码展示
string .h
#pragma once
#include <assert.h>
namespace yin
{
class string
{
public:
typedef char* iterator;
typedef const char* const_iterator;
iterator begin()
{
return _str;
}
iterator end()
{
return _str + _size;
}
const_iterator begin()const
{
return _str;
}
const_iterator end()const
{
return _str + _size;
}
/*string()
:_str(new char[1])
,_size(0)
,_capacity(0)
{
_str[0] = '\0';
}*/
//构造函数
//string(const char* str = nullptr)//不可以
//string(const char* str = '\0')
string(const char* str = "")
:_size(strlen(str))
{
_capacity = _size;
_str = new char[_capacity + 1];
strcpy(_str, str);
}
//拷贝构造
string(const string& s)
:_size(s._size)
,_capacity(s._capacity)
{
_str = new char[s._capacity + 1];
strcpy(_str, s._str);
}
//赋值重载
string& operator=(const string& s)
{
if (this != &s)
{
/*delete[] _str;
_str = new char[s._capacity + 1];
strcpy(_str, s._str);
_size = s._size;
_capacity = s._capacity;*/
char* tmp = new char[s._capacity + 1];
strcpy(_str, s._str);
delete[] _str;
_str = tmp;
_size = s._size;
_capacity = s._capacity;
}
return *this;
}
bool operator>(const string& s)const
{
return strcmp(_str, s._str) > 0;
}
bool operator==(const string& s)const
{
return strcmp(_str, s._str) == 0;
}
bool operator>=(const string& s)const
{
//return *this > s || *this == s;
return *this > s || s == *this;
}
bool operator<(const string& s)const
{
return !(*this >= s);
}
bool operator<=(const string& s)const
{
return !(*this > s);
}
bool operator!=(const string& s)const
{
return !(*this == s);
}
void reserve(size_t n)
{
if (n > _capacity)
{
char* tmp = new char[n + 1];//多开一个给\0
memcpy(tmp, _str, _size);
//strcpy(tmp, _str);错误，不能用strcpy
delete[] _str;
_str = tmp;
_capacity = n;
}
}
void resize(size_t n, char ch = '\0')
{
if (n <= _size)
{
_size = n;
_str[_size] = '\0';
}
else
{
if (n > _capacity)
reserve(n);
size_t i = _size;
while (i < n)
{
_str[i] = ch;
++i;
}
_size = n;
_str[_size] = '\0';
}
}
void push_back(char ch)
{
/*if (_size + 1 > _capacity)
{
reserve(_capacity == 0 ? 4 : _capacity * 2);
}
_str[_size] = ch;
_size++;
_str[_size] = '\0';*/
insert(_size, ch);
}
void append(const char* str)
{
/*size_t len = strlen(str);
if (_size + len > _capacity)
{
reserve(_size + len);
}
strcpy(_str + _size, str);
_size += len;*/
insert(_size, str);
}
string& operator+=(char ch)
{
push_back(ch);
return *this;
}
string& operator+=(const char* str)
{
append(str);
return *this;
}
string& insert(size_t pos, char ch)
{
assert(pos <= _size);
//扩容
if (_size + 1 > _capacity)
{
reserve(_capacity == 0 ? 4 : _capacity * 2);
}
//挪动数据
size_t end = _size + 1;
while (end > pos)
{
_str[end] = _str[end - 1];
--end;
}
//插入数据
_str[pos] = ch;
++_size;
return *this;
}
string& insert(size_t pos, const char* str)
{
assert(pos <= _size);
size_t len = strlen(str);
//扩容
if (_size + len > _capacity)
{
reserve(_size + len);
}
//挪动数据
size_t end = _size + len;
while (end > pos + len - 1)
{
_str[end] = _str[end - len];
--end;
}
//插入数据
strncpy(_str+pos, str, len);
_size += len;
return *this;
}
string& erase(size_t pos = 0, size_t len = npos)
{
assert(pos < _size);
if (len == npos || pos + len >= _size)
{
_str[pos] = '\0';
_size = pos;
}
else
{
strcpy(_str + pos, _str + pos + len);
_size -= len;
}
return *this;
}
void swap(string& s)
{
std::swap(_str, s._str);
std::swap(_size, s._size);
std::swap(_capacity, s._capacity);
}
size_t find(char ch, size_t pos = 0)
{
assert(pos < _size);
for (size_t 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* p = strstr(_str + pos, str);
if (p == nullptr)
return npos;
else
return p - _str;
}
//析构
~string()
{
delete[] _str;
_str = nullptr;
_size = _capacity = 0;
}
const char* c_str()
{
return _str;
}
const char& operator[](size_t pos)const
{
assert(pos < _size);
return _str[pos];
}
char& operator[](size_t pos)
{
assert(pos < _size);
return _str[pos];
}
size_t size()const
{
return _size;
}
size_t capacity()const
{
return _capacity;
}
void clear()
{
_str[0] = '\0';
_size = 0;
}
private:
char* _str;
size_t _size;
size_t _capacity;
static const size_t npos;
};
const size_t string::npos = -1;
ostream& operator<<(ostream& out, const string& s)
{
for (auto e : s)
out << e;
return out;
}
istream& operator>>(istream& in, string& s)
{
s.clear();
char ch = in.get();
char buff[128];
size_t i = 0;
while (ch != ' ' && ch != '\n')
{
buff[i++] = ch;
if (i == 127)
{
buff[127] = '\0';
s += buff;
i = 0;
}
ch = in.get();
}
if (i != 0)
{
buff[i] = '\0';
s += buff;
}
return in;
}
}
test.cpp
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
#include "string.h"
//int main()
//{
// yin::string s1("hello world");
// yin::string s2(s1);
//
// cout << s1.c_str() << endl;
// cout << s2.c_str() << endl;
//
// yin::string s3;
// s1 = s1;
// cout << s1.c_str() << endl;
// cout << s3.c_str() << endl;
// return 0;
//}
void Print(const yin::string& s)
{
for (auto e : s)
cout << e << " ";
cout << endl;
}
//int main()
//{
// yin::string s1("hello world");
// for (yin::string::iterator it = s1.begin(); it != s1.end(); it++)
// {
// (*it)='*';
// }
// for (auto e : s1)
// cout << e << " ";
// cout << endl;
// /*for (yin::string::iterator it = s1.begin(); it != s1.end(); it++)
// {
// cout << *it << " ";
// }*/
// cout << endl;
// Print(s1);
// return 0;
//}
//int main()
//{
// yin::string s1("hello word");
// yin::string s2("xxxxxxxxxxxx");
// cout << (s1 > s2) << endl;
// cout << (s1 == s2) << endl;
// cout << (s1 < s2) << endl;
//
// return 0;
//}
//int main()
//{
// yin::string s1("hello world");
// s1.push_back('X');
// s1.append("*************");
//
// /*s1 += 'x';
// s1 += "***********";*/
// cout << s1.c_str() << endl;
// return 0;
//}
//int main()
//{
// yin::string s("hello world");
// //s.insert(5, '*');
// s.insert(5, "***");
// cout << s.c_str() << endl;
//
// //s.insert(0,'*');
// s.insert(0,"xxxxxxxxxxxxxx");
// cout << s.c_str() << endl;
// return 0;
//}
//int main()
//{
// yin::string s("hello word*****************");
// cout << s.capacity() << endl;
// s.reserve(10);
// cout << s.capacity() << endl;
//
// return 0;
//}
//int main()
//{
// yin::string s;
// s.resize(20, '*');
// cout << s.c_str() << endl;
// s.resize(30, 'x');
// cout << s.c_str() << endl;
// s.resize(10);
// cout << s.c_str() << endl;
//
// return 0;
//}
//int main()
//{
// yin::string s("0123456789");
// cout << s.c_str() << endl;
// s.erase(4, 3);
// cout << s.c_str() << endl;
// s.erase(4, 30);
// cout << s.c_str() << endl;
// s.erase(2);
// cout << s.c_str() << endl;
// return 0;
//}
//int main()
//{
// yin::string s1("hello world");
// yin::string s2("yhq dyf");
// s1.swap(s2);
// cout << s1.c_str() << endl;
// cout << s2.c_str() << endl;
//
// return 0;
//}
//int main()
//{
// yin::string s1("hello world");
// s1 += '\0';
// s1 += "xxxxxxxx";
//
// cin >> s1;
// cout << s1<< endl;
//
// /*yin::string s1("hello world");
// s1 += '\0';
// s1 += "xxxxxxxx";
// cout << s1 << endl;
// s1.reserve(50);
// cout << s1 << endl;*/
//
// return 0;
//}
int main()
{
string s;
cout << sizeof(s) << endl;
return 0;
}
🆗，那这篇文章的内容就先到这里，欢迎大家指正！！！
- 点赞
- 收藏
- 关注作者
评论（0）