C++ STL学习之【string类的模拟实现】

简介: string 本质上就是一个专注于存储字符的顺序表,使用起来很方便;但在模拟实现 string 时,有许多值得注意的点,下面就来看看 string 类是如何诞生的吧

✨个人主页: Yohifo

🎉所属专栏: C++修行之路

🎊每篇一句: 图片来源


The key is to keep company only with people who uplift you, whose presence calls forth your best.


关键是只与那些提升你的人在一起,他们的存在唤起了你最好的一面。


e759e755f209f3ab42eb5c1d7eae379.png


🪁前言


string 本质上就是一个专注于存储字符的顺序表,使用起来很方便;但在模拟实现 string 时,有许多值得注意的点,下面就来看看 string 类是如何诞生的吧


注意string 接口众多,本文模拟实现的只是部分常用接口


40b8079118bd875050a70de5171cf40.png


🥏正文


跟着官方文档走,string 分割成了几个部分进行实现


《string官方文档》


1、结构


string 本质上就是一个顺序表,因此它也是由 指针、大小、容量 这几部分组成


namespaceYohifo//命名空间{
//定义一个 string 类classstring    {
private:
char*_str; //数据指针size_t_size;   //大小size_t_capacity;   //容量    };
}


大小 容量 设为 size_t,上限值为 42亿多,即 无符号整型 -1,这个值常常被用来当作循环结束判断条件和查找时未找到的标志,因此有一个专门用来表示 size_t -1 的变量 npos


public:
staticconstsize_tnpos=-1;  //定义能全局使用的 npos 值(public)


npos 需要设置为公开,否则类外就无法使用了


注意:


  • npos 类型为 static const size_t
  • static 修饰后,npos 只能被初始化一次
  • 而加了 const 后,允许在类中赋予缺省值进行初始化,如果不加 const,则必需到类外手动初始化静态成员
  • const 修饰的静态变量,只允许整型家族在类中设置缺省值


staticconstcharc=1;    //合法,为整型家族staticconstdoubled=3.14;   //非法,只允许整型家族操作


2、默认成员函数


string 中的四大默认成员函数需要自己设计,因为涉及空间申请与释放,以及后续的深拷贝问题

其他的两个默认成员函数没有必要自己设计,库中的就已经够用了

e8819900ff1f30a4942bba75f7f2a17.png

注意: 此时的默认成员函数均在类中直接实现,成为内联函数


2.1、构造与析构


构造函数

使用缺省参数,当用户未传递字符串时,将 string 对象初始化为空串;此时 构造函数 可以利用初始化列表进行初始化


//default   默认成员函数string(constchar*str="")
    :_size(strlen(str))
{
_capacity=_size;
_str=newchar[_capacity+1]; //预留 '\0' 的位置strcpy(_str, str);
}


注意:


  • 为了确保程序的正确性,在初始化列表中只初始化 大小,再将 大小 赋值给 容量,避免出现赋值为随机值的情况(初始化列表初始化顺序只与类中的声明顺序有关)
  • 开辟空间时,需要多开一个空间,存储 ‘\0’


析构函数

析构函数 中在释放内存时,统一为 delete[] 的形式,因此其他地方在申请内存时,即使只申请一个 char,也要写成 new char[1] 的形式,目的就是与销毁对应


~string()
{
delete[] _str;
_str=nullptr;
_size=_capacity=0;
}


2.2、拷贝与赋值


拷贝构造

涉及空间开辟,此处为深拷贝,即先开辟一块等量空间,再拷贝数据至新空间,完成拷贝


string(conststring&s)
{
//将 s 对象拷贝给 *this_str=newchar[s._capacity+1];   //开空间、赋值,深拷贝_size=s._size;
_capacity=s._capacity;
strcpy(_str, s._str);
}


注意: 在申请空间后,一定要 记得使用 strcpy 进行数据拷贝,否则就是无效操作


赋值重载

赋值重载 函数在实现时需要注意几种情况:

  • 是否为同一对象的赋值
  • 被赋值对象空间是否足够


前者用一个判断就可以很好解决,而后者在设计时,是 先借助临时变量开辟空间,若空间开辟成功,则将数据拷贝至新空间,释放原空间,改变指针 _str 指向;若空间开辟失败,则抛出异常,同时还确保了原空间数据不被损坏


