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

初识C++ · 模拟实现string

news 来源：原创 2024/9/30 2:18:24

目录

1 构造 析构 拷贝构造 赋值

1.1 构造

1.2 析构

1.3 拷贝构造

1.4 赋值

2 迭代器

3 capacity部分

3.1 size capacity clear

3.2 resize reserve

4 [] const[] c_str的实现

4.1 push_back

4.2 append

4.3 +=

4.4 insert

4.5 erase

5 string operations部分

5.1 find

5.2 substr

6 6个全局函数->比较

7 几个非成员函数

7.1 swap

7.2 流插入

7.3 流提取

8 现代写法

继上文介绍了string的函数实现之后，本文介绍模拟实现string的大部分函数。

1 构造 析构 拷贝构造 赋值

1.1 构造

构造函数需要考虑的是无参和有参的构造不一样，所以我们可以使用函数重载实现两个构造函数，一个用来写无参构造，一个用来写const char*的：

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

对于无参的构造，即是一个空串，所以_size _capacity都要给0，但是为什么还要给一个空间呢？为什么不给指针呢？因为即便是空串，里面也是有'\0'的，所以需要一个空间。

		string(const char* s):_size(strlen(s)),_capacity(_size)//注意声明次序问题,_str(new char[strlen(s) + 1])//保证斜杠0{strcpy(_str, s);}

对于有参的构造，注意的地方应该是声明次序以及_str指向的空间，因为_capacity是等于_size，所以声明的时候是_size在前，不然给_capacity的值就是随机值了，然后_str指向的空间应该要给斜杠0预留一个位置，所以是strlen(s) + 1：

class strin
{
public://...
private:size_t _size;size_t _capacity;char* _str;
};

但是实际上，我们不用写上两个函数，可以将两个函数合二为一：

string(const char* str = "")//合二为一来个缺省值:_size(strlen(str)),_capacity(_size), _str(new char[strlen(str) + 1])
{strcpy(_str, str);
}

_size和_capacity的赋值问题不用多说，const char* str = ""可能是比较容易出错的点，当我们想要构造一个空串的时候，给_str的值就是一个""，部分同学会写的五花八门，比如const char* str = '\0'，又或者是const char* str = "\0”，一个是char一个是char*不能赋值，一个是两个斜杠0，这里最好的写法就是这样，直接给一个空串就行了，然后strcpy即可。

1.2 析构

析构函数就简单了，没什么要特别注意的：

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

1.3 拷贝构造

使用拷贝构造的时候，就容易引出一个问题，即深浅拷贝的问题，如果我们只是简单的浅拷贝的一下，即两个_str指向的空间是一样的，那么带来的后果是很严重的，比如:

	void Test_string(){string s1("123456");string s2(s1);s1[2] = 'x';cout << s1 << endl;cout << s2 << endl;}

他们指向的空间是一样的，那么修改的时候就会一并修改了，并且同一块空间都会析构两次，所以会报错：

所以我们要执行深拷贝，那么就是，给s2新开一块空间，再把s1的值赋值给它：

		string(const string& s){_str = new char[s.capacity() + 1];strcpy(_str, s._str);_size = s._size;_capacity = s._capacity;}

这样，就是深拷贝。

1.4 赋值

赋值问题，如果被赋值的串是空串，其实和拷贝构造函数没有什么太大的差别，但是大多数时候被赋值的串都是有值的，所以我们需要做的是拷贝构造一个临时变量，赋值给临时变量，释放被赋值的对象的原来的空间，再进行赋值。

	string& operator=(const string& s){char* tmp = new char[s._capacity + 1];strcpy(tmp, s._str);delete[] _str;_str = tmp;_size = s._size;_capacity = s._capacity;return *this;}

目前赋值和拷贝构造都是比较传统的写法，后面介绍了swap，你就知道现代写法写起来有多舒服了。

2 迭代器

在string这里，实现的迭代器我们可以理解为指针，所以实现起来很简单，这里就实现begin end和cbegin cend：

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

这个命名也是比较关键的，比如模拟实现顺序表的时候，重命名的又是另外的名字了，这也是为什么迭代器类型如此吓人的原因。

这里的实现是超乎你想象的简单的，所以不做过多介绍。

3 capacity部分

这里模拟实现size,resize,capacity,reserve,clear部分。

3.1 size capacity clear

size_t capacity() const
{return _capacity;
}
size_t size() const
{return _size;
}
void clear()
{_str[_size] = '\0';_size = 0;
}

其中clear的模拟实现我们不用想的太多复杂，直接给第一个字符置为斜杠0，也就达到了我们想要的效果

