✨个人主页: Yohifo
🎉所属专栏: C++修行之路
🎊每篇一句: 图片来源
- The key is to keep company only with people who uplift you, whose presence calls forth your best.
- 关键是只与那些提升你的人在一起,他们的存在唤起了你最好的一面。
🪁前言
string
本质上就是一个专注于存储字符的顺序表,使用起来很方便;但在模拟实现 string
时,有许多值得注意的点,下面就来看看 string
类是如何诞生的吧
注意:string
接口众多,本文模拟实现的只是部分常用接口
🥏正文
跟着官方文档走,string 分割成了几个部分进行实现
《string官方文档》
1、结构
string
本质上就是一个顺序表,因此它也是由 指针
、大小
、容量
这几部分组成
namespace Yohifo //命名空间
{
//定义一个 string 类
class string
{
private:
char* _str; //数据指针
size_t _size; //大小
size_t _capacity; //容量
};
}
大小 和 容量 设为 size_t
,上限值为 42亿多
,即无符号整型 -1
,这个值常常被用来当作循环结束判断条件和查找时未找到的标志,因此有一个专门用来表示 size_t -1
的变量 npos
public:
static const size_t npos = -1; //定义能全局使用的 npos 值(public)
npos
需要设置为公开,否则类外就无法使用了
注意:
npos
类型为static const size_t
static
修饰后,npos
只能被初始化一次- 而加了
const
后,允许在类中赋予缺省值进行初始化,如果不加const
,则必需到类外手动初始化静态成员 - const 修饰的静态变量,只允许整型家族在类中设置缺省值
static const char c = 1; //合法,为整型家族
static const double d = 3.14; //非法,只允许整型家族操作
2、默认成员函数
string
中的四大默认成员函数需要自己设计,因为涉及空间申请与释放,以及后续的深拷贝问题
其他的两个默认成员函数没有必要自己设计,库中的就已经够用了
注意:此时的默认成员函数均在类中直接实现,成为内联函数
2.1、构造与析构
构造函数
使用缺省参数,当用户未传递字符串时,将 string
对象初始化为空串;此时 构造函数
可以利用初始化列表进行初始化
//default 默认成员函数
string(const char* str = "")
:_size(strlen(str))
{
_capacity = _size;
_str = new char[_capacity + 1]; //预留 '\0' 的位置
strcpy(_str, str);
}
注意:
-
为了确保程序的正确性,在初始化列表中只初始化
大小
,再将大小
赋值给容量
,避免出现赋值为随机值的情况(初始化列表初始化顺序只与类中的声明顺序有关) - 开辟空间时,需要多开一个空间,存储 ‘\0’
析构函数析构函数
中在释放内存时,统一为 delete[]
的形式,因此其他地方在申请内存时,即使只申请一个 char
,也要写成 new char[1]
的形式,目的就是与销毁对应
~string()
{
delete[] _str;
_str = nullptr;
_size = _capacity = 0;
}
2.2、拷贝与赋值
拷贝构造
涉及空间开辟,此处为深拷贝,即先开辟一块等量空间,再拷贝数据至新空间,完成拷贝
string(const string& s)
{
//将 s 对象拷贝给 *this
_str = new char[s._capacity + 1]; //开空间、赋值,深拷贝
_size = s._size;
_capacity = s._capacity;
strcpy(_str, s._str);
}
注意: 在申请空间后,一定要 记得使用 strcpy
进行数据拷贝,否则就是无效操作
赋值重载赋值重载
函数在实现时需要注意几种情况:
- 是否为同一对象的赋值
- 被赋值对象空间是否足够
前者用一个判断就可以很好解决,而后者在设计时,是 先借助临时变量开辟空间,若空间开辟成功,则将数据拷贝至新空间,释放原空间,改变指针 _str
指向;若空间开辟失败,则抛出异常,同时还确保了原空间数据不被损坏
string& operator=(const string& s)
{
if (this != &s)
{
char* tmp = new char[s._capacity + 1]; //考虑创建失败的情况
strcpy(tmp, s._str);
delete[] _str; //释放原空间
_str = tmp; //改变指针指向
_size = s._size;
_capacity = s._capacity;
}
return *this; //需要返回,避免 a = b = c 连续赋值情况
}
3、访问数据
string
离不开数据访问函数,如同顺序表一样,可以直接通过 []
+ 下标 访问数据,同时也可以通过 迭代器
访问数据
注意:下标访问
在类中定义,类外实现;迭代器
则是直接在类中定义
3.1、下标访问
类中的数据为私有,无法直接访问,但可以 通过函数间接访问
#include"String.h"
using namespace Yohifo;
//access 访问相关
char& string::operator[](size_t pos)
{
assert(pos < _size); //下标必须小于 _size
//通过下标访问
return _str[pos];
}
//需要再提供一个 const 版本
const char& string::operator[](size_t pos) const
{
assert(pos < _size);
return _str[pos];
}
注意:在类外实现的函数,需要先包含命名空间(这里使用的是全局展开),再通过 ::
访问到指定的类,才能正常实现函数
3.2、迭代器访问
迭代器
是 STL
六大组件之一,适用于所有容器,我们这里只是简单模拟实现 迭代器
,使用的是获取原生指针的方式
//需要通过 typedef 重命名数据类型
typedef char* iterator; //简易迭代器
typedef const char* const_iterator; //简易const迭代器
//iterator 迭代器
iterator begin()
{
return _str;
}
const_iterator cbegin() const
{
//需要再新增一个 const 版本
return _str;
}
iterator end()
{
return _str + _size;
}
const_iterator cend() const
{
return _str + _size;
}
下面来看看通过 原生指针
实现的 迭代器
效果:
4、修改数据
string
支持对其中的数据进行任意修改:尾插字符、尾插字符串、任意位置插入删除都可以
4.1、尾插
尾插即 push_back
,这个东西在数据结构实现阶段已经很熟悉,对于顺序表直接在尾部插入数据即可,当然插入前需要先判断是否需要扩容
//modify 修改相关
void string::push_back(char ch)
{
//检查容量是否足够
if (_size + 1 > _capacity)
{
_capacity == 0 ? _capacity = 1 : 0;
reserve(2 * _capacity); //二倍扩容
}
//尾插字符
_str[_size] = ch;
_str[++_size] = '\0';
}
注意:VS 中的 string
扩容机制为 1.5 倍扩容,我们这里直接采用二倍扩容的方式
4.2、附加
append
译为附加,指在 string
尾部附加 n
个字符或 str
字符串
附加字符
附加字符直接调用 n
次 push_back
即可,不过值得注意的是,为了避免二倍扩容而造成的空间浪费,可以提前将空间扩容至 _size + n
节省空间
string& string::append(size_t n, char ch)
{
//复用代码,尾插n次
//提前开空间
if (_size + n > _capacity)
reserve(_size + n);
while (n--)
push_back(ch);
return *this;
}
附加字符串
附加字符串的话,同样需要判断空间是否足够,如果不够就扩容,然后再 调用库函数 strcat
即可完成字符串附加
string& string::append(const char* str)
{
int len = strlen(str);
if (_size + len > _capacity)
reserve(_size + len);
//调用库函数
strcat(_str, str);
_size += len;
return *this;
}
注意:附加字符串在完成操作后,需要对 _size
作出改变
4.3、重载
push_back
和 append
在实际中用的都比较少,一般是直接使用运算符重载 +=
实现拼接
+= 实际就是对尾插字符和尾插字符串这两种功能的封装,使用起来更加方便
string& string::operator+=(char ch)
{
//复用
return append(1, ch);
}
string& string::operator+=(const string& s)
{
//复用
return append(s._str);
}
复用代码可以尽可能的减少错误的出现
4.4、任意位置插入、删除
任意位置的操作,需要对原数据进行挪动
尤其是 pos = 0
处的操作,需要格外注意
任意位置插入
可以分为两步:挪动数据、插入数据
string& string::insert(size_t pos, size_t n, char ch)
{
assert(pos < _size);
if (_size + n > _capacity)
reserve(_size + n);
//挪动
size_t end = size() + n; //错位
while (end > pos)
{
_str[end] = _str[end - n];
end--;
}
//赋值
//从 pos 位置开始,插入 n 个字符
size_t count = n;
while (count--)
{
_str[pos++] = ch;
}
_size += n;
return *this; //有返回值
}
假设存在 string
对象为 "abcde"
,现需要在 pos = 0
位置插入 "123"
,具体执行结果如下所示
注意:while
循环中,不推荐将条件写为 >=
,因为两者都是 size_t
类型,当 pos = 0
时,可能会出现死循环的情况,因此推荐写为 >
的方式,定义 end
在 size() + n
处,这样错位处理后可以有效避免死循环问题
string
也支持任意位置插入字符串,此时挪动 len
个字符,再通过 strncpy
函数覆盖字符串即可
string& string::insert(size_t pos, const char* str)
{
assert(pos < _size);
int len = strlen(str);
if (_size + len > _capacity)
reserve(_size + len);
//挪动
size_t end = size() + len;
while (end > pos)
{
_str[end] = _str[end - len];
end--;
}
//衔接
strncpy(_str + pos, str, len); //注意:只拷贝 len 个
return *this;
}
strncpy
拷贝 len
个字符,避免将字符串 str
中的 '\0'
也拷贝进去
任意位置删除
任意位置删除函数为 全缺省参数
:
- 参数1
size_t pos
,默认pos = 0
- 参数2
size_t len
,默认len = npos
删除元素分为两种情况
- 元素不够删或
len == npos
,此时需要全部删除,即_size = 0
- 元素足够删,将
pos + len
处的字符串覆盖至pos
处
string& string::erase(size_t pos, size_t len)
{
assert(pos < _size);
assert(!empty());
if (len == npos || _size < pos + len)
{
_str[pos] = '\0';
_size = pos;
}
else
{
strcpy(_str + pos, _str + pos + len);
_size -= len;
}
return *this;
}
假设存在 string
对象为 "123abcde"
,现需要在 pos = 3
位置删除 2个元素
,具体执行结果如下所示
删除并不是真删除,只要合理的调整
'\0'
位置和_size
值,使访问不到后续元素就行了
erase
还支持通过迭代器区间删除元素,实现很简单,通过 指针 - 指针
获取元素个数(下标),复用上面的代码就行了
string::iterator string::erase(iterator begin, iterator end)
{
//复用
erase(begin - _str, end - _str);
return this->begin();
}
5、查看容量
顺序表支持查看各种数据,如大小、容量,同时动态增长的顺序表还有一个不可缺的功能:扩容,对应到 string
中,扩容由 reserve
完成,而调整大小由 resize
负责
5.1、大小、容量、判空
获取这些数据时,因为不需要对 *this
做出修改,这里均使用 const
修饰 *this
// capacity 容量相关
size_t string::size() const
{
return _size;
}
size_t string::capacity() const
{
return _capacity;
}
bool string::empty() const
{
return _size == 0;
}
这三个函数很简单,不做过多赘述
5.2、扩充容量
reserve
可以扩充 _str
的容量,具体使用时,只需要通过 reserve(size_t capacity)
的方式,即可将 _str
容量改变为 capacity
注意:
- 传入的
capacity
可能小于或等于_capacity
,此时不需要缩容,什么操作都不需要 - 传入的
capacity
大于_capacity
,正常扩容,具体逻辑和赋值重载一致
void string::reserve(size_t capacity)
{
//Mask:当扩容容量小于 _size 值时,_size 会变成什么样子
//Reply: 不变,连 _capacity 也不变
if (capacity > _capacity)
{
//开空间+拷贝
char* tmp = new char[capacity + 1];
strcpy(tmp, _str);
//释放空间+改变指向
delete[] _str;
_str = tmp;
_capacity = capacity;
}
}
5.3、调整大小
resize
函数为半缺省参数,缺省参数为参数2 char ch = '\0'
,参数1为 size_t size
调整大小的步骤:
- 判断
size
是否大于_capacity
,如果大于则需要扩容 - 从
_size
处开始,填入字符ch
,直到size
结束 - 重新赋值
_str[_size] = '\0'
void string::resize(size_t size, char ch)
{
//考虑扩容的情况
if (size > _capacity)
reserve(size);
//如果给定的容量大于 _size 就需要植入字符
while (_size < size)
_str[_size++] = ch;
_size = size; //重新赋值,以防 _size > size的情况
_str[_size] = '\0'; //置 '\0'
}
注意:_size = size
这一步不能省略,防止 size
小于 _size
时大小不改变的问题
6、运算符重载
string
中还存在许多重载函数
6.1、字符串相加
"abc"
+ "123"
= "abc123"
这种情况是合法的,当然也存在这个相加函数,无非就是借助临时变量做字符或字符串附加操作
//operator 运算符重载
string string::operator+(char ch) const
{
string tmp(*this); //传值返回,需要借助第三方变量
tmp.push_back(ch);
return tmp;
}
string string::operator+(const string& s) const
{
string tmp(*this);
tmp.append(s._str);
return tmp;
}
注意:对于操作双方都不能作出修改,因此需要借助临时变量 tmp
;返回时,需要使用传值返回,接收时调用拷贝构造,因为 tmp
是局部变量
6.2、逻辑判断
string
对象的大小判断是借助于 ASCII
码值,可以直接使用 strcmp
函数
只需要实现 小于
和 等于
判断,其他逻辑判断可以复用代码
bool string::operator<(const string& s) const
{
//直接调用库函数
return strcmp(_str, s._str) < 0;
}
bool string::operator>(const string& s) const
{
//复用逻辑
return !(*this <= s); //不小于等于就是大于
}
bool string::operator==(const string& s) const
{
return strcmp(_str, s._str) == 0;
}
bool string::operator!=(const string& s) const
{
return !(*this == s); //等于取反就是不等于
}
bool string::operator<=(const string& s) const
{
return (*this < s) || (*this == s); //小于或等于
}
bool string::operator>=(const string& s) const
{
return !(*this < s); //不小于就是大于或等于
}
7、其他
string
中还有其他实用的函数,如查找字符或字符串、清理字符串、交换两个字符串等
7.1、查找
查找字符
传入目标字符,遍历一遍字符串,若找到,返回目标下标,没找到返回 npos
默认 size_t pos = 0
从 0
处开始向后查找,也支持传入参数从指定位置开始查找
//other 其他
size_t string::find(char c, size_t pos) const
{
assert(pos < _size);
//从 pos 位置开始,挨个比较
while (pos < _size)
{
if (_str[pos] == c)
return pos;
pos++;
}
return npos; //没找到返回 npos
}
查找字符串
在算法界存在一个大名鼎鼎的字符串查找算法:KMP 匹配算法
,该算法在子串重复字符较多时比较实用,效率很高,但在实际中,字符串中的重复字符较少,使用 KMP
的查找效率和 strstr
暴力匹配效率相差不大,所以这里直接调用函数 strstr
size_t string::find(const char* s, size_t pos) const
{
assert(pos < _size);
//此处可以使用 KMP 算法,不过意义不大
char* dst = strstr(_str, s); //调用库函数
if (dst == NULL)
return npos;
return dst - _str; //返回下标(位置)
}
注意:指针 - 指针
就是实际找到字符串的下标(位置)
7.2、清理、交换
有时候需要将字符串中的内容一键清空,有时候也需要将两个字符串进行交换
清理
清理的逻辑很简单,令 _size = 0
,再令 _str[_size] = '\0'
即可
void string::clear()
{
//置空
_size = 0;
_str[_size] = '\0';
}
交换
可以直接使用库中的 swap
交换函数,但这样做的 效率较低,会发生多次拷贝构造操作,而且都是 深拷贝
,可以稍微变通下,将 string
中的三个成员分别 swap
,此时是 浅拷贝
,效率很高,也能完成交换任务
void string::swap(string& s)
{
//直接调用库函数进行三次浅拷贝,避免发生深度拷贝构造行为
std::swap(_str, s._str); //交换指针
std::swap(_size, s._size); //交换大小
std::swap(_capacity, s._capacity); //交换容量
}
7.3、获取原生指针
C++
兼容C语言
,在部分场景中,需要获取指针字符串的指针,但此时 _str
为私有成员,所以需要通过函数间接获取指针 _str
char* const string::c_str() const
{
//返回原生指针,方便与 C语言 接口统一
return _str;
}
8、读取与写入
流操作是 string
中少有的类外成员函数,因为此时的左操作数为 ostream
或 istream
注意:这里不需要设为友元函数,因为有很多函数可以辅助我们完成任务
8.1、流插入
将 string
对象的内容直接输出到屏幕上
通过下标访问的方式输出内存
//流插入
ostream& Yohifo::operator<<(ostream& _cout, const string& s)
{
//借助访问函数,输出字符串
size_t pos = 0;
while (pos < s.size())
_cout << s[pos++];
return _cout;
}
还可以使用 迭代器
或 原生指针
输出
8.2、流提取
流提取分析:
-
在获取字符串前,不知道用户输入的字符串长度,无法提前开辟空间
- 如果采用默认2倍扩容的方式,势必会造成严重的空间浪费
- 读取数据后,若字符串中已存在数据,需要覆盖原数据
解决方案:
- 借助一个
char buff[128]
数组存储数据,当数组装满时,将buff
拼接至字符串尾部,buff
重新开始存储数据,这样无论输入多长的字符串,都可以很好的读取,而且避免了空间的浪费 - 调用
clear()
函数先清理字符串,再进行输入
//流提取
istream& Yohifo::operator>>(istream& _cin, string& s)
{
s.clear(); //流插入前先清理
//此时输入字符串大小未知,需要通过 buff 数组不断装载的方式实现流插入
char buff[128] = { 0 }; //大小为128
int pos = 0;
char ch = _cin.get(); //获取字符
while (ch != ' ' && ch != '\n')
{
buff[pos++] = ch;
if (pos == 127)
{
//拼接至 s
s += buff;
pos = 0; //重新装载
}
ch = _cin.get();
}
if (pos < 127)
{
//此时需要手动置 '\0'
buff[pos] = '\0';
s += buff; //链接
}
return _cin;
}
注意:
- 逐字符读取,可以使用
cin.get()
函数,类似于getc()
函数 - 流提取的结束条件是遇到
空白字符
就结束 - 当
while
循环结束后,如果pos < 127
,需要置入'\0'
,避免插入两个半(或更多)buff
数据的情况
buff
数组是一个 局部变量,不会造成空间浪费
8.3、获取整行串
getline
函数可以读取到空格,实现逻辑95%都和流提取一致,不过在循环结束条件中,getline
只取决于是否读取到 '\n'
//获取一行字符串
istream& Yohifo::getline(istream& _cin, string& s)
{
//大体逻辑与流提取一致,不过判断条件减少
s.clear(); //先清理
char buff[128] = { 0 }; //大小为128
int pos = 0;
char ch = _cin.get(); //获取字符
while (ch != '\n')
{
buff[pos++] = ch;
if (pos == 127)
{
//链接至 s
s += buff;
pos = 0; //重新装载
}
ch = _cin.get();
}
if (pos < 127)
{
//此时需要手动置 '\0'
buff[pos] = '\0';
s += buff; //链接
}
return _cin;
}
9、整体代码
文中所有代码都存储 Gitee
仓库,可以通过下面的链接直接跳转查看
sting_2_28 代码仓库
🎯总结
以上就是本次关于 string
类模拟实现的全部内容了,string
比较适合尝试自己实现,相信在实现之后,对 string
类的理解和使用能更上一层楼
如果你觉得本文写的还不错的话,可以留下一个小小的赞👍,你的支持是我分享的最大动力!
如果本文有不足或错误的地方,随时欢迎指出,我会在第一时间改正
文章来源:https://www.toymoban.com/news/detail-407121.html
文章来源地址https://www.toymoban.com/news/detail-407121.html
相关文章推荐
C++ STL 学习之【string】
C++【模板初阶】
C/C++【内存管理】
===============
类和对象实操
类和对象实操之【日期类】
到了这里,关于C++ STL学习之【string的模拟实现】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!