当前位置: 首页 > news >正文

C/C++ string模拟实现

1.模拟准备

1.1因为是模拟string,防止与库发生冲突,所以需要命名空间namespace隔离一下,我们来看一下基本内容

namespace yx
{class string{private://char _buff[16];  lunix下小于16字节就存buff里char* _str;size_t _size;size_t _capacity;};
}

1.2我们这里声明和定义分离,分为string.h和string.cpp

最简单的是:把声明和定义都往命名空间里包就可以

        

2.模拟实现

2.1遇到一个类,先来写构造和析构

构造和析构

我们来看一下下面代码对不对

namespace yx
{ string::string(const char* str):_str(str){}
}

既然这么问了,那肯定是不对的,

因为你初始化string的时候,可能为常量字符串初始化的,它是不可以作为初始化对象的,当你扩容、修改就没法改了

yx::string s1("hello world");

应该这样玩:

namespace yx
{ string::string(const char* str):_str(new char[strlen(str) + 1]){}
}

我和你开一样的空间

完整写法👇 

string::string(const char* str):_str(new char[strlen(str) + 1]), _size(strlen(str)), _capacity(strlen(str))
{strcpy(_str, str);
}

但还是有点问题的,strlen的效率还是有点底的,它和sizeof不一样,sizeof是在编译时运行,根据存储规则,内存对齐规则来算,strlen是运行时算的,三个strlen就重复运算了。

我们可以把size放在初始化列表,把其他的放在函数体初始化

string::string(const char* str): _size(strlen(str))
{_str = new char[_size + 1];_capacity = _size;strcpy(_str, str);
}

这是比较传统的写法,我们来看一下同样手法

tring::string(const string& s)
{string tmp(s._str);std::swap(tmp._str, _str);std::swap(tmp._size, _size);std::swap(tmp._capacity, _capacity);
}

创建一个临时变量tmp,s1给给tmp,然后把s2指向tmp,tmp指向s2的位置.

c_str

const char* c_str() const;
const char* string::c_str() const
{return _str;
}

加const是为了让const或非const成员都能访问到,c_str()的类型为const char*,相当于常量字符串,遇到\0就会停止

无参string

我们可不可以这样写呢?

string::string()
{_str = nullptr;_size = 0;_capacity = 0;
}

看起来可以,但实际不可以,这里的delete和free是不会出问题的,因为delete是可以空指针的

我们看例子,后定义的先析构,程序崩溃了,为什么呢?

c_str ,类型为const char* 不会按指针打印,是常量字符串,就会解引用找到\0才停止。

但库里不会崩溃

为什么?

因为这个地方不是没有空间,库里面开了一个空间

所以初始化要改为

string::string()
{_str = new char[1] {'\0'};_size = 0;_capacity = 0;
}

new一个空间,而实践中不会这样写,无参的和带参的是可以和成一个的,就是全缺省

如下👇,冒号里的\0是可以不写的 默认就是\0 , 给的是字符串

namespace yx
{class string{public://string(); //无参构造  string(const char* str = "\0");~string();const char* c_str() const;//加上const,const成员和非const成员都可以调用private://char _buff[16];  lunix下小于16字节就存buff里char* _str;size_t _size;size_t _capacity;};
}

遍历:运算符重载[] 和 size()

char& string::operator[](size_t pos)
{assert(pos < _size);return _str[pos];
}
size_t string::size() const
{return _size;
}

测试:可读可写

迭代器:begin 和 end

实现方式有两种,自定义类型的和简单点的,我们这里使用简单的

typedef char* iterator;iterator begin();
iterator end();
string::iterator string::begin()
{return _str;
}
string::iterator string::end()
{return _str + _size;
}

为什么这样写?

注:

        这里必须用typedef,为什么?迭代器体现的是一种封装