string&operator=(conststring&s)
{
if (this!=&s)
    {
char*tmp=newchar[s._capacity+1];  //考虑创建失败的情况strcpy(tmp, s._str);
delete[] _str;  //释放原空间_str=tmp; //改变指针指向_size=s._size;
_capacity=s._capacity;
    }
return*this;   //需要返回,避免 a = b = c 连续赋值情况}


3、访问数据


string 离不开数据访问函数,如同顺序表一样,可以直接通过 [] + 下标 访问数据,同时也可以通过 迭代器 访问数据


6b1937cd8be36708b5b93219c248222.png

注意:下标访问 在类中定义,类外实现;迭代器 则是直接在类中定义


3.1、下标访问


类中的数据为私有,无法直接访问,但可以 通过函数间接访问


#include"String.h"usingnamespaceYohifo;
//access    访问相关char&string::operator[](size_tpos)
{
assert(pos<_size);    //下标必须小于 _size//通过下标访问return_str[pos];
}
//需要再提供一个 const 版本constchar&string::operator[](size_tpos) const{
assert(pos<_size);
return_str[pos];
}



注意: 在类外实现的函数,需要先包含命名空间(这里使用的是全局展开),再通过 :: 访问到指定的类,才能正常实现函数


3.2、迭代器访问


迭代器 STL 六大组件之一,适用于所有容器,我们这里只是简单模拟实现 迭代器,使用的是获取原生指针的方式


//需要通过 typedef 重命名数据类型typedefchar*iterator; //简易迭代器typedefconstchar*const_iterator; //简易const迭代器//iterator  迭代器iteratorbegin()
{
return_str;
}
const_iteratorcbegin() const{
//需要再新增一个 const 版本return_str;
}
iteratorend()
{
return_str+_size;
}
const_iteratorcend() const{
return_str+_size;
}


下面来看看通过 原生指针 实现的 迭代器 效果:


c9c6201d61ec4ae5ddce471fb1b6e25.png


4、修改数据


string 支持对其中的数据进行任意修改:尾插字符、尾插字符串、任意位置插入删除都可以


2017df898a11dd72f9fa91f336fe5c2.png


4.1、尾插


尾插即 push_back,这个东西在数据结构实现阶段已经很熟悉,对于顺序表直接在尾部插入数据即可,当然插入前需要先判断是否需要扩容


