C++基础 [五] - String的模拟实现
目录
前言
成员函数的实现
构造函数的实现
拷贝构造函数
析构函数的实现
元素访问的实现
operator[ ]
Iterator - 迭代器
容量大小的实现
size
capacity
reserve
resize
内容修改的实现
push_back
append
operator+=(char ch)
operator+=(const char* s)
insert
erase
内容查找的实现
find - 字符
find - 字符串
substr
非成员函数的重载
小于
等于
小于等于
大于
大于等于
不等于
前言
本模块呢,我将会带大家一起从 0~1去模拟实现一个STL库中的 string类,当然模拟实现的都是一些常用的接口,以便于让大家更好的巩固之前学习过的 缺省参数、封装、类中的6大默认成员函数等
成员函数的实现
首先想,对于一个自定义函数,在调用的时候第一步是干嘛呢?答案肯定是我们之前讲到的,默认成员函数的实现。因为我们是模拟实现的string,也就是说库里面已经有了,所以我们要加上namespace,防止跟库文件发生冲突。
构造函数的实现
我们先回想一下,string函数都要干嘛呢?首先肯定是要有数据,然后也要保存数据的空间,最后也要有个大小用于计算数据的多少。所以我们的成员变量就是 char* _str; size_t _size; size_t _capacity;
能不能这样初始化呢?获取到char*的str之后,初始化_str;答案是不能的,1.因为你的成员变量_str是char*类型的,构造函数的形参是const类型的,会涉及到权限的放大 2.万一你传的是个常量字符串,也就是不能修改的,所以我们要去开空间初始化。 我们之前也说过要尽量用初始化列表去初始化。
我们同学可能就是这样想的,先去读字符串的大小,然后再进行计算容量,最后计算完再开空间
可是我们运行之后就报错了呀,这是为什么呢?
我们会发现这个地址为啥是错的呢?
这有个之前的问题,初始化列表初始化的顺序是按照成员变量的顺序,而不是初始化列表写的顺序。
也就是说,它会先去走 _str(new char[strlen(str)+1]),而此时capacity还没初始化,就是个随机值,要是很大的话,这个new就会崩掉的了。这里有两种改法。1.让顺序保持一致
接着开了空间之后,我们就要把值拷进来了。
此时我们就发现可以了。
注意:此写法有个大坑,就是成员变量的顺序要声明正确!
2.就是把内置类型_size,_capacity 放到函数里面去初始化
拷贝构造函数
我们有提到过若是一个类在没有显示定义拷贝构造对于内置类型不做处理,而对于自定义类型会去调用 类中默认提供的拷贝构造函数 此时就会造成浅拷贝的问题
- 浅拷贝:拷贝出来的目标对象的指针和源对象的指针指向的内存空间是同一块空间。其中一个对象的改动会对另一个对象造成影响。
- 深拷贝:深拷贝是指源对象与拷贝对象互相独立。其中任何一个对象的改动不会对另外一个对象造成影响。
很明显,我们并不希望拷贝出来的两个对象之间存在相互影响,因此,我们这里需要用到深拷贝。下面提供深拷贝的两种写法:
写法一:传统写法
传统写法的思想简单:先开辟一块足以容纳源对象字符串的空间,然后将源对象的字符串拷贝过去,接着把源对象的其他成员变量也赋值过去即可。因为拷贝对象的_str与源对象的_str指向的并不是同一块空间,所以拷贝出来的对象与源对象是互相独立的
//拷贝构造
string(const string& s)
{
_str = new char[s._capacity + 1];
strcpy(_str, s._str);
_size = s._size;
_capacity = s._capacity;
}
- 通过调试再去观察的话,我们可以发现,此时 对象
s1
和 对象s2
中的数据存放在不同的空间中,此时去修改或者是析构的话都不会受到影响
写法二:现代写法
现代写法与传统写法的思想不同:先根据源字符串的C字符串调用构造函数构造一个tmp对象,然后再将tmp对象与拷贝对象的数据交换即可。拷贝对象的_str与源对象的_str指向的也不是同一块空间,是互相独立的。
//拷贝构造
string(const string& s)
:_str(nullptr)
, _size(0)
, _capacity(0)
{
string tmp(s._str); //调用构造函数,构造出一个C字符串为s._str的对象
swap(tmp); //交换这两个对象
}
析构函数的实现
我们要析构,就是要把类中的数据给清除了。那什么才是我们需要清楚的呢?也就是这三个char* _str; size_t _size; size_t _capacity;
这里的顺序不需要进行刻意,因为大小和容量并不是存在delete释放的是_str所指向的内存块
它们是存在栈内存中的
目前我们看数据都是再调试窗口查看的,为了更方便些,我们先定义个c_str,直接返回const char*类型的_str;
const char* c_str() const
{
return _str;
}
这里建议加个const,表示 该成员函数不会修改类的成员变量 为什么要加const呢?const对象调const可以达到一个平传的效果。修饰的是this指针指的对象。权限不能放大但是可以缩小
此时我们就可以打印数据了
但是我们有时候也需要个无参的构造,然后再进行增加修改的操作。
默认构造函数包括三种,1.我们不写,编译器自动生成的。2.全缺省的 3.无参的。这里我们写个无参的,那该怎么写呢?我们能不能这样写?
答案是不能的,如果我们这样给_str空的话,那c_str就悬空了,此时返回个空指针那不是就崩了吗?那该怎么做呢?
我们观察库里的string,即便是空的也会有个'\0'
所以我们要对_str先开个空间,然后再给个'\0',注意这里不是"\0",不是字符串\0,而是字符\0
此时,我们说能不能合并下呢?用全缺省的,那这两种写法你们觉得可以吗?
答案是都不能,第一个是类型不匹配。一个是字符,一个是字符串指针
第二个不能给空,如果给空了之后,_size(strlen(str)) 就会崩了
最优写法是这样的
常量字符串默认是有"\0"的。
元素访问的实现
operator[ ]
operator有两种形式,1.可读可写 2.只读
首先最常用的就是这【下标 + [ ]】的形式去进行一个访问,那很简单,我们通过当前所传入的下标值去访问对应的数据即可
可读可写的实现
这里我们先用传值返回,看看会有什么问题呢
这里为什么会报错呢?
问题出在代码的 operator[] 函数部分。你正在定义一个 operator[] 来访问 _str 数组的元素,但是函数的返回值是 char 类型,这意味着返回的是一个值,而不是引用。如果你试图修改 s1[i]++ 中的值,这会导致错误,因为 operator[] 返回的是不可修改的副本。
所以这里要换成引用
只读的实现
读写和读的operator构成函数重载,我们可以加入const对权限进行限定
// 可读不可写
const char& operator[](size_t pos) const// 最后也加上const 因为防止该函数对const进行修改
{
assert(pos < _size);
return _str[pos];
}
const加在前面是为了防止返回的数据被修改。const加在后面是为了防止传过来的数据被修改
Iterator - 迭代器
那经过上面的学习我们可以知道,要去遍历访问一个string对象的时候,除了【下标 + []】的形式,我们还可以使用迭代器的形式去做一个遍历,迭代器指向的是位置,而不是数据
- 而对于迭代器而言我们也是要去实现两种,一个是非const的,一个则是const的
- string类中的迭代器实际上就是字符指针,只是给字符指针起了一个别名叫iterator而已。
typedef char* iterator;
typedef const char* const_iterator;
注:不是所有的迭代器都是指针。
我们知道,对于begin来说,也就是_str所指向的的位置,那对于end呢?end的意思是返回最后一个字符的下一个位置。那既然str_是第一个位置,size又是这个数据的大小,那最后一个位置的下一位不就是_str+size吗?
iterator begin()
{
return _str;// 返回指向字符数组起始位置的指针
}
iterator end()
{
return _str + _size;
}
- 实现了普通版本的迭代器之后,我们再来看看常量迭代器。很简单,只需要修改一下返回值,然后在后面加上一个【const成员】,此时就可以构成函数重载了
const_iterator begin() const
{
return _str;
}
const_iterator end() const
{
return _str + _size;
}
范围for的底层实现就是用iterator迭代器实现的
容量大小的实现
size
首先是 size(),这里的话我们直接返回_size
即可,因为不会去修改成员变量,所以我们可以加上一个【const成员】(因为它是不可被修改滴)
size函数用于获取字符串当前的有效长度(不包括’\0’)
size_t size() const
{
return _size;
}
注意:这里的 const 是用来修饰 this指针的
capacity
capacity函数用于获取字符串当前的容量
size_t capacity() const
{
return _capacity;
}
reserve
reserve规则:
- 当扩容n大于对象当前的capacity时,将capacity扩大到n或大于n。
- 当扩容n小于对象当前的capacity时,什么也不做。
很明显,只有当这个 新容量大于旧容量的时候,才会去选择去开空间,这里的扩容逻辑和我们在实现旧版本的拷贝构造函数时类似的:也是先开出一块新的空间(这里主要使用这个newCapacity 去开),然后再将原本的数据拷贝过来,让_str指向新空间然后释放旧空间的数据。最后的话不要忘了去更新一下容量大小
void reserve(size_t newCapacity)// 扩容(修改_capacity)
{
// 当新容量大于旧容量的时候,就开空间
if (newCapacity > _capacity)
{
// 1.以给定的容量开出一块新空间
char* tmp = new char[newCapacity + 1]; //多开一个空间用于存放'\0'
// 2.将原本的数据先拷贝过来
strncpy(tmp, _str, _size + 1); //将对象原本的C字符串拷贝过来(包括'\0')
// 3.释放旧空间的数据
delete[] _str;
// 4.让_str指向新空间
_str = tmp;
// 5.更新容量大小
_capacity = newCapacity;
}
}
不能先赋值再delete _str,这样会把新地址的str给释放掉。
注意:代码中使用strncpy进行拷贝对象C字符串而不是strcpy,是为了防止对象的C字符串中含有有效字符’\0’而无法拷贝(strcpy拷贝到第一个’\0’就结束拷贝了)。
resize
首先我们来分析一下,对于【resize】而言主要对对象中的数据去做一个变化,用于调整字符串的大小。那么该怎么调呢
如果调的大小很大,该考虑什么呢?如果调的很小,又该考虑什么呢?接下来我们就要进行分类讨论了
- 如果这个 newSize < _size 的话,那我们要选择去删除数据
- 如果这个 newSize > _size,但是呢 newSize < _capacity 的话,此时要做的就是新增数据但是呢不去做扩容
- 如果这个 newSize > _size 并且 newSize > _capacity,我们便要选择去进行扩容了
当 _size = 10 , _capacity = 15 时
- 在分析完了之后,我们立即来实现一下相关的代码。可以看到,一上来我就直接去判断了
newSize
是否大于_size
,然后在内部又做了一层判断,只有当newSize > _capacity
时,才去执行【reserve】的扩容逻辑 - 如果
newSize
并没有超过容量大小的话我们要做的事情就是去填充数据,这里用到的是一个内存函数memset- 我们从
_str + _size
的位置开始填充; - 填充的个数是
newSize - _size
个; - 填充的内容是
c
- 我们从
- 若是
newSize <= _size
的话,我们所要做的就是去截取数据,到newSize
为止直接设置一个 \0,然后更新一下当前对象的_size
大小
// 改变大小
void resize(size_t newSize, char c = '\0')
{
// 1.当新的_size比旧的_size来得小的话,则进行删除数据
if (newSize > _size)
{
// 只有当新的size比容量还来的大,才去做一个扩容
if (newSize > _capacity)
{
reserve(newSize);
}
// 如果newSize <= _capacity,填充新数据即可
memset(_str + _size, c, newSize - _size);
}
// 如果 newSize <= _size,不考虑扩容和新增数据
_size = newSize;
_str[newSize] = '\0';
}
有几点是易错的,reserve的时候要扩容到新的newSize,而不是扩容newSize-_size。
内容修改的实现
push_back
首先第一块的话简单一点,我们去追加一个字符,那首先要考虑到的也是一个扩容逻辑,因为我们是一个字符一个字符去进行插入的,那么当这个_size == _capacity的时候,就要去执行一个扩容的逻辑了,这边的话是运用到了这个三目运算符,若是容量的大小为0的话,默认开个大小为4的空间就可以了;其他的情况都是以2倍的形式去进行扩充
最后在扩完容之后我们就在末尾去增加数据了,因为此时_size
指向的就是 \0 的位置,所以就把字符放在这个位置上就可以了,顺带地记得去后移一下这个_size
,再放上一个 \0
// 追加一个字符
void push_back(char ch)
{
// 如果数据量大于容量的话,则需要进行扩容
if (_size == _capacity)
{
reserve(_capacity == 0 ? 4 : _capacity * 2);
}
_str[_size] = ch;
++size;
_str[_size] = '\0';
}
append
接下去的话是【append】,要追加的是一个字符串,所以我们要先去算出它的长度,接下去判断一下在加上这个长度后是否要去做一个扩容,最后的话还是通过我们熟悉的【memcpy】通过字节的形式一一拷贝到_str + _size的位置(注意拷贝len + 1个,带上最后 \0),最后再把大小_size给增加一下即可
// 追加一个字符串
void append(const char* s)
{
int len = strlen(s); // 获取到待插入字符串的长度
// 若是加上len长度后超出容量大小了,那么就需要扩容
if (_size + len > _capacity)
{
reserve(_size + len);
}
// 将字符串拷贝到末尾的_size位置
memcpy(_str + _size, s, len + 1);
// 大小增加
_size += len;
}
注意这里的_size + len > _capacity; 用原来的大小加上新追加的字符串的长度,然后再去和容量去比较
为啥要用c_str打印呢?
因为 c_str()
返回的是 const char*
,即一个 C 风格的字符串指针,表示你的 MyString
对象内部存储的字符数组
operator+=(char ch)
首先的话是去【+=】一个字符,这里我们直接复用前面的push_back()
接口即可,最后因为【+=】改变的是自身,所以我们return *this
,那么返回一个出了作用域不会销毁的对象,可以采取 引用返回 减少拷贝
string& operator+=(char ch)
{
push_back(ch);
return *this;
}
operator+=(const char* s)
而对于【+=】一个字符串,我们则是去复用前面的append()
即可
string& operator+=(const char* s)
{
append(s);
return *this;
}
这里为什么不用char&而是用string&呢
char& 代表一个单个字符的引用,而 operator+= 是一个修改 MyString 对象的操作,而不是修改单个字符
insert
接下去我们就要来实现一下【insert】这个接口了-- 从 pos 位置 开始插入n 个字符
不过在这之前呢我们先要去声明并初始化一个静态的成员变量npos
,它是最大的无符号整数值。但是对于 静态的成员变量 来说我们需要 在类内声明并且在类外进行初始化
// 类内声明
const static size_t npos;
// 类外初始化
const static size_t npos = -1;
首先第一个的话就是要在pos
位置插入n个字符
void insert(size_t pos, size_t n, char ch)
因为这里会传入一个pos
位置,所以第一步我们就是要去考虑这个pos
位置是否合法
assert(pos <= _size);
接下去第二步的话就是去考虑过扩容的问题了,如果_size + n
之后的大小大于_capacity
的话那就要调用【reserve】接口去实现一个扩容的逻辑了
// 考虑扩容
if (_size + n > _capacity)
{
reserve(_size + n);
}
第三步呢并不是直接去插入数据,而是要先给需要插入的n个字符腾出位置。从_size
位置开始,让字符以n个单位地从后往前挪即可,若是从前往后挪的话就会造成覆盖的问题
再次强调,这里是挪动end + n 不是 end + 1个位置
// 挪动数据
size_t end = _size;
while (end >= pos)
{
_str[end + n] = _str[end];
--end;
}
不过呢,我们在这里还要考虑一种极端的情况,如果这个pos == 0的话,也就是在这个位置开始插入数据,那也就相当于头插,此时需要将全部的数据向后进行挪动,可是呢当这个end超出pos的范围时,也就减到了-1,但是呢这个end的数据类型则是【size_t】,为一个无符号整数,我们知道对于无符号整数来说是不可能为负数的,那么这个时候就会发生一个轮回,变成最大的无符号正数
我们可以来看看当这个end
在不断减少直至减到0的时候就会突然变成一个很大的数字,这个其实就是npos
的值了,此时就会造成一个死循环,导致程序崩溃
// 字符插入测试
void test6()
{
xas_string::string s1("abcdefghijk");
s1.insert(0, 3, '#');
cout << s1.c_str() << endl;
}
int main()
{
test6();
return 0;
}
所以我们应该将无符号该有 有符号类型 size_t ----> int
// 挪动数据
int end = _size;
while (end >=(int)pos)
{
_str[end + n] = _str[end];
--end;
}
当这个挪动的逻辑结束后,我们就可以从pos这个位置去插入n个字符了。最后再去更新一下这个_size
的大小即可
// 插入n个字符
for (size_t i = 0; i < n; i++)
{
_str[pos + i] = ch;
}
_size += n;
erase
删除从pos位置开始的len个有效长度字符
- erase函数的作用是删除字符串任意位置开始的n个字符。删除字符前也需要判断pos的合法性,进行删除操作的时候分两种情况:
1.pos位置及其之后的有效字符都需要被删除
- 这时我们只需在pos位置放上’\0’,然后将对象的size更新即可。
2.pos位置及其之后的有效字符只需删除一部分。
这时我们可以用后方需要保留的有效字符覆盖前方需要删除的有效字符,此时不用在字符串后方加’\0’,因为在此之前字符串末尾就有’\0’了。
// 删除 -- 从 pos 位置 删除 长度为 len 的字符串
void erase(size_t pos, 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;
}
}
不建议使用 因为挪动数据代价挺大的
内容查找的实现
find - 字符
这个很简单,就是去遍历一下当前对象中的_str
,若是在遍历的过程中发现了字符ch
的话就返回这个位置的下标,如果遍历完了还是没有找到的话就返回npos
这个最大的无符号数
find - 字符串
我直接使用的是C语言中的库函数 strstr函数详解,这个的话我们在 字符串函数与内存函数解读 的时候也有讲解并模拟过,如果找到了的话就会返回子串第一次出现在主串中的指针。那我们如果要去计算这个指针距离起始位置有多远的话使用指针 - 指针的方式即可。那如果没找到的话我们返回【npos】即可
size_t find(const char* s, size_t pos) const
{
assert(pos < _size);
char* tmp = strstr(_str, s);
if (tmp)
{
// 指针相减即为距离
return tmp - _str;
}
return npos;
}
substr
上面是去匹配子串,现在我们要将这个子串给取出来,要如何去取呢?
首先要考虑的问题是长度的问题,如果我们从pos位置取的子串长度大于剩余子串的长度,那么最多能取得范围也是从pos位置到size_t的位置。所以当取得长度过高的时候,我们就要更新下子串长度的有效范围
- 可以看到,我以这个
n
作为可取的子串长度,一开始得让其等于传入进来的len
长,因为如果这个所取长度没有超出有效范围的话,我们所用的还是len
- 但是如果呢这个长度超出了有效范围后,我们便要去更新这个
n = _size - pos
size_t n = len;
if (len == npos || pos + len > _size)
{
// 就算要取再大的长度,也只能取到pos - _size的位置
n = _size - pos;
}
- 那接下去的话我们就可以去取这个子串了,使用循环的方式从
pos
位置开始取,取【n】个即可,然后追加到这个临时的 string对象 中去,最后呢再将其返回即可,那我们返回一个出了作用域就销毁的临时对象,只能使用【传值返回】,而不能使用【传引用返回】
string substr(size_t pos, size_t len = npos)
{
size_t n = len;
if (len = npos || len + pos > _size)
{
n = _size - pos;
}
string temp;
temp.reserve(n);
for (int i = pos; i < n + pos; i++)
{
temp += _str[i]; //这里用到了操作符重载 //等于是追加的意思
}
return temp;
}
为什么是string类型
substr
需要返回一个新的字符串对象,因为原字符串中的一部分需要作为独立的字符串进行存储和操作。
-
char
类型 是用来存储单个字符的基本数据类型,而std::string
是用来存储多个字符的容器。 -
如果
substr
返回char
,就意味着它只能返回一个单一字符,但实际上我们要提取的是 多个字符(即一个子字符串)。这就不适合用char
类型来返回。
为啥不能temp = _str[i]; temp++;
- 这行代码是递增
temp
,也就是将temp
的值加一。如果temp
是一个字符类型的变量(char
),那么temp++
实际上将其字符值增加一个。 - 但,在这种情况下,
temp++
会使temp
的值变成下一个字符,而不是将字符追加到一个字符串中。
这里i的取值范围为什么是n+pos,为什么不是n?
首先我们要知道i是从pos位置开始的,就好比substr(5,2);指的是从第五个位置,取两个字符串。那你难道就写成i = 5;i < 2吗?这肯定是错误的,应该是pos+n才是最后的位置
非成员函数的重载
最后的话再来模拟一些【非成员函数重载】,使用到的也是非常多
小于
//< 运算符重载
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)
{
return *this < s || *this == s;
}
大于
bool operator>(const string& s)
{
return !(*this <= s);
}
大于等于
bool operator>=(const string& s)
{
return !(*this < s);
}
不等于
bool operator!=(const string& s)
{
return !(*this == s);
}