CD38.【C++ Dev】string类的模拟实现(2)

已于 2025-05-17 09:16:02 修改
阅读量1k 收藏 19
点赞数 40
分类专栏： C++ Develop 文章标签： c++ 开发语言
于 2025-05-14 14:09:03 首次发布
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/2401_85828611/article/details/147846890
版权

目录

1.append

测试代码

2.operator+=

string& operator+= (char c)

string& operator+= (const char* s)

测试代码

★3.insert

​编辑

string& insert (size_t pos, size_t n, char c)

​编辑

算法

1.首先要挪动数据,为插入的字符串腾出空间

2.插入n个字符

测试代码

string& insert(size_t pos, const char* s)

测试代码

3.erase

分析

完整代码

测试代码

4.find

size_t find(char c, size_t pos = 0) const

 size_t find(const string& str, size_t pos = 0) const

测试代码

5.substr

拷贝构造函数

substr

测试代码

承接CD37.【C++ Dev】string类的模拟实现(1)文章

1.append

依照STL标准实现,为了简单起见只实现第一个:

append是追加字符串,追加字符串之前先考虑空间够不够:
设追加的C语言风格的字符串的有效长度为len,则追加后字符串的有效长度为_size+len,比较它与_capacity的大小即可,如果大于_capacity,应该至少扩容到_size+len

string& append(const char* str)
{
	size_t len = strlen(str);
	if (len + _size > _capacity)
		reserve(len + _size);
	memmove(_str + _size, str, len+1);
	_size += len;
	return *this;
}

注意:memmove的第3个参数应该为len+1,因为strlen不会将\0计入在内,因此len+1的+1是为\0准备的

测试代码

void test8()
{
	mystl::string str("abc");
	str.append("defghijklmn");
	for (char it : str)
		std::cout << it;
	return;
}

运行结果:

2.operator+=

依照STL标准实现,为了简单起见只实现其中两个:

string& operator+= (char c)

直接复用push_back的代码:

string& operator+=(char c)
{
	push_back(c);
	return *this;
}

string& operator+= (const char* s)

直接复用append代码:

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

测试代码

void test9()
{
	mystl::string str("abc");
	str += 'd';
	str += "edf";
	str += 'g';
	str +="hijklmn";
	for (char it : str)
		std::cout << it;
	return;
}

运行结果:

★3.insert

依照STL标准实现,为了简单起见只实现其中两个:

string& insert (size_t pos, size_t n, char c)

 1.pos必须合法

assert(pos <= _size);

2.插入前需不需要扩容

if (pos + n > _capacity)//注意不是和_size比较
	reserve(pos + n);//至少扩容到pos + n

扩容后,未插入字符串前:

插入n个字符后:

算法

1.首先要挪动数据,为插入的字符串腾出空间

那么黄色区域的位置为i的元素要挪动到位置i+n,从最后一个字符\0开始挪动,避免覆盖丢失数据,

一共需要移动_size-(pos+1)+1==_size-pos次,即当i==pos时停止移动数据

size_t i = _size;//_str[i]为\0
while (i>=pos)
{
	_str[i + n] = _str[i];
	i--;
}
2.插入n个字符

while循环执行结束后,i==pos-1,i需要++变成pos才能复制n个字符,不要忘记修改_size!

//i==pos-1
i++;//之后i==pos
while (i < pos + n)
	_str[i++] = c;
_size += n;

当然也可以使用memset让代码更简洁

有关memset的用法参见文章:

60.【C语言】内存函数(memset,memcmp函数)

CC8.【C++ Cont】使用memset和memcpy来设置数组

memset(_str + pos, c, n);
_size += n;

错误代码:

string& insert(size_t pos, size_t n, char c)
{
	assert(pos <= _size);
	if (pos + n > _capacity)//注意不是和_size比较
		reserve(pos + n);//至少扩容到pos + n
	size_t i = _size;//_str[i]为\0
	while (i>=pos)
	{
		_str[i + n] = _str[i];
		i--;
	}

	//i==pos-1
	i++;//之后i==pos
	while (i < pos + n)
		_str[i++] = c;
	_size += n;
	return *this;
}