3.2 resize reserve

reserve的实现是影响的capacity，但是其他的不会变，这里也不用考虑缩容，考虑扩容即可，容易出错的点在于如何理解扩容，部分同学理解的可能是直接给原来的空间后面接上一段空间，实际上不是，大部分都是异地扩容的，所以需要我们重新开空间：

void reserve(size_t new_capacity)
{if (new_capacity > _capacity){char* tmp = new char[new_capacity + 1];_capacity = new_capacity;strcpy(tmp, _str);delete[] _str;_str = tmp;}//缩容一般不考虑
}

resize的实现是影响的size，再是间接的影响capacity，如果_size比原来的_size小的话是比较简单的，直接点就是一刀砍死，即在新_size的位置上给一个'\0'就可以了，那么如果是扩大，就在扩大之后的_size里面补上字符就行了，同时考虑需不需要扩容，最后不要忘记补个'\0'：

	void resize(size_t new_size,char ch = '\0'){//new_size < _size直接砍死if (new_size < _size){_str[new_size] = '\0';_size = new_size;}else{reserve(new_size);for (int i = _size; i < new_size; i++){_str[i] = ch;}_str[new_size] = '\0';//估摸着得忘}}

4 [] const[] c_str的实现

const char* c_str() const
{return _str;
}
char& operator[](size_t pos)
{assert(pos < _size);return _str[pos];
}
const char& operator[](size_t pos)const
{assert(pos < _size);return _str[pos];
}

常用，并且简单，很容易实现。

5 Modifiers部分

这里介绍push_back,append,insert,erase,+=，swap函数。

4.1 push_back

push_back即尾插，需要考虑size == capacity，那么涉及扩容就扩容二倍就行，因为有时候是空串，所以扩容的时候可以使用三木操作符，当然，补'\0'也是很重要的，不能忘记。

void push_back(char ch)
{考虑扩容 二倍扩容即可if (_size == _capacity){reserve(_capacity == 0 ? 4 : 2 * _capacity);}_str[_size++] = ch;_str[_size] = '\0';
}

4.2 append

append即在末尾插入一个字符串，这里有两个思路，第一种是一直尾插，即一直调用push_back，第二种是判断出所需要空间，然后扩容，再使用字符函数strcpy直接进行插入：

void append(const char* s)
{size_t len = strlen(s);if (_size + len > _capacity){reserve(_size + len);}strcpy(_str + _size, s);_size += len;
}

第一种思路就留给读者进行实现了，也是比较容易的，注意，这里的第二种思路是不可以只考虑二倍的，会出错，思维不能固化。

4.3 +=

+=有了前面两个函数的基础就很简单了：

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

是的，没有了。

4.4 insert

insert有两个版本，一个是任意位置插入字符，一个是任意位置之前插入字符串，这里比较容易出现的问题是循环问题及斜杠0的问题，扩容问题同push_back就可以了，插入一个字符的时候，我们应该将该位置之后的字符全部往后移动一个单位，同理，插入一个字符串的时候，就应该移动字符串个的长度个单位，先来看第一种:

void insert(size_t pos, char ch)
{assert(pos <= _size);if (_size == _capacity){reserve(_capacity == 0 ? 4 : 2 * _capacity);}size_t end = _size;while (end >= pos){_str[end + 1] = _str[end];--end;}_str[pos] = ch;++_size;
}

代码逻辑是没有什么大问题的，这里要注意的就是循环体，在平时，我们循环的元素类型都是int一类的，但是在string里面，size_t是很常见的，size_t不用多介绍吧，是无符号整型，即最小都是0，那么这个部分，除了头部的插入都是没有问题的，一旦是头插，那么在最后一步就会出岔子，因为pos是0，所以想要结束循环end就应该为-1，但是end不可能为-1，end = 0的下一步，减减的时候就会出问题，end会直接到42亿多（32位平台下），因为类型，好了，这里有人说把end改为int类型的不就好了，改了仍然会出问题，因为pos也是size_t类型的时候，比较的时候就会发生转换，即end还是会变为size_t类型的，那么这里的第一个解决方案就是把pos强转为int，为什么不在参数位置就设置为int呢？因为下标不可能为负数，所以：

int end = _size;
while (end >= (int)pos)
{_str[end + 1] = _str[end];--end;
}

这是第一种解决方式。

第二种解决方法是在end上面操作，即让end在0的时候结束就行了，这里思维稍微跳跃一点点:

size_t end = _size + 1;
while (end > pos)
{_str[end] = _str[end - 1];--end;
}

慢慢体会~

Tips:有了insert之后，前面的部分函数就可以进行复用了，比如，push_back ,append，所以说insert要放到最后实现呢：

void push_back(char ch)
{insert(_size, ch);
}
void append(const char* s)
{insert(_size, s);
}

4.5 erase

erase即删除，删除一段区间，当然这个区间长度也可以是1，文档记录的是如果没有给上参数，那么就是从该位置删完，所以要给上缺省值：

void erase(size_t pos, size_t len = npos)//删除一段区间
{assert(pos < _size);//可能存在溢出//npos - 1 + 未知数if (len == npos || len >= _size - pos){_str[pos] = '\0';}else{//while循环可以控制，但是有点麻烦strcpy(_str + pos, _str + pos + len);}_size -= len;
}

可以看到这里需要注意的问题有，向上溢出的问题，如果代码是len + pos >= _size，当pos是npos - 1，那么随便加个数就会导致向上溢出，这里的解决方法也是很简单，移项的事。

删除之后赋值，可以选择两种方法，一是直接使用strcpy，二是使用循环控制，将每个字符挨个挨个的存进去，当然比较麻烦，不太推荐。

当然，npos这里也是要自己声明，自己定义的。

5 string operations部分

上面实现了c_str,这里就实现find,substr即可。

5.1 find

find的重载可以找字符，也可以找字符串，所以需要模拟实现两个，模拟实现字符的函数简单，即匹配然后返回对应下标就可以了：

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

模拟实现字符串的返回下标有一点点难度，这里需要用到指针的运算，即指针相减 / 指针指向的类型是个数，这里也要复用到C语言的函数，strstr，使用字符串匹配，要是模拟实现strstr，就麻烦许多了：

size_t find(const char* sub, size_t pos = 0)const
{assert(pos < _size);//函数strstrconst char* p = strstr(_str + pos, sub);if (p){return p - _str;}else{return npos;}
}

5.2 substr

substr即是从pos位置开始，返回后面的字符串，返回字符串我们的第一个想法可能是返回该位置的指针，但是文档里面substr返回类型是string，所以我们也要返回string，这里就可以单独创建一个string变量，再复用+=，最后返回即可：

string substr(size_t pos = 0, size_t len = npos)
{string sub;//len + pos 向上溢出!!擦if (len >= _size - pos){for (size_t i = pos; i < _size; i++){sub += _str[i];}}else{for (size_t i = pos; i < pos + len; i++){sub += _str[i];}}return sub;
}

6 6个全局函数->比较

这里就和日期类是一样的，比较的时候我们只用实现一个，后面的所有比较函数复用前面的函数就可以了，这里的比较函数有 > < == != >= <=：

//几个全局函数
bool operator==(const string& s1,const string& s2)
{return !strcmp(s1.c_str(),s2.c_str());
}
bool operator<(const string& s1, const string& s2)
{return (strcmp(s1.c_str(), s2.c_str())) < 0;
}
bool operator>(const string& s1, const string& s2)
{return (strcmp(s1.c_str(), s2.c_str())) > 0;
}
bool operator<=(const string& s1, const string& s2)
{//return (s1 < s2) || (s1 == s2);return !(s1 > s2);
}
bool operator>=(const string& s1, const string& s2)
{return !(s1 < s2);
}	
bool operator!=(const string& s1, const string& s2)
{return !(s1 == s2);
}

比较的时候是按照字典序比较的，所以使用的函数是strcmp，

7 几个非成员函数

这里实现流插入和流重载以及swap。

7.1 swap

swap的使用是有讲究的，如果我们平时使用的时候使用std库里面的swap函数，那代价可就大了去了：

库里面的函数模板，使用的使用会自动识别类型，所以会发生拷贝构造，也会有析构的调用，一共是三次拷贝一次析构，但是对于内置类型的交换是很容易的，所以我们模拟实现string里面的交换的时候，就可以使用这个函数：

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

交换自定义类型无非就是交换空间，交换类里面的内置类型。

7.2 流插入

流插入很好实现，流提取的坑就比较多了：

	ostream& operator<<(ostream& out, const string& s){out << s.c_str();return out;}

这里实现的流插入和日期类实现的流插入基本上是一样的。

7.3 流提取

代码先直接给上：

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

有如下要注意的点，

一是clear的调用，流提取本身是覆盖，所以我们需要把字符串原来的值给清除了，再进行提取。

二是提取是使用cin还是scanf还是？如果我们使用cin或者是scanf，就会导致空格读取不了，因为cin和scanf都是默认空格或换行都是字符串的结束标志，但是它们都是默认不读取的，所以这里使用的读取是io流里面的一个函数->get()，这个函数是可以读取空格或换行的，所以，使用这个函数。

三是为什么使用buff数组，因为我们不知道读取多少个字符，如果频繁调用insert或者其他函数会对效率影响挺大，插入扩容都是会消耗效率的，所以这里使用一个很奇妙的思路，使用一个数组，存满了清0重新存入即可，最后再给上斜杠0。

8 现代写法

string& operator=(string ss)
{swap(ss);return *this;
}
//现代写法 详细
string& operator=(const string& s)
{string ss(s);swap(ss);return *this;
}	
string(const string& s)
{string tmp(s._str);swap(tmp);
}

赋值，使用swap，将我们需要的值给上一个临时变量，再把这临时变量的值交换给我们被赋值的变量，代码十分的简洁，并且nb。

拷贝构造同理可得，效率方面其实差别不大，但是这个思路很厉害，可以借鉴一下。

感谢阅读！

相关文章：

  • 力扣106. 从中序与后序遍历序列构造二叉树
  • 代码随想录算法训练营第五十三天||1143.最长公共子序列、1035.不相交的线、53. 最大子序和
  • 20240523金融读报：跨境支付规模扩大银行服务科创企业举措
  • 摸鱼大数据——Hive表操作——分区表
  • 618有什么宠物空气净化器推荐？希喂FreAir Lite宠物空气净化器真实体验
  • linux系统部署Oracle11g：netca成功启动后1521端口未能启动问题
  • 论文精读：TASKBENCH: BENCHMARKING LARGE LANGUAGE MODELS FOR TASK AUTOMATION
  • 什么是知识中台？为什么企业需要知识中台？
  • js检验一个字符串是否是正确时间格式的工具方法
  • Linux信号机制与docker应用
  • OrangePi AIpro初识及使用大模型GPT-Neo-1.3B测试
  • 常见排序算法之插入排序
  • leetcode——169.多数元素（多解法）
  • 回溯算法05（leetcode491/46/47）
  • 消防体验馆升级，互动媒体点亮安全之路！
  • 时间复杂度分析经典问题——最大子序列和
  • [NodeJS] 关于Buffer
  • axios 和 cookie 的那些事
  • iOS 系统授权开发
  • IOS评论框不贴底（ios12新bug）
  • java中具有继承关系的类及其对象初始化顺序
  • Node项目之评分系统（二）- 数据库设计
  • PHP的Ev教程三(Periodic watcher)
  • 关于 Cirru Editor 存储格式
  • 开源SQL-on-Hadoop系统一览
  • 聊聊flink的TableFactory
  • 每天一个设计模式之命令模式
  • 前端 CSS : 5# 纯 CSS 实现24小时超市
  • 由插件封装引出的一丢丢思考
  • 正则表达式小结
  • 阿里云ACE认证学习知识点梳理
  • ​ubuntu下安装kvm虚拟机
  • ​一文看懂数据清洗：缺失值、异常值和重复值的处理
  • # Swust 12th acm 邀请赛# [ K ] 三角形判定 [题解]
  • $(document).ready(function(){}), $().ready(function(){})和$(function(){})三者区别
  • $.each()与$(selector).each()
  • （免费领源码）Java#ssm#MySQL 创意商城03663-计算机毕业设计项目选题推荐
  • （亲测有效）解决windows11无法使用1500000波特率的问题
  • (全注解开发)学习Spring-MVC的第三天
  • （四）【Jmeter】 JMeter的界面布局与组件概述
  • （四）搭建容器云管理平台笔记—安装ETCD(不使用证书)
  • . ./ bash dash source 这五种执行shell脚本方式 区别
  • .NET Project Open Day(2011.11.13)
  • .NET 反射 Reflect
  • .Net（C#）常用转换byte转uint32、byte转float等
  • .NET/C# 使用 #if 和 Conditional 特性来按条件编译代码的不同原理和适用场景
  • .pyc文件还原.py文件_Python什么情况下会生成pyc文件？
  • @JsonSerialize注解的使用
  • [ CTF ] WriteUp-2022年春秋杯网络安全联赛-冬季赛
  • [20170713] 无法访问SQL Server
  • [BZOJ1178][Apio2009]CONVENTION会议中心
  • [ERROR] Plugin 'InnoDB' init function returned error
  • [Git].gitignore失效的原因
  • [GN] 后端接口已经写好 初次布局前端需要的操作（例）
  • [HarekazeCTF2019]encode_and_encode 不会编程的崽