        这里的typedef相当于把char*用iterator封装起来,而且这里的迭代器一定是char*吗,在lunix下是char*吗,不同平台是不同的。

把不同类型,不同平台的类型都封装成Iterator,隐藏的底层的细节。它是一个像指针的东西。iterator的原生类型是不确定的,给了一种简单通用访问容器的方式。

无论哪个容器都重命名为iterator,各个类域也不会发生冲突。

const迭代器

定义及实现

const_iterator begin() const;
const_iterator end() const;
string::const_iterator string::begin() const
{return _str;
}

这里可以直接返回_str,_str类型为char*,begin为const char* ,相当于权限缩小。

string::const_iterator string::end() const
{return _str + _size;
}

这里也是权限缩小,下面我们测试一下

测试成功,而且是不能给常量赋值的,如下👇

如果我们用方括号加size来遍历呢?

这里会报错,为啥?因为s3是常量,所以还需要重载一个const修饰的operator[]

const char& operator[](size_t pos) const;​
const char& string::operator[](size_t pos) const
{assert(pos < _size);return _str[pos];
}

测试通过。

push_back()  、 append()  和 reserve()

完成了string的基本功能,下面我们来进行string的插入。

push_back()是尾插一个字符,append()插入一个字符串,这里我们会遇到一个问题,push_back()尾插扩容一倍或两倍,不会太大;append()是插入一个字符串,有可能需要扩容,但扩容多少呢?插入字符串长短不定,万一非常长,你扩容二倍?显然扩容多少倍是不确定的。这里我们引入reserve().

reserve()请求保留空间,一般不会缩容,如果空间比capacity大了就会扩容

void string::reserve(size_t n)
{if (n > _capacity){char* tmp = new char[n + 1];//为什么预留一个空间? 因为\0是不算在里面的strcpy(tmp,_str);delete[] _str;//释放旧空间_str = tmp;//指向新空间_capacity = n;}
}

push_back()

​
void string::push_back(char ch)//插入字符
{if (_size == _capacity)//如果size 等于 容量大小才会扩容{size_t newcapacity = _capacity == 0 ? 4 : _capacity * 2;reserve(newcapacity);//传给reserve,如果比当前capacity大,就扩容}_str[_size] = ch;//_size是最后一个字符的下一个位置_str[_size + 1] = '\0';++_size;
}​

满足扩容条件才扩容,_size是最后一个字符的下一个位置,也就是\0的位置,所以需要把\0也处理一下。

append()

我们来看一下下面代码正确否?

void string::append(const char* str)//插入字符串
{size_t len = strlen(str);if (_size + len > _capacity){reserve(_size + len);//现在有_size个,我们需要插入长度为len的字符串}strcat(_str, str);_size += len;
}

使用了strcat(),直接在原字符串后面追加,我们测试一下

测试没问题。但是我们用strcat的时候要谨慎一些,他会从头开始找\0,效率低,这里我们采用strcpy(),从指定位置开始拷贝,带\0

void string::append(const char* str)//插入字符串
{size_t len = strlen(str);if (_size + len > _capacity){reserve(_size + len);//现在有_size个,我们需要插入长度为len的字符串}strcpy(_str + _size, str);_size += len;
}

同样测试通过,但效率很高

直接从\0位置开始插入

 

operator+=

说到尾插字符串,那必须得提到+=运算符重载,这里提供俩个版本

这里引用返回,返回对象本身,出了作用域对象还存在。

string& operator+=(char ch);//+=是需要返回值的,用引用返回减少拷贝
string& operator+=(const char ch);

这里我们直接调用push_bakc和append

string& string::operator+=(char ch)
{push_back(ch);return *this;
}
string& string::operator+=(const char* str)
{append(str);return *this;
}

测试

inset() 和 erase()

size_t insert(size_t pos,char ch); //pos位插入字符
size_t insert(size_t pos,const char* ch);//插入字符串
void erase(size_t pos, size_t len = npos);//pos开始删除len个字符
private://char _buff[16];  lunix下小于16字节就存buff里char* _str;size_t _size;size_t _capacity;const static size_t npos;

对于npos,静态成员如何初始化在类里面声明,在类外定义。

类里的静态成员遍历,相当于全局变量,如果在string.h里定义,在预处理以后,string

.h会在string.cpp和test.cpp里展开,展开两份,俩文件最后生成.o文件,再一链接就出问题了,

声明和定义分离的时候把定义放在.cpp,声明放在.h。

insert()插入一个字符

size_t string::insert(size_t pos, char ch)
{if (_size == _capacity)//空间不够,就扩容{size_t newcapacity = _capacity == 0 ? 4 : _capacity * 2;reserve(newcapacity);}size_t end = _size;while (end >= pos){_str[end + 1] = _str[end];--end;}_str[pos] = ch;++_size;
}

测试

如果我们在0出插入一个字符呢?

显然报错了,为什么?

因为edn >= 0 继续交换,把0之前的哪个未知值也交换进去了,

当end >= pos = 0 时,已将交换完了,但又进入循环了,为什么?因为当操作符两边的操作数类型不同的时候,会发生隐式类型转化,当有符号遇到无符号,有符号转换为无符号,end变为非常大的数,end依据大于pos。那有什么方法来修改呢?

我们是否可以把pos改为int类型呢?答案是不建议,因为我们要与库里的类型一样。

直接把pos强制转为int,运行测试提供。

void string::insert(size_t pos, char ch)
{if (_size == _capacity)//空间不够,就扩容{size_t newcapacity = _capacity == 0 ? 4 : _capacity * 2;reserve(newcapacity);}size_t end = _size;while (end >= (int)pos){_str[end + 1] = _str[end];--end;}_str[pos] = ch;//把字符放进去++_size;
}

那么我们可以不强转可以修改吗?可以

这里最根本的问题点在于end >= pos,只要是无符号遇到>=绝对是坑,无符号最小就是0,无法停止,非常扯淡。

这里我们去掉= ,把end的位置变为_size + 1,把前一个往后挪。

代码修改为:

void string::insert(size_t pos, char ch)
{if (_size == _capacity)//空间不够,就扩容{size_t newcapacity = _capacity == 0 ? 4 : _capacity * 2;reserve(newcapacity);}size_t end = _size + 1;while (end > pos){_str[end] = _str[end - 1];--end;}_str[pos] = ch;//把字符放进去++_size;
}

测试通过

insert()插入一个字符串

void insert(size_t pos,const char* str);//插入字符串

首先pos不能越界,检查是否需要扩容,

把xxx拷贝进去,不能用strcpy,它携带了\0,我们可以用strncpy或memcpy,这里我们采用memcpy

代码:

void string::insert(size_t pos, const char* str)
{ assert(pos <= _size);size_t len = strlen(str);if (_size + len > _capacity){reserve(_size + len);}int end = _size;while (end >= pos){_str[end + len] = _str[end];--end;}memcpy(_str + pos, str, len);_size += len;}

测试通过

这是我们在0出插入,还是会遇到之前的问题

我们只需要把pos强制类型转化为int即可。

如果我们不想用这种方式,我们把=去掉,把前一个往后挪,

到pos + len依旧需要挪动,可以写成end>=pos+len

void string::insert(size_t pos, const char* str)
{ assert(pos <= _size);size_t len = strlen(str);if (_size + len > _capacity){reserve(_size + len);}/*int end = _size;while (end >=(int) pos){_str[end + len] = _str[end];--end;}*/size_t end = _size + len;//len插入字符串长度while (end > pos + len - 1){_str[end] = _str[end - len];--end;}memcpy(_str + pos, str, len);_size += len;}

erase()

void erase(size_t pos, size_t len = npos);//pos开始删除len个字符

代码:第一种情况,删除的长度大于pos后的长度,直接全部删除;第二种情况,直接把不删除的字符覆盖在要删除的字符上。

void string::erase(size_t pos = 0, size_t len = npos)
{assert(pos < _size);if (len == npos || len >= _size - pos)//删除的字符大于pos后的字符{_str[pos] = '\0';_size = pos;}else{strcpy(_str + pos, _str + pos + len);_size -= len; }}

find()

查找一个字符

size_t string::find(char ch, size_t pos = 0)
{for (size_t i = 0; i < _size; i++){if (_str[i] == ch){return i;}}return npos;
}

查找一个子串


size_t string::find(const char* sub, size_t pos = 0)//从pos位置开始查找
{const char* p = strstr(_str + pos, sub);//在_str 种匹配sub子串,,返回对应位置指针return p - _str;//指针相减获取下标
}

测试通过

运算符重载 = 

看下面代码,s1赋值拷贝给s2,s3赋值给s1,下面程序有没有问题呢?

void test5()
{yx::string s1("hello world");yx::string s2(s1);cout << s1.c_str() << endl;cout << s2.c_str() << endl;yx::string s3("yyyy");s1 = s3; // s3赋值给s1cout << s1.c_str() << endl;cout << s3.c_str() << endl;
}

当然是有问题的,当我们没有运算符重载=时,编译器会默认提供一个版本,会执行浅拷贝,当 s2 被创建为 s1 的副本时,s2 实际上可能仅仅是指向 s1 所指向的字符串常量的另一个指针。这意味着,如果改变 s2 所指向的内容,s1 的内容也会随之改变。所以需要我们实现深拷贝版本。

修正:

string& 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;}
}

重新开一个空间tmp,把需要拷贝的字符串拷贝进去,然后释放旧空间,把new的空间给给原空间

而且为了避免自己给自己赋值,需要再套一个判断 this != &s

优化写法:

s1 = s3,s是s3的别名

	string& string::operator=(const string& s){if (this != &s){string tmp(s._str);this->swap(tmp);}return *this;}

s3拷贝给s1,设置一个临时变量tmp,s3拷贝构造tmp,然后再交换s1和tmp的空间。

而且tmp是个局部对象,出了作用域会析构,免去了释放空间这一步

最简化的写法:

s1 = s3

string& operator=(string tmp);string& string::operator=(string tmp)
{swap(tmp);return *this;
}

和上面最大的区别在于没有引用,s3拷贝构造tmp,然后s1和tmp交换,和上面的道理一样,tmp是临时对象,出了作用域自动销毁,效率并没有提示,只是简化了代码

swap()

如果我们swap一下s1 和 s2呢?库里的swap能否帮我们完成任务呢?答案是可以的,因为他是模板,但是它的代价非常大,

a 拷贝给 c,b 赋值给 a,c赋值给b,都会开空间,拷贝数据,传值传参代价都非常大。

自己实现:

void string::swap(string& s)
{std::swap(_str, s._str);//交换char*指针,size capacitystd::swap(_size, s._size);std::swap(_capacity, s._capacity);
}

通过命名空间,来使用库里的swap,如果不写std,swap就会调用自己,而且这里面交换的都是内置类型

strsub()

从pos位置开始,取len个字符的子串

代码实现:

string string::substr(size_t pos, size_t len)
{if (len > _size - pos)//如果len大于pos后面的长度,有多少取多少{string sub(_str + pos);//_str(开始的指针 ) + pos 从pos位置开始取,然后构造一个子串返回return sub;}else{string sub;sub.reserve(len);//扩容for (size_t i = 0;i< len ;i++){sub += _str[pos + i];}return sub;}
}

运算符重载 < > <= >= == !=

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);
}
bool string::operator==(const string& s) const
{return strcmp(_str, s._str);
}
bool string::operator!=(const string& s) const
{!(*this == s);
}

其实这里写两个,然后取反复用就可以。

流插入和流提取operator<< >> 

istream& operator>>(istream& is, string& str)// is - cin
{char ch = is.get();is >> ch;while (ch != ' ' || ch != '\n')//不等于空格或换行{str += ch;//在io流里提取一个一个的char += 到str里char ch = is.get();}return is;
}
ostream& operator<<(ostream& os, const string& str)//os - cout
{for (size_t i = 0; i < str.size(); i++){os << str[i];//一个一个插入}return os;
}

流插入和流提取的运算符重载不能写成成员函数,且不一定写成友元。

cin是不能获取空格的,而scanf可以 当输入 y 空格 y 时, 写两个cin ,两个cin都会获得y,而忽略空格。

clear()

void string::clear() //请调当前的数据
{_str[0] = '\0';_size = 0;
}

相关文章:

  • MYSQL execute command denied to user ‘‘@‘%‘ for routine
  • 腾讯《地下城与勇士:起源》手游在部分安卓平台停止更新
  • 微信小程序-上拉加载和下拉刷新
  • C类IP介绍
  • 【Java数据结构】优先级队列详解(二)
  • centos环境上:k8s 简单安装教程
  • 《算法设计与分析》第五六章:回溯法与分支限界法
  • FreeRTOS学习笔记-基于stm32(11)任务通知及相关API函数简介
  • 12306 火车票价格解析 (PHP 解析)
  • 洛谷 P1008 [NOIP1998 普及组] 三连击
  • 被拷打已老实!面试官问我 #{} 和 ${} 的区别是什么?
  • 算法金 | 再见!!!梯度下降(多图)
  • 力扣469A
  • C++ 50 之 继承中的对象模型
  • 就因为没在大屏项目加全屏按钮,早上在地铁挨了领导一顿骂
  • 分享的文章《人生如棋》
  • 【面试系列】之二:关于js原型
  • 345-反转字符串中的元音字母
  • 5分钟即可掌握的前端高效利器:JavaScript 策略模式
  • Bytom交易说明(账户管理模式)
  • CSS中外联样式表代表的含义
  • EventListener原理
  • Java Agent 学习笔记
  • nodejs:开发并发布一个nodejs包
  • SOFAMosn配置模型
  • 百度小程序遇到的问题
  • 分布式任务队列Celery
  • 关于 Linux 进程的 UID、EUID、GID 和 EGID
  • 基于Android乐音识别(2)
  • 基于MaxCompute打造轻盈的人人车移动端数据平台
  • 如何学习JavaEE,项目又该如何做?
  • 使用 5W1H 写出高可读的 Git Commit Message
  • 译米田引理
  • ​软考-高级-系统架构设计师教程(清华第2版)【第20章 系统架构设计师论文写作要点(P717~728)-思维导图】​
  • ‌[AI问答] Auto-sklearn‌ 与 scikit-learn 区别
  • ‌Excel VBA进行间比法设计
  • # Swust 12th acm 邀请赛# [ E ] 01 String [题解]
  • #if #elif #endif
  • #NOIP 2014# day.2 T2 寻找道路
  • #pragma data_seg 共享数据区(转)
  • #调用传感器数据_Flink使用函数之监控传感器温度上升提醒
  • #我与Java虚拟机的故事#连载11: JVM学习之路
  • $redis-setphp_redis Set命令,php操作Redis Set函数介绍
  • (5)STL算法之复制
  • (delphi11最新学习资料) Object Pascal 学习笔记---第2章第五节(日期和时间)
  • (Java企业 / 公司项目)点赞业务系统设计-批量查询点赞状态(二)
  • (附源码)spring boot北京冬奥会志愿者报名系统 毕业设计 150947
  • (附源码)springboot炼糖厂地磅全自动控制系统 毕业设计 341357
  • (每日一问)设计模式:设计模式的原则与分类——如何提升代码质量?
  • (欧拉)openEuler系统添加网卡文件配置流程、(欧拉)openEuler系统手动配置ipv6地址流程、(欧拉)openEuler系统网络管理说明
  • (三)模仿学习-Action数据的模仿
  • (一)使用IDEA创建Maven项目和Maven使用入门(配图详解)
  • (原)Matlab的svmtrain和svmclassify
  • (原創) 如何解决make kernel时『clock skew detected』的warning? (OS) (Linux)
  • (转)Android学习笔记 --- android任务栈和启动模式