//modify    修改相关voidstring::push_back(charch)
{
//检查容量是否足够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_tn, charch)
{
//复用代码,尾插n次//提前开空间if (_size+n>_capacity)
reserve(_size+n);
while (n--)
push_back(ch);
return*this;
}


附加字符串

附加字符串的话,同样需要判断空间是否足够,如果不够就扩容,然后再 调用库函数 strcat 即可完成字符串附加


string&string::append(constchar*str)
{
intlen=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+=(charch)
{
//复用returnappend(1, ch);
}
string&string::operator+=(conststring&s)
{
//复用returnappend(s._str);
}


复用代码可以尽可能的减少错误的出现


4.4、任意位置插入、删除


任意位置的操作,需要对原数据进行挪动


尤其是 pos = 0 处的操作,需要格外注意


任意位置插入

可以分为两步:挪动数据、插入数据


string&string::insert(size_tpos, size_tn, charch)
{
assert(pos<_size);
if (_size+n>_capacity)
reserve(_size+n);
//挪动size_tend=size() +n;    //错位while (end>pos)
    {
_str[end] =_str[end-n];
end--;
    }
//赋值//从 pos 位置开始,插入 n 个字符size_tcount=n;
while (count--)
    {
_str[pos++] =ch;
    }
_size+=n;
return*this;   //有返回值}


假设存在 string 对象为 "abcde",现需要在 pos = 0 位置插入 "123",具体执行结果如下所示


任意位置插入.gif

注意: while 循环中,不推荐将条件写为 >= ,因为两者都是 size_t 类型,当 pos = 0 时,可能会出现死循环的情况,因此推荐写为 > 的方式,定义 endsize() + n 处,这样错位处理后可以有效避免死循环问题


string 也支持任意位置插入字符串,此时挪动 len 个字符,再通过 strncpy 函数覆盖字符串即可


string&string::insert(size_tpos, constchar*str)
{
assert(pos<_size);
intlen=strlen(str);
if (_size+len>_capacity)
reserve(_size+len);
//挪动size_tend=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_tpos, size_tlen)
{
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个元素,具体执行结果如下所示

任意位置删除.gif


删除并不是真删除,只要合理的调整 '\0' 位置和 _size 值,使访问不到后续元素就行了


erase 还支持通过迭代器区间删除元素,实现很简单,通过 指针 - 指针 获取元素个数(下标),复用上面的代码就行了

string::iteratorstring::erase(iteratorbegin, iteratorend)
{
//复用erase(begin-_str, end-_str);
returnthis->begin();
}


5、查看容量


顺序表支持查看各种数据,如大小、容量,同时动态增长的顺序表还有一个不可缺的功能:扩容,对应到 string 中,扩容由 reserve 完成,而调整大小由 resize 负责


3c417c6aaae713534289cb315d733bc.png


5.1、大小、容量、判空


获取这些数据时,因为不需要对 *this 做出修改,这里均使用 const 修饰 *this

// capacity 容量相关size_tstring::size() const{
return_size;
}
size_tstring::capacity() const{
return_capacity;
}
boolstring::empty() const{
return_size==0;
}

三个函数很简单,不做过多赘述


5.2、扩充容量


reserve 可以扩充 _str 的容量,具体使用时,只需要通过 reserve(size_t capacity) 的方式,即可将 _str 容量改变为 capacity


注意:

  • 传入的 capacity 可能小于或等于 _capacity,此时不需要缩容,什么操作都不需要
  • 传入的 capacity 大于 _capacity,正常扩容,具体逻辑和赋值重载一致


voidstring::reserve(size_tcapacity)
{
//Mask:当扩容容量小于 _size 值时,_size 会变成什么样子//Reply: 不变,连 _capacity 也不变if (capacity>_capacity)
    {
//开空间+拷贝char*tmp=newchar[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'


voidstring::resize(size_tsize, charch)
{
//考虑扩容的情况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 中还存在许多重载函数


5350171a65cd0eb9a1c7581cc3b5e6c.png


6.1、字符串相加


"abc" + "123" = "abc123" 这种情况是合法的,当然也存在这个相加函数,无非就是借助临时变量做字符或字符串附加操作


//operator  运算符重载stringstring::operator+(charch) const{
stringtmp(*this);  //传值返回,需要借助第三方变量tmp.push_back(ch);
returntmp;
}
stringstring::operator+(conststring&s) const{
stringtmp(*this);
tmp.append(s._str);
returntmp;
}



注意: 对于操作双方都不能作出修改,因此需要借助临时变量 tmp;返回时,需要使用传值返回,接收时调用拷贝构造,因为 tmp 是局部变量


6.2、逻辑判断


string 对象的大小判断是借助于 ASCII 码值,可以直接使用 strcmp 函数


只需要实现 小于等于 判断,其他逻辑判断可以复用代码


boolstring::operator<(conststring&s) const{
//直接调用库函数returnstrcmp(_str, s._str) <0;
}
boolstring::operator>(conststring&s) const{
//复用逻辑return!(*this<=s);   //不小于等于就是大于}
boolstring::operator==(conststring&s) const{
returnstrcmp(_str, s._str) ==0;
}
boolstring::operator!=(conststring&s) const{
return!(*this==s);   //等于取反就是不等于}
boolstring::operator<=(conststring&s) const{
return (*this<s) || (*this==s); //小于或等于}
boolstring::operator>=(conststring&s) const{
return!(*this<s);    //不小于就是大于或等于}



7、其他


string 中还有其他实用的函数,如查找字符或字符串、清理字符串、交换两个字符串等


3b9b5aff2abb30ef4048ff4994e1918.png


7.1、查找


查找字符

传入目标字符,遍历一遍字符串,若找到,返回目标下标,没找到返回 npos

默认 size_t pos = 0 0 处开始向后查找,也支持传入参数从指定位置开始查找


//other 其他size_tstring::find(charc, size_tpos) const{
assert(pos<_size);
//从 pos 位置开始,挨个比较while (pos<_size)
    {
if (_str[pos] ==c)
returnpos;
pos++;
    }
returnnpos;    //没找到返回 npos}


查找字符串

在算法界存在一个大名鼎鼎的字符串查找算法:KMP 匹配算法,该算法在子串重复字符较多时比较实用,效率很高,但在实际中,字符串中的重复字符较少,使用 KMP 的查找效率和 strstr 暴力匹配效率相差不大,所以这里直接调用函数 strstr


size_tstring::find(constchar*s, size_tpos) const{
assert(pos<_size);
//此处可以使用 KMP 算法,不过意义不大char*dst=strstr(_str, s);    //调用库函数if (dst==NULL)
returnnpos;
returndst-_str;  //返回下标(位置)}


注意:指针 - 指针 就是实际找到字符串的下标(位置)


7.2、清理、交换


有时候需要将字符串中的内容一键清空,有时候也需要将两个字符串进行交换


清理

清理的逻辑很简单,令 _size = 0,再令 _str[_size] = '\0' 即可


voidstring::clear()
{
//置空_size=0;
_str[_size] ='\0';
}


交换

可以直接使用库中的 swap 交换函数,但这样做的 效率较低,会发生多次拷贝构造操作,而且都是 深拷贝,可以稍微变通下, string 中的三个成员分别 swap,此时是 浅拷贝,效率很高,也能完成交换任务


voidstring::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*conststring::c_str() const{
//返回原生指针,方便与 C语言 接口统一return_str;
}


8、读取与写入


流操作是 string 中少有的类外成员函数,因为此时的左操作数为 ostream istream

7f3b574b7e71029a3ba8bb0accbf3a8.png


注意: 这里不需要设为友元函数,因为有很多函数可以辅助我们完成任务


8.1、流插入


string 对象的内容直接输出到屏幕上

通过下标访问的方式输出内存


//流插入ostream&Yohifo::operator<<(ostream&_cout, conststring&s)
{
//借助访问函数,输出字符串size_tpos=0;
while (pos<s.size())
_cout<<s[pos++];
return_cout;
}


还可以使用 迭代器原生指针 输出


8.2、流提取


流提取分析:

  1. 在获取字符串前,不知道用户输入的字符串长度,无法提前开辟空间
  2. 如果采用默认2倍扩容的方式,势必会造成严重的空间浪费
  3. 读取数据后,若字符串中已存在数据,需要覆盖原数据


解决方案:

  • 借助一个 char buff[128] 数组存储数据,当数组装满时,将 buff 拼接至字符串尾部,buff 重新开始存储数据,这样无论输入多长的字符串,都可以很好的读取,而且避免了空间的浪费
  • 调用 clear() 函数先清理字符串,再进行输入


d0e43bf0175c7a9ac8f55890a37b477.png


//流提取istream&Yohifo::operator>>(istream&_cin, string&s)
{
s.clear();  //流插入前先清理//此时输入字符串大小未知,需要通过 buff 数组不断装载的方式实现流插入charbuff[128] = { 0 }; //大小为128intpos=0;
charch=_cin.get();   //获取字符while (ch!=' '&&ch!='\n')
    {
buff[pos++] =ch;
if (pos==127)
         {
//拼接至 ss+=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();  //先清理charbuff[128] = { 0 }; //大小为128intpos=0;
charch=_cin.get();   //获取字符while (ch!='\n')
    {
buff[pos++] =ch;
if (pos==127)
         {
//链接至 ss+=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 类的理解和使用能更上一层楼


如果你觉得本文写的还不错的话,可以留下一个小小的赞👍,你的支持是我分享的最大动力!


如果本文有不足或错误的地方,随时欢迎指出,我会在第一时间改正


1658489422102.jpg.jpg


相关文章推荐


C++ STL 学习之【string】


C++【模板初阶】


C/C++【内存管理】


===============


类和对象实操


类和对象实操之【日期类】


承蒙厚爱,感谢支持.gif

目录
相关文章
|
20小时前
|
C语言 C++
C++对C的改进和拓展\string类型
C++对C的改进和拓展\string类型
|
3天前
|
算法 前端开发 Linux
【常用技巧】C++ STL容器操作:6种常用场景算法
STL在Linux C++中使用的非常普遍,掌握并合适的使用各种容器至关重要!
31 10
|
5天前
|
存储 编译器 程序员
【C++高阶】C++继承学习手册:全面解析继承的各个方面
【C++高阶】C++继承学习手册:全面解析继承的各个方面
11 1
|
5天前
|
存储 算法 程序员
【C++进阶】深入STL之 栈与队列:数据结构探索之旅
【C++进阶】深入STL之 栈与队列:数据结构探索之旅
15 4
|
5天前
|
存储 缓存 编译器
【C++进阶】深入STL之list:模拟实现深入理解List与迭代器
【C++进阶】深入STL之list:模拟实现深入理解List与迭代器
8 0
|
5天前
|
C++ 容器
【C++进阶】深入STL之list:高效双向链表的使用技巧
【C++进阶】深入STL之list:高效双向链表的使用技巧
9 0
|
5天前
|
编译器 C++ 容器
【C++进阶】深入STL之vector:深入研究迭代器失效及拷贝问题
【C++进阶】深入STL之vector:深入研究迭代器失效及拷贝问题
11 0
|
5天前
|
存储 算法 程序员
【C++进阶】深入STL之vector:构建高效C++程序的基石
【C++进阶】深入STL之vector:构建高效C++程序的基石
12 1
|
5天前
|
编译器 C++
【C++进阶】深入STL之string:模拟实现走进C++字符串的世界
【C++进阶】深入STL之string:模拟实现走进C++字符串的世界
12 1
|
18小时前
|
C++
C++类和类模板——入门
C++类和类模板——入门
6 1

热门文章

最新文章