C++:STL详解(二)string类的模拟实现
白乐天_ξ( ✿>◡❛) 2024-10-21 15:35:02 阅读 92
✨ Blog’s 主页: 白乐天_ξ( ✿>◡❛)
🌈 个人Motto:他强任他强,清风拂山冈!
💫 欢迎来到我的学习笔记!
🔥🔥🔥🔥🔥本文参考文章:【C++】深入浅出STL之string类
一、成员函数
1.1 框架建立
首先我们要先建立一个框架,确定各个文件实现什么。
<code>string.h用于实现声明和类的声明与定义;string.cpp
用于实现具体的定义、功能;test.cpp
用于测试实现的功能师傅正确,能否使用等。
为了不和库中的string类发生冲突,我们可以在其外层套上一层Harper
的命名空间。
//string.h:声明文件
#pragma once
#include <iostream>
#include <assert.h>
#include <string>
using namespace std;
namespace Harper
{ -- -->
class string// 类在此处实现
{
public:
// 在这里实现部分功能以及功能的声明…………
private:
char* _str;
size_t _size;
size_t _capacity;
};
}
//string.cpp:实现文件
#define _CRT_SECURE_NO_WARNINGS 1
#include "string.h"
namespace Harper
{
// 在这里实现具体功能(即功能的定义)…………
}
//test.cpp:测试文件
#define _CRT_SECURE_NO_WARNINGS 1
#include "string.h"
int main()
{
// 在这里进行各个实现的功能的测试
return 0;
}
1.2 构造函数
然后我们要在
string.h
中实现string
类的构造函数。
构造函数主要分为无参构造函数、带参构造函数、全缺省构造函数。首先我们先实现无参构造函数。我们默认给_size
和_capacity
的大小为0
,字符数组先开辟一个空间,然后初始化为字符\0
。
// string.cpp
// 无参构造函数
string()
:_size(0)
, _capacity(0)
,_str(new char[1]) // 申请空间使用new,不要再malloc了
{
_str[0] = '\0';
}
由于自主实现的string类在命名空间Harper
中,因此我们在使用此类时需要使用域作用限定符::
。运行结果:
我们写了无参构造,就必须写带参构造,可以看到我们在初始化<code>_size时先去计算了字符串str
的长度,因为_size
取值范围为到\0
为止不包括\0
的有效数据个数,那么strlen
可以实现这个效果。在_str
这里我们为其开出的就是【空间容量大小 + 1】,最后再拷贝有效数据到该空间中,即使用strcpy
。
// 带参构造函数
string(const char* str)
:_size(strlen(str))
, _capacity(_size)
, _str(new char[_capacity + 1])// 开辟空间:多开一个??????
{ -- -->
strcpy(_str, str);// 拷贝数据
}
// test.cpp
void TestString1()
{
Harper::string s1("Hello\0world");
cout << s1.c_str() << endl;
}
运行结果:
再改进为函数体内实现,使用<code>""空字符串(中间没没有空格)来进行初始化,末尾隐藏了一个\0
。strcpy()
拷贝不到\0
,strcpy
拷贝到\0
就发生终止而不在继续拷贝了。
string(const char* str = "")// 使用空字符串进行初始化,它还可以提供一个\0
{ -- -->
_size = strlen(str);
_capacity = _size;
_str = new char[_capacity + 1];
// memcpy(_str, str, _size + 1);
strcpy(_str,str);
}
// test.cpp
void TestString1()
{
Harper::string s1("Hello\0world");
cout << s1.c_str() << endl;
}
strcpy()
函数运行结果:(先注释掉前两个构造函数)
<code>memcpy()函数运行结果:
注意:构造函数中的参数写成下面,输出结果仍然是空串,这样写不太好!
<code>string(const char* str = "\0")
如果写成下面这样也是不行的!因为
strlen()
调用的时候就会发生空指针异常!
string(const char* str = nullptr)
总结:
//string.h
string (const char* str = ""})// 写全缺省,没有空格d
{ -- -->
_size = strlen(str);
_capacity = _size;// _size不能+1,_capacity不包含\0,因此下面一句代码开辟空间时多加一个
_str = new char[_capacity + 1];// 这里才+1
strcpy(_str, str);// 功能:先拷贝,再判断,遇到\0停止,且会拷贝\0
}
注意1:这里最好不要使用初始化列表进行初始化。
原因:变量初始化的顺序是private
中的声明顺序,所以我们最好设置初始化列表的顺序位声明顺序,避免出现用未初始化的随机值来进行初始化。而且,我们是建议使用初始化列表进行初始化,但是也不是什么时候都必须用它来初始化的,毕竟成员变量定义时会自动走一遍初始化列表。 注意:_size
不能+1,_capacity
需要+1。
原因:_size
记录的是_str
的长度,但是_capacity
中不包含\0
,因此它需要+1。 注意3:在初始化列表中,_str
即使为空,也不能直接使用nullptr
来初始化。
原因:空_str
是用空指针定义初始化的,char*
不会按照指针打印,而是会空指针解引用去找字符,遇到\0
了才会停止。空_str
在string
中崩溃,在库中不打印无输出。正确的初始化方式:(在初始化列表里)new char[1]{'\0'}
。(在string函数参数里)const char* str = ""
。空间只有一个字符\0
。 小技巧:加入<string>
头文件,就可以std::string s1;
来观察库并做比较。
1.3 打印输出函数
我们在
string.h
文件中的string类里面实现打印输出函数c_str()
。
我们实现它是因为目前还没有实现流提取流插入。
const char* c_str() const
{
return _str;
}
1.4 拷贝构造函数
接着就是拷贝构造函数相关的内容!
在【链接:六大拷贝构造函数】中我们知道:如果一个类没有显示定义拷贝构造函数,那么它对内置类型就不做处理,而对于自定义类型就会去调用类中的默认拷贝构造函数。此时就会产生“浅拷贝”的问题。使用浅拷贝会出现调用两次析构
的情况。因此,我们需要自己实现拷贝构造函数,在这里拷贝数据也是使用的memcpy()
。
// 显示实现拷贝构造函数
string(const string& s)
{
_str = new char[s._capacity + 1];// 先开辟新空间,修改变量
memcpy(_str, s._str, s._size);// 再存放数据,拷贝数据
_size = s._size;
_capacity = s._capacity;
}
现在再去调试观察 ,可以发现s1
和s2
对象中存放的数据存放在不同的空间,无论修改还是析构都不会有影响。
还有一个版本的拷贝构造函数,这个在下面的赋值重载会继续提到。
<code>// 拷贝构造函数(新版本)
string(const string& s)
: _str(nullptr)
, _size(0)
, _capacity(0)
{ -- -->
string tmp(s._str);
// tmp出了当前函数作用域就销毁了,和this做一个交换
this->swap(tmp);
}
1.5 析构函数
下面我们在
string.h
里面实现string
函数的析构函数!
~string()
{
delete[] _str;
_str = nullptr;
_size = _capacity = 0;
}
原则:短小频繁使用的函数可以直接定义在类里面,默认是inline
;小函数就不用声明与定义分离了。
1.6 赋值运算符重载
赋值运算符重载也是类的默认成员函数之一,我们不写编译器会自动生成一个。
默认生成的复制运算符重载也会造成【浅拷贝】的问题。例如下面:我们打算执行``s1 = s3,但是没有为其开辟新的空间,导致
s1和
s3`都指向同一块空间,这样会出现下列问题:
在修改其中一个时,另一个会发生变化。(因为他们是同一块空间同一个地址)在进行析构时会造成二次析构
。原先的s1
所指向的空间没有进行维护,就会出现内存泄漏的问题。
现在我们应该:
先开辟一块新的空间,
将<code>s3 的内容拷贝到新空间里面,
然后再释放掉s1
指向的旧空间,
指向新的空间,
再改变变量的数据即可,
注意s1
和s3
是否为同一块空间,这样也就不用二者共同维护同一块空间,也就实现了【深拷贝】。
代码如下:
<code>string& operator=(const string& s)
{ -- -->
// 避免是同一块空间
if (this != &s)
{
char* tmp = new char[s._capacity + 1];// 1.开辟新空间
memcpy(tmp, s._str, s._size + 1);// 2.拷贝数据
delete[]_str;// 3.释放旧空间
_str = tmp;// 4.指向新空间
_size = s._size;// 5.改变变量值
_capacity = s._capacity;
}
//else// 是同一块空间
//{
// return *this;// 直接返回原来的空间,即可
//}
return *this;//直接写
}
这种写法还可以继续改进:也就是前面提到过的版本,仍然是是使用了深拷贝的。
// 赋值重载(初级版本)
string& operator=(const string& s)
{
if (this != &s)
{
string tmp(s);// 拷贝构造了一个临时对象tmp
this->swap(tmp);// 临时对象和s(当前对象)做交换
}
return *this;
}
在这里就使用到了swap()
,在讲【链接:C++初步学习模板】时提到过,swap()
是一个函数模板,可以自动推导函数的类型,去交换不同类型的数据。在这里我们自己实现swap(string& s)
函数,在这个函数中,我们调用了标准库std
中的函数然后交换一个string对象的所有成员变量。代码如下:
void swap(string& s)
{
// 将对象那个的成员变量一个一个地进行交换
std::swap(_str, s._str);
std::swap(_size, s._size);
std::swap(_capacity, s._capacity);
}
解释原理:(解释一下上上面代码的原理)我们在这个赋值重载的函数内部调用了拷贝构造去获取到一个临时对象tmp
,然后再通过swap()函数
去交换当前对象和tmp
的指向,此时s1
就刚好获取到赋值之后的内容,而tmp
则是一个临时对象,出了当前函数的作用域后自动销毁,那么原本s1
所维护的这块空间刚好就会销毁了,也不会造成内存泄漏的问题。
而这里,<code>tmp的作用就是拥有有效的资源,但是自己却用不到,扔了也是可惜,正好可以给这里需要的对象使用,离开作用域销毁也不会有影响。
还可以继续改进:代码如下:
// 赋值重载(究极版本)
string& operator=(string tmp)
{ -- -->
this->swap(tmp);
return *this;
}
使用传值传参,而不是传引用传参。 传值传参先去调用拷贝构造函数,会拷贝出一个临时对象,这正好就像我们在上一个版本写的一样:在函数内部调用拷贝构造函数。那么当外界在给函数传递参数时,tmp
就是外面这个对象的一个临时拷贝,我们直接操作此对象,也有同样的效果。(可以调试观察体验)回过头来看看之前实现的一个版本的拷贝构造函数。注意:这一版本的拷贝构造函数有缺陷在于初始化列表。如果我们没有手动地初始化成员变量,对于内置类型,编译器是不会做任何处理的;但对于自定义类型编译器则会去调用默认生成的拷贝构造函数,这样做很不安全!
// 拷贝构造函数(新版本)
string(const string& s)
: _str(nullptr)
, _size(0)
, _capacity(0)
{
string tmp(s._str);
// tmp出了当前函数作用域就销毁了,和this做一个交换
this->swap(tmp);
}
二、iterator迭代器
那么我们自己实现的函数能否支持
范围for
遍历呢?可以写一个测试代码来观察。
void TestString1()
{
string s1;
string s2("Hello world");
cout << s1.c_str() << endl;
cout << s2.c_str() << endl;
for (size_t i = 0; i < s2.size(); i++)
{
s2[i] += 2;// 先修改数据
}
cout << s2.c_str() << endl;// 输出字符串
// 范围for的底层就是迭代器,这里不支持范围for
for (auto e : s2)// error c2672: “begin”: 未找到匹配的重载函数
{
cout << e << " ";// 下面的迭代器修改好,上面的范围for就跟着好了,侧面证明了底层就是迭代器
}
cout << endl;
}
遍历访问一个string类对象的时候,出来
opeartor[]
还可以使用迭代器的形式进行遍历访问。
模拟迭代器的实现之前,我们要对迭代器的底层实现方式有所了解:
由上面可知,我们需要模拟实现两种迭代器:const的,非const的。现在我们开始迭代器的模拟实现:
首先我们需要谁用<code>typedef进行两个名称的修改;
typedef char* iterator;
typedef char* const_iterator;// const迭代器
然后就实现begin
和end
两个变量,分别是_str
指向的位置和_str+_size
指向的位置。
// 普通迭代器:
iterator begin()// begin返回第一个位置的迭代器
{ -- -->
return _str;
}
iterator end()// end返回末尾的迭代器
{
return _str + _size;
}
普通迭代器在函数参数列表末尾加上const
,改变迭代器名称为const_iterator
,就是const
对象的常量迭代器。
// const迭代器
const_iterator begin() const
{
return _str;
}
const_iterator end() const
{
return _str + _size;
}
首先我们来看看普通迭代器的使用:遍历string对象。
void TestString4()
{
Harper::string s1("hello");
Harper::string::iterator it = s1.begin();
while (it != s1.end())
{
cout << *it << " ";
++it;
}
}
运行结果:
接着我们看看常量迭代器的使用:常对象使用常量迭代器进行遍历。
<code>void TestString5()
{ -- -->
Harper::string s2("world");
Harper::string::const_iterator cit = s2.begin();
while (cit != s2.end())
{
cout << *cit << " ";
++cit;
}
}
运行结果:
小技巧:上面的代码中有一句比较繁琐,类型名称比较长,我们可以简化,直接使用<code>auto替代。
Harper::string::const_iterator cit = s2.begin();
// 替换成:
auto cit = s2.begin();
一个类只要支持迭代器就一定支持范围for
。
// 分别遍历两个string对象
for (auto ch : s1)
{ -- -->
cout << ch << " ";
}
cout << endl;
for (auto ch : s2)
{
cout << ch << " ";
}
总结:
// string.h
namespace Harper
{
class string
{
public:
typedef char* iterator;
typedef char* const_iterator;// const迭代器
// 原生指针来实现迭代器,迭代器模拟的是指针的行为!!!!!!
// 普通迭代器:
iterator begin()// begin返回第一个位置的迭代器
{
return _str;
}
iterator end()
{
return _str + _size;
}
// const迭代器
const_iterator begin() const
{
return _str;
}
const_iterator end() const
{
return _str + _size;
}
// 反向迭代器后面补充……
}
}
进行测试:
// test.cpp
void TestString1()
{
string s1;
string s2("Hello world");
cout << s1.c_str() << endl;
cout << s2.c_str() << endl;
for (size_t i = 0; i < s2.size(); i++)
{
s2[i] += 2;
}
cout << s2.c_str() << endl;
// 范围for底层就是迭代器,这里不支持,但是
// 但是下面的迭代器修改好,上面的范围for就跟着好了,侧面证明了底层就是迭代器
// 而且,如果将下面的begin换一个名字Begin,end,这里的范围for就失灵了
// 这里起始就是一个直接替换,并不会关心是怎么实现的
for (auto e : s2)// error c2672: “begin”: 未找到匹配的重载函数
{
cout << e << " ";
}
cout << endl;
// 类域里面进行typedef,iterator原名char*
// 这里在进行使用自己实现的迭代器遍历
string::iterator it = s2.begin();
while (it != s2.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
容器中的iterator都是typedef得来的,可能是指针可能是自定义类型,也可能是内置类型,例如:
vector<int>::iterator
。我们可以查看链表的底层,看看iterator
的原始类型(右击鼠标转到文档)。
为什么可以使用原生指针来实现迭代器而链表却不可以呢?
因为string的数组结构比较有优势。迭代器模拟的是指针的行为,如果结构是链表结构,就不能使用原生指针作为迭代器。因为链表结构以节点作为原生指针,++操作不能到下一个节点。
在类里面定义一个类型的方法:一种是内部类、一种就是<code>typedef,类名是别名。相当于是对char*
改了一个名叫做iterator
。自主分析一下代码。
迭代器的设计其实是一种封装思想:就像数据和方法放在类里面,公有私有保护等模块分开一样,迭代器提供了一种统一的类似的访问方式去访问容器、数据结构,我们不需要关系数据结构的底层细节(带头不带头,循环不循环,链表还是数组),迭代器直接屏蔽了底层实现细节。封装带来了遍历、互通。
三、capacity容量
3.1 size
直接返回`_size`即可,因为不会去修改成员变量,所以我们可以家还是那个一个【const】。size_t size() const// 普通对象和const对象都可以调用
{ -- -->
return _size;
}
3.2 reserve
接下来是有关于reserve扩容的内容。
当新容量大于旧容量的时候(即容量变大的时候),会去选择开辟空间。这里的扩容逻辑是
先开辟一块新空间,
然后再将原来的数据拷贝过来,
释放掉旧空间,
让_str
指向新空间,
最后更新一下变量的大小。 VS环境下实现1.5倍
的扩容。
void string::reserve(size_t n)// reserve一般只扩容不缩容,Linux下可以缩。官方文档说:capacity小的时候,reserve是不确定的
{
if (n > _capacity)
{
// 手动扩容:
char* tmp = new char[n + 1];//多开辟一个空间,给\0,因此后面就不用考虑\0的一个空间了
strcpy(tmp, _str);// 拷贝数据
delete[] _str;// 释放旧空间
_str = tmp;// 指向新空间
_capacity = n;// 修改变化后的数据
}
}
// 扩容(修改_capacity)
void reserve(size_t newCapacity = 0)
{
// 当新容量大于旧容量的时候,就开空间
if (newCapacity > _capacity)
{
// 1.以给定的容量开出一块新空间
char* tmp = new char[newCapacity + 1];
// 2.将原本的数据先拷贝过来
memcpy(tmp, _str, _size);
// 3.释放旧空间的数据
delete[] _str;
// 4.让_str指向新空间
_str = tmp;
// 5.更新容量大小
_capacity = newCapacity;
}
}
3.3 capacity
同上上。size_t capacity() const
{
return _capacity;
}
3.5 clear
clear()
主要是清楚当前对象的数据,我们直接在_str[0]
这个位置上放一2个\0
即可,并且再去修改一下它的_size = 0
即可。不加const
,因为修改了成员变量_size
。
void clear()
{
_str[0] = '\0';
_size = 0;// 修改成员变量_size
}
3.6 empty
这里就是判断是否有数据,有,返回1
;没有,返回0
。
bool empty() const
{
return (_size == 0);
}
测试:
void TestString6()
{
Harper::string s1("hello");
cout << s1.size() << endl;
cout << s1.capacity() << endl;
cout << s1.empty() << endl;
s1.clear();
cout << s1.empty() << endl;
}
运行结果:
3.7 resize
<code>resize主要是对对象中的数据去做一个变化。
首先进行resize
的分类讨论:
若newSize < _size
,我们要选择删除数据;若_size < newSize < _capacity
时,我们要选择不扩容地增加数据;若newSize > _size
,我们要选择进行扩容。 画图:
开始实现代码:
首先先判断<code>newSize和_size
的大小,在内部还要与_capacity
进行比较,newSize > _capacity
时才去执行reserve
扩容。如果newSize
并没有超过容量大小的话,我们需要填充数据:(超过了_size
但是没有超过容量值)
从_str + _size
的位置开始填充;填充个数newSize - _size
个;填充的容量是c
。 若newSize <= _size
,我们需要截取数据,到newSize
为止直接设置一个\0
,再更新一下当前对象_size
的大小。
// 改变大小
void resize(size_t newSize, char c = '\0')
{ -- -->
// 1.当新的_size比旧的_size来得小的话,则进行删除数据
if (newSize > _size)
{
// 只有当新的size比容量还来的大,才去做一个扩容
if (newSize > _capacity)
{
reserve(newSize);
}
// 如果newSize <= _capacity,填充新数据即可
memset(_str + _size, c, newSize - _size);
}
// 如果 newSize <= _size,不考虑扩容和新增数据
_size = newSize;
_str[newSize] = '\0';
}
四、Modifiers修改器
4.1 PushBack
首先插入字符涉及到空间变化,我们就要先考虑扩容。
我们追加一个一个的字符,先考虑扩容逻辑,开始扩容:_size ==_capacity
的时候,说明空间已满,开始扩容操作。使用三目运算符,若容量为0,默认开辟大小为4 的空间;其他情况以2倍形式进行扩容。最后在扩容完成后,就在末尾增加数据,_size
只想那个的是\0
的位置,所以就把走服仿造该位置上,后移_size
,再加上\0
。
void string::PushBack(char ch)// 先实现reserve,帮助这里的扩容
{
if (_size == _capacity)// 容量满了——确定扩容
{
// 扩容:2倍/4空间
reserve(_capacity == 0 ? 4 : _capacity * 2);//扩容,注意_capacity可能是0
}
//_str[_size] = ch;// 插入数据
//++_size;// 这两句可以写成下面:
_str[_size++] = ch;
_str[_size] = '\0';// 记得处理\0!!!!!!!!
}
4.2 append
接下来是
append
的实现!
作用:追加一个字符串。
先计算出长度,按需进行扩容;然后判断改长度加上新增长度是否大于现有空间容量。若大,表明现有空间不够,需要进行扩容;若小,表明现有的空间足够了。接着,使用memcpy()
或者strcpy()
进行数据的拷贝,注意将\0
一起拷贝,拷贝到_str+_size
的位置(注意:拷贝len+1
个,加上\0
)最后_size
修改一下即可。
// 追加一个字符串
void string::append(const char* str)// 字符串
{
// 不能2被扩容了
// 插入的字符串可能与原来字符串相加都比2倍还大——按需扩容
size_t len = strlen(str);// 按需扩容
if (_size + len > _capacity)// 等于,说明空间刚好足够
{
// 扩容的容量大小:大于2倍:需要多少扩容多少;小于2倍按照2倍扩容
reserve(_size + len > 2 * _capacity ? _size + len : 2 * _capacity);
// 不建议
}
// strcat追加可以使用,但是不建议,它会自己找\0,在\0后面追加
strcpy(_str + _size, str);// 复制拷贝;_str + _size是\0的位置
// 更新大小
_size += len;
}
4.3 operator+=(char ch)
末尾追加字符;使用引用返回可以减少拷贝;复用前面的接口PushBack
;+=
改变的是自身,所以返回*this
,传引用返回(减少拷贝)。(返回一个出了作用域不会销毁的对象,可以传引用返回减少拷贝)
string& string::operator+=(char ch)
{
PushBack(ch);// 注意处理\0!!!!
return *this;
}
4.4 operator+=(const char* str)
+ 末尾追加字符串; + 复用`append()`; + 传引用返回。string& string::operator+=(const char* str)
{
append(str);// 直接调用append
return *this;
}
4.5 pos位置插入n个字符(xxxx……n个x)
下面就是
insert
接口的模拟实现了!
首先我们需要做一个准备工作:声明并初始化一个静态的成员变量npos
,无符号整型的最大值。
// 类里面声明
static size_t npos;
// 类外面初始化
size_t string::npos = -1;
然后我们在pos
位置插入n个字符。
// 声明
void insert(size_t pos, size_t n, char ch);
传入参数pos要合法,先对它断言:
assert(pos <= _size);
接着我们开始考虑是否扩容问题:判断要插入的字符串长度+原字符串长度(_size + len > _capacity
),就要调用reserve
接口实现扩容。
size_t len = strlen(str);// 表示str字符串的长度
if (_size + len > _capacity)
{
// 大于2倍,需要开多少就去开多少;小于2倍就按照2倍扩
reserve(_size + len > 2 * _capacity ? _size + len : 2 * _capacity);
//不需要考虑\0 ,因为已经开辟好了
}
// 或者是:
// 考虑扩容
if (_size + n > _capacity)
{
reserve(_size + n);
}
然后先给需要插入的n个字符腾出位置。从_size
(原始数据的末尾)开始,让字符以n个单位从后往前挪动,避免从前往后覆盖原始数据的问题。
// 开始挪动数据:
size_t end = _size + len;// end位置在_size+len
while (end > pos)
{
_str[len] = _str[end - len];
--end;
}
// 或者是:
// 挪动数据
size_t end = _size;
while (end >= pos)
{
_str[end + n] = _str[end];
--end;
}
注意:若pos == 0
,那么插入数据就相当于头插,此时就需要将全部数据往后挪动。但是当end
超出了pos
的范围时,就会减到-1
,无符号整型end就突然从0变成了无符号整型的最大值,这个就是npos
的值了,这样就会造成死循环,程序崩溃。因此我们在循环结束条件里面加上end != npos
。
// 挪动数据
size_t end = _size;
while (end >= pos && end != npos)
{
_str[end + n] = _str[end];
--end;
}
接着我们就在pos位置开始插入这n个字符,最后再更新一下_size
的大小。
// 插入n个字符
for (size_t i = 0; i < len; i++)
{
_str[pos + i] = str[i];
}
_size += len;
总结:
// 在pos位置插入一个字符串(len个字符)
void string::insert(size_t pos, const char* str)
{
// 可以使用memmove
// end在最后一个有效字符串的后一个位置
assert(pos <= _size);
size_t len = strlen(str);// 表示str字符串的长度
if (_size + len > _capacity)
{
// 大于2倍,需要开多少就去开多少;小于2倍就按照2倍扩
reserve(_size + len > 2 * _capacity ? _size + len : 2 * _capacity);
//不需要考虑\0 ,因为已经开辟好了
}
// 开始挪动数据:
size_t end = _size + len;// end位置在_size+len
while (end > pos)
{
_str[len] = _str[end - len];
--end;
}
// 改:?????
for (size_t i = 0; i < len; i++)
{
_str[pos + i] = str[i];
}
_size += len;// ?????
}
4.6 pos位置开始插入一个字符串(abcdefg……)
void insert(size_t pos, const char* s)
插入数据都是需要考虑扩容、挪动数据的问题的。
// pos位置插入一个字符串
for (size_t i = 0; i < len; i++)
{
_str[pos + i] = s[i];
}
// 更新_size
_size += len;
4.7 从pos位置开始插入一个字符
1. 第一种方法:void string::insert(size_t pos, char ch)// ???????????
{
assert(pos <= _size);
// 插入数据都要判断空间是否足够
if (_size==_capacity)
{
reserve(_capacity == 0 ? 4 : _capacity * 2);
}
//第一种方法:
int end = _size;
while (end >= (int)pos)// end>=0,不会<0。因此,size_t改成int
{
// 避免调试很长时中间错按键盘导致调试出错,就在此处加一段if代码
if (end == 0)
{
int i = 0;
// C语言中:当一个操作符两边的操作数类型不一样时,就会进行隐式类型转换(截断等)
// 因此,end = -1,也会进入循环
// 最好的办法,先在循环条件中直接进行强转
// pos有符号,会被提升成无符号!因此pos强转为int:string::insert也是size_t类型的参数
// memmove、memcpy也可以
}
_str[end + 1] = _str[end];
--end;
}
_str[pos] = ch;
++_size;
}
C语言中的一个容易出错的坑:当操作符两边的两个操作数类型不一样时,编译器会进行隐式类型转换或者提升。end减到-1的时候进行整型提升,结果就是+1。一个调试小技巧:在重复操作(F10)去调试时可以设置一个条件断点。
while (end >= (int)pos)
{
// 观察最后一两次的
if (end == 0)// 判断的是end=0时没有停下来的原因,因此这里断点打在end==0的情况
{
int i = 0;
}
_str[end + 1] = _str[end];
--end;
}
第二种方法:不用强转。
void string::insert(size_t pos, char ch)
{
assert(pos <= _size);
if (_size==_capacity)
{
reserve(_capacity == 0 ? 4 : _capacity * 2);
}
// 第二种方法:15:00:00
// end的起始位置变为:末尾\0位置
size_t end = _size + 1;// 说明插入了一个字符(\0的下一个位置)
while (end > pos) //
{
_str[end] = _str[end - 1];// 前一个位置的数据给后一个
--end;
}
_str[pos] = ch;
++_size;
}
4.8 删除pos位置开始的len个有效长度字符
从pos位置开始移位覆盖地删除len
个有效长度的字符。
void erase(size_t pos, int len = npos)
普通情况图解:
特殊情况图解:如果我们要去的长度<code>len很大甚至是最大的npos
,又或者在pos + len
之后的长度超出了当前_size
的大小,此时我们就需要直接对pos
之后的字符去做一个截断操作,让它变成新的_size
。
写法一:
<code>// 删除从pos位置开始的len个有效长度字符
void erase(size_t pos, int len = npos)
{ -- -->
if (len == npos || pos + len > _size)
{
_size = pos;
_str[_size] = '\0';
}
else
{
size_t end = pos + len;
while (end <= _size)
{
_str[pos++] = _str[end++];
}
_size -= len;
}
}
写法二:
// 删除pos位置后面的len个有效字符
// 记得画图
void string::erase(size_t pos, size_t len)
{
assert(pos < _size);// ??????
// 如果len比pos后面的字符个数,说明删除pos后面的所有数据:
// 左闭右开,相减就是个数
if (len >= _size - pos)// _size-pos:pos后面的数据个数
// _size在\0位置
{
_str[pos] = '\0';// 删除数据后新的\0位置
_size = pos; //
}
else //len < _size - pos// ???????
{
for (size_t i = pos + len; i < _size; i++)
{
_str[i - len] = _str[i];// 后面朝着前面挪动
}
_size -= len;
}
}
测试情况:
4.9 erase中的npos参数
//string.h
private:
static const size_t npos = -1;// 可以直接在这里初始化,相当于定义
static const double N = 1.1; // error
注意:static const size_t npos = -1;
静态的变量不能在类里面的声明位置给缺省值,但是这里可以,而且只有整型可以,因此这个权限只给了静态的整型。简建议写成下面:声明定义分离的形式。
// string.h
private:
static const size_t npos;
// string.cpp
const size_t string::npos = -1;
可能是为了类似下面的操作:
static const int N= 10;
int buff[N];
4.10 swap
void swap(string& s)
{
std::swap(_str, s._str);
std::swap(_size, s._size);
std::swap(_capacity, s._capacity);
}
五、字符串操作
5.1 c_str
由于流插入运算符<<
和string类对象并没有对应的重载函数,因此我们,选择重新写一个输出函数。
const char* c_str() const
{
return _str;
}
5.2 从pos位置开始找指定的字符
首先遍历一遍当前对象中的_str
,一边遍历一边匹配字符ch
,找到就返回ch
位置的下标。如果遍历完了还是没有找到就返回npos
(无符号整型的最大值)。
// 在pos位置查找对应的字符,返回字符对应的下标
size_t string::find(char ch, size_t pos) const
{
assert(pos <= _size);
for (size_t i = pos; i < _size; i++)// size_t i = 0?还是=pos?
{
if (_str[i] == ch)
{
return i;
}
}
return npos;//??????????
}
5.3 从pos位置开始找指定的字符串(找子串)
上面是在找单独的一个字符,这里进阶成从字符串中找字符串。
我们可以使用【KMP算法】【暴力搜索】等直接查找,也可以直接使用C语言中的strstr()
(如果找到了就返回子串第一次出现在主串中的指针)若要计算指针举例起始位置有多远,就是用指针 - 指针
。若没找到就返回npos
。
// 在pos位置查找子串
// 扩展:字符串匹配的BM算法、KMP算法(大博哥讲了)
// strstr:
size_t string::find(const char* str, size_t pos)
{
assert(pos < _size);//保证pos的合法性
const char* tmp = strstr(_str + pos, str);
if (tmp)
{
return tmp - _str;// 指针相减即为距离
}
return npos;
}
5.4 从pos位置开始取len个有效字符(取子串)
下面我们开始从字符串中取出子串!
string string::substr(size_t pos, size_t len = npos)
如果要取子串大于剩余的字符串长度,那么能取的有效字符串长度范围为**从pos
位置开始到末尾_size
结束的这段距离,所以所取的子串长度过长,就需要更新子串长度。
assert(pos < _size);// len大于剩余字符长度,更新len
if (len > _size - pos)
{
len = _size - pos;// 更新len
}
接下来开始取子串,从pos位置开始,以循环的方式取n个字符,然后追加到string对象中去,最后将其返回即可。避免返回离开作用域销毁对象,我们使用传值返回,而不能使用传引用返回。
string tmp;
tmp.reserve(len);
for (size_t i = 0; i < len; i++)
{
tmp += _str[pos + i];
}
return tmp;
// 或者是
string tmp;
tmp.reserve(n);
for (size_t i = pos; i < pos + n; i++)
{
tmp += _str[i];
}
return tmp;
总结:
string string::substr(size_t pos, size_t len = npos)
{
assert(pos < _size);// len大于剩余字符长度,更新len
if (len > _size - pos || len == npos)
{
len = _size - pos;// 更新len
}
string tmp;
tmp.reserve(len);
for (size_t i = 0; i < len; i++)
{
tmp += _str[pos + i];
}
return tmp;
}
六、元素遍历访问
6.1 operator+=
string& string::operator+=(char ch)
{
PushBack(ch);// 注意处理\0!!!!
return *this;
}
string& string::operator+=(const char* str)
{
append(str);
return *this;
}
6.2 operator[]
这里需要提供两个版本:普通对象、const对象。
可读可写普通版本:
// 可读可写
char& operator[](size_t pos)
{
assert(pos < _size);// 断言:防止越界
return _str[pos];// 返回pos.位置(普通对象,返回引用)
}
可读不可写const版本:
// 可读不可写(只读)
const char& operator[](size_t pos) const // const对象返回引用别名 给const对象
{
assert(pos < _size);
return _str[pos];
}
定义对象时加一个const
,该对象就具有常性了,在调用operator[]
时调用的是可读不可写
版本。(调试可以发现)
const Harper::string s2("world");
七、非成员函数重载
7.1 比较运算符重载
// string 比较大小:strcmp,按照ASCII码比,不能按照长度比较,长度相等的不同字符串不一定相等
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;
}
bool operator>(const string& s1, const string& 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);
}
7.2 operator<<流插入
```cpp // 流插入 ostream& operator<<(ostream& out, const string& s) { for (size_t i = 0; i < s.size(); i++) { out << s[i]; } return out; } ```7.3 operator>>流提取
istream& operator>>(istream& in, string& s)
{
char ch;
in >> ch;
while (ch != '\n')
{
s += ch;
in >> ch;
}
return in;
}
上一篇: Java 当中使用 “google.zxing ”开源项目 和 “github 的 qrcode-plugin” 开源项目 生成二维码
下一篇: JAVA基础之十-不常用但是又希望能看懂的关键字/保留字
本文标签
声明
本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。