上方代码有没有问题?

答:有,当pos==0时插入会失败!

 由于i是size_t类型,即无符号整型,取值范围是0~0xFFFFFFFF,当i为0时,循环最后i--,i不会变成-1,而是size_t类型的最大值!

提醒:不能将i定义为int,因为while (i>=pos)在比较时,i为int类型,pos为size_t类型,编译器会首先整型提升:将i转化为size_t类型(范围小的提升到范围大的),会导致i==-1仍然在循环

解决方法1:强制类型转换,改成while (i>=(int)pos)

解决方法2:while循环的条件需要多加一个i!=string::npos

注:STL库中npos是静态变量,定义为-1

注意静态变量需要在类中声明,在类外定义,用const修饰

//......	
    	const static size_t npos;
	};
	const size_t string::npos = -1;
}

正确代码:

string& insert(size_t pos, size_t n, char c)
{
	assert(pos <= _size);
	if (pos + n > _capacity)//注意不是和_size比较
		reserve(pos + n);//至少扩容到pos + n
	size_t i = _size;//_str[i]为\0
	while (i>=pos&&i!=npos)
	{
		_str[i + n] = _str[i];
		i--;
	}

	memset(_str + pos, c, n);
	_size += n;
	return *this;
}

测试代码

void test10()
{
	mystl::string str("abc");
	str.insert(3, 5, 'x');
	for (char it : str)
		std::cout << it;
	std::cout << std::endl;
	str.insert(2, 5, 'y');
	for (char it : str)
		std::cout << it;
	return;
}

运行结果:

string& insert(size_t pos, const char* s)

把上方代码的n定义为strlen(s),同时把memset改成memmove(_str+pos,s, n);

string& insert(size_t pos, const char* s)
{
	size_t n = strlen(s);
	assert(pos <= _size);
	if (pos + n > _size)
	{
		reserve(pos + n);
	}
	size_t i = _size;//_str[i]为\0
	while (i >= pos&&i!=npos)
	{
		_str[i + n] = _str[i];
		i--;
	}

	memmove(_str+pos,s, n);
	_size += n;
	return *this;
}

测试代码

void test11()
{
	mystl::string str("abc");
	str.insert(1, "def");
	for (char it : str)
		std::cout << it;
	std::cout << std::endl;
	str.insert(4, "ghi");
	for (char it : str)
		std::cout << it;
	return;
}

运行结果:

3.erase

分析

依照STL标准实现,为了简单起见只实现其中一个:

发现第二个参数是缺省参数,调用者如果没有给第二个参数,会默认删到最后

首先pos的取值必须合法,因此先判断筛去不合理的情况:

assert(pos <= _size);

满足pos<=_size的几种情况:

1.pos<_size

 

这3种情况只需要用\0修改并修改_size:

if (pos + len >= _size)
{
	_str[pos] = '\0';
	_size = pos;
}

上面这样写有没有问题?

答:有,当len == npos时会出问题,因为npos是size_t类型的最大值,根据size_t的回绕性或者称为截断特性,pos+len可以小于_size

回绕性(截断特性)的证明:

int main()
{
	size_t val = 0xFFFFFFFF;
	val++;
	return 0;
}

单步调试,看看val在内存中的值:

 pos+len可以小于_size的原因:

举例:pos==2,len==npos,_size==5,此时pos+len==1<5

需要改成:

if (len == npos || pos + len >= _size)
{
	_str[pos] = '\0';
	_size = pos;
}
else
{
    //pos + len < _size
}

注:依据||的短路原理,len == npos必须先判断!

2.pos==_size

此时len无论取何值,都没有字符需要删除

pos + len < _size的代码:

size_t i = pos + len;
while (i < _size)
	_str[pos++] = _str[i++];
_str[pos + len] = '\0';
_size -= len;

完整代码

string& erase(size_t pos = 0, size_t len = npos)
{
	assert(pos <= _size);
	if (len == npos || pos + len >= _size)
	{
		_str[pos] = '\0';
		_size = pos;
	}
	else
	{
		size_t i = pos + len;
		while (i < _size)
			_str[pos++] = _str[i++];
		_str[pos + len] = '\0';
		_size -= len;
	}
	return *this;
}

测试代码

void test12()
{
	mystl::string str1("teststring1");
	mystl::string str2("teststring2");
	str1.erase(4);
	str2.erase(3,3);
	for (char it : str1)
		std::cout << it;
	std::cout << std::endl;
	for (char it : str2)
		std::cout << it;
	return;
}

运行结果:

4.find

依照STL标准实现,为了简单起见只实现其中两个:

注意到最后都写了const,因为find没有修改字符串

size_t find(char c, size_t pos = 0) const

注意pos要合法

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

 size_t find(const string& str, size_t pos = 0) const

作用:查找子字符串

可以直接调用strstr函数,对其返回值作不同处理即可

由于strstr只接收char*或const char*型的参数,str需要取它的C语言类型的字符串,使用c_str函数,注意pos要合法

size_t find(const string& str, size_t pos = 0) const
{
    assert(pos < _size);
	const char* ret_ptr = strstr(_str, str.c_str());
	if (ret_ptr == nullptr)
		return npos;
	return ret_ptr - _str;
}

测试代码

void test13()
{
	mystl::string str("teststring");
	std::cout << str.find('s', 1) << std::endl;
	std::cout << str.find("str", 1) << std::endl;
	std::cout << str.find("abc", 4) << std::endl;
	return;
}

运行结果:

5.substr

依照STL标准实现,注意到最后写了const,因为substr没有修改字符串 

pos要合法,首先断言,按照erase函数分类讨论的思想写substr,由于返回类型为string,因此程序会自动调用拷贝构造函数,那么这里先写拷贝构造函数

拷贝构造函数

代码

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

注意: 1.正确设置几个参数,使用memmove更方便,但不能使用strcpy, 2.一定不能使用默认的拷贝构造函数,浅拷贝,局部对象一出作用域就销毁了,会出问题,

substr

代码

string substr(size_t pos = 0, size_t len = npos) const
{
	assert(pos < _size);
	string ret;
	ret._size = len;
	if (len == npos || pos + len >= _size)//从pos处截取到末尾
		ret._size = _size - pos;

	ret.reserve(ret._size);
	memmove(ret._str, _str + pos, ret._size);
		
	if (ret._str[ret._size] != '\0')
		ret._str[ret._size] = '\0';
	return ret;
}

注意memove截取的字符串很有可能没有\0,因此需要判断,如果没有就在ret._str[ret._size]上补\0,成为有效字符串

测试代码

void test14()
{
	mystl::string str("teststring");
	mystl::string ret1 = str.substr(4);
	mystl::string ret2 = str.substr();
	mystl::string ret3 = str.substr(2,3);

	for (char it : ret1)
		std::cout << it;
	std::cout << std::endl;
	for (char it : ret2)
		std::cout << it;
	std::cout << std::endl;
	for (char it : ret3)
		std::cout << it;
	return;
}

执行结果:

评论
添加红包

请填写红包祝福语或标题

个

红包个数最小为10个

元

红包金额最低5元

当前余额3.43元 前往充值 >
需支付：10.00元
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包

打赏作者

zhangcoder

赠人玫瑰手有余香,感谢支持~

¥1 ¥2 ¥4 ¥6 ¥10 ¥20
扫码支付：¥1
获取中
扫码支付

您的余额不足，请更换扫码支付或充值

打赏作者

实付元
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明：

1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载，可以购买VIP、付费专栏及课程。

余额充值