C++--string的使用及其模拟实现

1. 问题引入

C语言中，字符串是以’\0’结尾的若干个字符的集合，为了操作方便，C语言 string.h 头文件提供了一些系列的库函数，但是这些库函数与字符串是分离开的，不符合面向对象的思想，而且底层空间需要用户自己管理，稍不留神可能还会越界访问。

基于上面这些原因，C++标准库提供了 string 类，string 类中提供了各种函数接口，比如类的六个默认成员函数、字符串插入删除、运算符重载等等，可以使用 string 来实例化对象，然后通过 string 的各种接口来完成对该对象的各种操作。

string 类的实现框架大概如下：

namespace std {
	template<class T>
	class string {
	public:
		// string 的各种成员函数
		
	private:
		T* _str;
		size_t _size;
		size_t _capacity;
		//string 的其他成员变量，比如npos
	};
}

**注意：**严格来说 string 其实并不属于 STL，因为 string 出现的时间比 STL 要早，但是由于 string 的各种接口和 STL 中其他容器的接口非常类似，所以可以把 string 也当作 STL 的一种，放在一起学习。

2. VS 和 g++ 下 string 的结构

注意：下述结构是在32位平台下进行验证，32位平台下指针占4个字节。

2.1 VS 下 string 的结构

VS 下 string 总共占28个字节，其内部结构比较复杂，包含一个联合体，联合体用来定义 string 中字符串的存储空间：

• 当字符串长度小于16时，使用内部固定的字符数组来存放；
• 当字符串长度大于等于16时，从堆上开辟空间

补充： 在每次开辟新的空间的时候，均是以之前的1.5倍开辟。

union _Bxty { 
    // storage for small buffer or pointer to larger one
    value_type _Buf[_BUF_SIZE];
    pointer _Ptr;
    char _Alias[_BUF_SIZE]; // to permit aliasing
} _Bx;

这种设计有其自身的好处，大多数情况下字符串的长度都小于16，这样当 string 对象创建好之后，内部已经有了16个字符数组的固定空间，就不需要再通过向堆申请空间来存储字符了，提升了效率。

同时，string 内部还有一个 size_t 字段用来保存字符串长度 (size)，一个 size_t 字段保存从堆上开辟空间总的容量 (capacity)，最后还有一个指针做一些其他事情。

总的来说，VS 下 string 结构是一种以空间换取时间的做法。

2.2 g++ 下 string 的结构

g++ 中，string 是通过写时拷贝实现的，string 对象总共占4个字节，内部只包含了一个指针，该指针将来指向一块堆空间，内部包含了如下字段：

• 空间总大小 capacity；
• 字符串有效长度 size；
• 引用计数 refcount ；(拷贝构造时默认使用浅拷贝来提高效率 + 使用引用计数来保证同一块堆空间不被析构多次)
• 指向堆空间的指针，用来存储字符串。

补充： 在每次开辟新的空间的时候，均是以之前的2倍开辟。

3. 标准库中的string类

3. 1 了解string类

string类的文档介绍

在使用功能 string 类时，必须包含 #include <string> 包含头文件，以及 using namespace std。

string 类模版：

string 其实是 basic_string 类模板使用字符类型 char 实例化得到的一个类：

补充：

那么为什么要将 string 设计成模版呢？

因为编码的不同，存储一个字符所需要的空间也就不同，空间不同变量的类型大小就需要改变成 char16_t 或者 char32_t ，所以将 string 类设计为一个模版从而适配不同编码方式产生的不同大小的字符。

编码的介绍：

ASCII

ASCII 全称为美国信息交换标准代码，这是接触到的第一种编码，由于英语所有的英文字母 (包括大小写) 加上各种标点符号以及特殊字符一共只有一百多种，所以我们使用一个字节即可表示所有字符；但是根据 ASCII 编码设计出的计算机不能表示其他国家的语言，比如中文、日文、韩文等等。

Unicode

Unicode 就是中国的统一码，也叫万国码；它是为了解决传统的字符编码方案的局限而产生的，它为每种语言中的每个字符设定了统一并且唯一的二进制编码，以满足跨语言、跨平台进行文本转换、处理的要求。Unicode 主要包括 utf-8，utf-16 与 utf-32，其中的8、16与32分别代表了字符的最小空间为1、2以及4字节。

由于 utf-8 支持 ASCII，且字符最小单位为一字节，节省了空间，所以现在使用率最高的编码方式就是它。

GBK

GBK 即 “国标”，是我国专门为汉字设计的一套编码，其中一个字符最小占用空间为两个字节。

编码方式对 basic_string 的影响如下：

• char – 采用单字节编码
• char16_t – 采用双字节编码
• char32_t – 采用四字节编码

所以，平时使用的 string 本质上是 basic_string，不用自己显式实例化是因为 string 内部进行了 typedef：

typedef basic_string<char, char_traits, allocator> string

3.2 auto和范围for

3.2.1 auto关键字

auto是C++11中补充的一个小语法，可以方便平时代码的编写。

int main()
{
	int i = 0;
	int j = i;
	//自动推导类型
	auto z = i;		//int
	auto x = 1.1;	//double
	auto p = &i;	//int*

	//使用场景
	string s1("abcd");
	//string::iterator it = s1.begin();
	auto it = s1.begin();
    
    std::map<std::string, std::string> dict;
    //std::map<std::string, std::string>::itrerator dit = dict.begin();
    auto dit = dict.begin();//大大简化代码
}

作用：auto 可以根据右值自动推导类型，在简化代码，替换写起来长类型的时候很好用。

注意：

• 无法推导出引用

  

3.2.2 范围for

对于一个有范围的集合而言，由程序员来说明循环的范围是多余的，有时候还会容易犯错误。因此C++11中引入了基于范围的for循环，在遍历容器时可以方便操作。

**格式：**for循环后的括号由冒号“ ：”分为两部分：第一部分是范围 内用于迭代的变量，第二部分则表示被迭代的范围

**作用：**智能遍历容器，自动取容器的数据赋值给左边的变量，自动++，自动判断结束。适用于容器和数组。

**补充：**范围 for 还可以将括号中的变量类型用 auto 代替。

注意：

• 使用引用做参数

  • 利用范围for修改容器数据

    

    因为上面已经介绍了，范围 for 遍历的本质是取出数据给 for 中定义的形参，只可以对形参进行操作，但是因为形参是实参的拷贝，对形参的操作不会影响到实参，所以这里将 ch 的类型改为引用，这样对 ch 的操作本本质就是对 s1的操作。

  • 容器内数据类型过大

    因为涉及拷贝，如果容器内数据的数据类型过大可能会占用大量空间，这里使用引用传参可以节省空间。

    但是如果使用了引用传参但是不想对容器内的数据进行修改，同样可以加上 const 修饰即可。

• 范围for的底层结构

  范围for的底层为迭代器，这个从汇编层可以看到。这也是为什么范围for只能用来遍历容器中的数据，因为只有容器才支持迭代器。

  同时编译器也经过了特殊处理，使得内置类型数组也支持使用范围 for。这样就不用像以前一样使用 for 循环遍历数组了。

  

3.3 string类的常用接口

3.3.1 构造函数

string 提供了很多构造函数，只需要掌握其中最常用的几个就可以，其余的如果有需要再查询文档：

(constructor)函数名称	功能说明
string()	构造空的string类对象，即空字符串
string(const char s)*	用C-string来构造string类对象
string(size_t n, char c)	string类对象中包含n个字符c
string(const string& s)	拷贝构造函数

3.3.2 Element Access

string 提供了一些接口来获取字符串中的单个字符：

3.3.2.1 operator []

运算符重载的一种，可以通过 opetator[] 来获取与修改字符串中具体下标的字符，从而实现字符串的遍历：

使用了和访问数组下标一样的方式，修改了字符串中的数值。

补充：operator [] 定义两种运算符重载的原因

一般来说一个成员函数要么是 const 修饰的，要么是非 const 修饰的，但是这里的重载函数是同时写的，这是因为想让普通对象调用普通的重载函数**（用于修改字符串），const 修饰的变量就调用 const 修饰的重载函数（用于访问字符串）**。

因为这里 operator [] 的重载函数是需要对不同的类型的对象调用不同的接口，需要进行区分，所以才需要对照这两种类型都进行重载。一切从需求出发。

所以这里的 operator [] 接口是既可以读的接口，又是可以写的接口。

补充：operator [] 的普适性

operator [] 是一个很有效的访问底层是数组类型的容器，但是对于非连续存储的容器，其重载 operator [] 是一个比较复杂的过程，所以于非连续存储的容器主要使用迭代器进行内容的访问。

3.3.2.2 at

at 和 operator [] 的功能上是一致的，都可以通过下标的方式访问字符数组中的数据。

但是区别是在访问越界的时候的报错方式的不同：

• operator 通过断言报错，强制终止程序执行。

  

• at 通过抛异常进行报错，需要对异常进行捕获。
  

3.3.3.3 front 和 back

这两个函数的作用分别是返回字符串的第一个字符和最后一个字符（不包含\0）。但是如果需要访问第一个和最后一个字符完全可以依靠下标来完成，所以这两个函数的使用频率很低。

注意：

这两个函数的返回值都是返回数据的引用，所以是可以进行修改的。

3.3.3 Iterators

迭代器是容器通用的遍历方式

Iterators 是C++中的迭代器，可以把它当成指针来理解，当然，并不是所有迭代器的底层都是用指针实现的：

typedef char* iterator;  //简单理解string中的迭代器

函数名称	函数功能
begin()	返回一个指向字符串中第一个字符的迭代器
end()	返回一个指向字符串最后一个有效字符下一个位置（‘0’）的迭代器
rbegin()	反向迭代器，返回一个指向字符串最后一个有效字符下一个位置（‘0’）的迭代器
rend()	反向迭代器，返回一个指向字符串中第一个字符的迭代器

3.3.3.1 普通迭代器和反向迭代器

普通迭代器：

反向迭代器：

有了迭代器之后，就可以使用迭代器来遍历与修改字符串了：

如上代码解释：

分别使用了迭代器 begin 和 end 从正向指向字符串的第一个字符和最后一个有效字符的下一位（’\0‘）

分别使用了反向迭代器 rbegin 和 rend 从反向指向字符串的第一个字符和最后一个有效字符的下一位（’\0‘）

这样就可以通过迭代器，向使用指针一样前后遍历字符串中的数据。

注意：使用迭代器遍历容器

这里在使用迭代器遍历容器中的数据的时候其实还是需要考虑容器底层的实现结构，比如这里的 string 底层本质是数组物理空间是连续的，所以前面的地址小后面的地址大。但是如果是list 之类的其底层本质的物理空间是不连续，对于其地址前后之间没有大小关系。所以在遍历容器数据的时候不推荐使用大小比较的方式作为循环的终止条件，更推荐使用 != 的方式作为终止条件。

补充：迭代器的普适性

迭代器是访问一个容器内部数据的通用方式，这里的 string 或者是 vectro 可能显得不太方便，但是对于后面的 list 之类非连续存储的容器访问其中数据就很有效，所以说迭代器是容器通用的遍历方式。所以所有容器都会定义迭代器，并且他们的使用方式也十分相似。

注意：迭代器区间均是左闭右开。

3.3.3.2 const迭代器

const对象没有办法使用普通迭代器，所以为了使 const 对象也能调用，每个迭代器函数都设计了 const 版本。

针对 const 对象调用 const 版本迭代器：

注意：

• const版本迭代器只能访问容器数据，不可以修改容器中的数据。
• 同样这里的 string::const_iterator 类型也可以简化为 auto 。

3.3.4 Capacity

string 中提供了一些对容量进行操作的函数：

函数名称	功能说明
size（重点）	返回字符串有效字符长度
length	返回字符串有效字符长度
capacity	返回空间总大小
empty（重点）	检测字符串释放为空串，是返回 true，否则返回 false
clear（重点）	清空有效字符
reserve（重点）	为字符串预留空间
resize（重点）	将有效字符的个数改成 n 个，多出的空间用字符 c 填充

3.3.4.1 用于返回 string 中信息的函数

解释：

• size 和 length

  size 和 length 的功能和使用方法一样，因为 string 的实现在 STL 之前，所以 length 是先在 string 中表示获取字符串中字符个数，但是后来为了兼容 STL 其他容器所以又设计了 size 表示获取字符串中字符个数，所以在后续开发中更推荐使用 size 。

  **注意：**这里的 size 和 length 在获取字符串中字符个数的时候，不会计算 \0 。

• max_size

  这里函数基本不使用，因为获取到的数据大小会根据当时编译的机器的机器架构有关。

• capacity

  由于 string 的底层实现在前文进行了基本介绍，size 用于显示字符数组中的有效数据个数，capacity 用于显示字符串数组的实际空间大小。

• clear

  clear 函数用来清空字符串，即将 size 改为0，至于是否会改变 capacity，标准也未规定，所以具体实现还是根据编译器而定。

• empty

  empty 函数用于判断字符串中是否还有有效数据，并返回一个 Bool 类型的数据。

3.3.4.2 用于管理 string 中空间的函数

3.3.4.2.1 reserve

reserve 可以在提前知道字符串数组空间大小的时候提前开辟空间，避免扩容提升效率，用来扩容与预留空间，相当于C语言中的 realloc 函数，它分两种情况：

n 大于原字符串的 capacity，此时 reserve 函数会将 capacity 扩容到 n；
n 小于等于原字符串的 capacity，标准未规定是否要缩容 (VS下不缩容)；

注意：

• reserve 函数不会改变原字符串的 size 以及数据。

• resevre 函数在不同编译器下扩容的空间可能不同，比如在 VS 编译器下申请的空间一般会大于要求开辟的空间，但是在 g++ 编译器下申请的空间一般等于要求开辟的空间。

  这也说明了不同的平台底层的实现是存在差异的，但是最终使用的功能和效果一定是符合要求的。

3.3.4.2.2 resize

resize 函数用来调整字符串大小，它一共分为三种情况：

n 小于原字符串的 size，此时 resize 函数会将原字符串的 size 改为 n，但不会改变 capacity。

n 大于原字符串的 size，但小于其 capacity，此时 resize 函数会将 size 后面的空间全部设置为给的参数字符或者\0。

n 大于原字符串的 capacity，此时 resize 函数会将原字符串扩容，然后将size 后面的空间全部设置为给参数字符或者 \0。

3.3.5 Modify

string 提供了一些列用来修改字符串内容的函数：

在这里插入图片描述

函数名称	功能说明
push_back	在字符串后尾插字符c
append	在字符串后追加一个字符串
operator+=（重点）	在字符串后追加字符串str

不常用的函数的使用示例：

3.3.5.1 operator +=

operator+= 是运算符重载的一种，用于向字符串尾插数据，支持尾插一个字符串、尾插一个字符数组以及尾插一个字符。

其是在插入字符的场景中使用十分广泛的函数。

3.3.5.2 insert

insert 函数用于向在字符串的 pos 处头插入数据：

注意：

• 头插的可以是字符，也可以是字符串。
• 不建议在代码中过多的使用头插，因为其占用的时间复杂度较高，会降低代码的执行效率。

3.3.5.3 erase

erase 用来从 pos 位置开始向后删除 len 个字符：

注意：

len 的缺省值是 npos，虽然 npos 的值为-1，但是 npos 是无符号数，所以 npos 其实是无符号整形的最大值。所以，如果不知道 len，那么 erase 函数会一直往后删除，直到遇到 ‘\0’。

注意：

• 此函数也同样不建议过多使用，如果频繁的删除字符串中间的字符，就需要设计底层数据的挪动，如果频繁调用就会影响代码的效率。

3.3.5.4 replace

replace 是用于将字符串中的某一段替换成别的字符：

注意：

• 此函数仍不建议过多使用，因为一段替换的数目存在差异，比如将新的3个字符的字符串替换掉原来的字符串中的2个字符，这样的差异会导致的底层的数据需要挪动。所以如果在这种情况下过多使用则会使得效率变低。

  所以只有在平替（替换数目与原字符串需要操作的字符数目一致）的情况下比较推荐使用。

补充：将字符串中的空格都替换成 %%

//法一（时间复杂度过高）
int main()
{
    string s1("12 34 5 ab cd");
    cout << s1 <<endl;
    
    size_t i = s1.find(' ');
    while(i != string::npos)
    {
        s1.replace(i, 1, "%%");
        i = s1.find(' ', i+2);
    }
    cout << s1 << endl;
}

//法二（空间换时间）
int main()
{
    string s1("12 34 5 ab cd");
    cout << s1 <<endl;
    
    string s2;
	for(auto ch ： s1)	//遍历s1
    {
        if(ch != ' ');
        	s2 += ch;	//不是空格的直接挪到s2中
       	else
            s2 += "%%";	//是空格则替换
    }
    cout << s1 << endl;
    s1.swap(s2);
}

3.3.6 String Operations

string 提供了系列对 string 进行操作的函数：string 提供了系列对 string 进行操作的函数：

3.3.6.1 c_str

在某些场景中只支持对C形式的字符串（类型为 const char*），即字符数组进行操作，比如网络传输、fopen，而不支持对C++中的 string 对象进行操作，所以 string 提供了c_str，用于返回C形式的字符串：

3.3.6.2 find

find 用于返回 一个字符或一个字符数组或一个 string 对象 在 string 中首次出现的位置，如果找不到就返回 npos：

3.3.6.3 rfind

find 函数是默认从起始位置开始从前往后找，而 rfind 函数是默认从倒数第二个位置 ( \0 的前一个位置) 从后往前找：

3.3.6.4 find_first_of \ find_last_of \ find_first_not_of \ find_last_not_of

• find_first_of 函数用于返回在 string 中寻找第一个与 字符/字符数组/string 中任意一个字符匹配的元素的位置。
• find_last_of 函数用于返回在 string 中寻找最后一个与 字符/字符数组/string 中任意一个字符匹配的元素的位置。
• find_first_not_of 函数用于返回在 string 中寻找第一个与 字符/字符数组/string 中任意一个字符不匹配的元素的位置。
• find_last_not_of 函数用于返回在 string 中寻找最后一个与 字符/字符数组/string 中任意一个字符不匹配的元素的位置。

3.3.6.5 substr

stustr 函数可以将 string 中从 pos 位置开始往后的 n 个字符构造成一个新的 string 对象并返回：

3.3.7 Non-member function overloads

string 中还提供了一些非成员函数的重载函数：

3.3.7.1 getline

C++ 中的 cin 和 C语言中的 scanf 函数都是以空格、换行、Tab 作为不同数据之间的分割标志的，即当它们遇到这些符号时就会停止读取：

C语言提供了 gets 函数来读取一行字符，C++ 则是提供了 getline 函数来读取一行字符，并且还可以自己指定结束标志符：

4. 有关 string 类的面试题

4.1 仅仅反转字母

题目链接：917. 仅仅反转字母 - 力扣（LeetCode）

题目描述：

给你一个字符串 s ，根据下述规则反转字符串：

• 所有非英文字母保留在原有位置。
• 所有英文字母（小写或大写）位置反转。

返回反转后的 s 。

class Solution
{
public:
        //判断是不是字符
    bool IsLetter(char ch)
    {
        if(ch >= 'a' && ch <= 'z')
            return true;
        if(ch >= 'A' && ch <= 'Z')
            return true;

        return false;
    }

    //进行翻转判断
    string reverseOnlyLetters(string s)
    {
        //判断是不是空字符串
        if(s.empty())
            return s;

        //双指针法
        size_t begin = 0, end = s.size() - 1;
        while(begin < end)
        {
            //先从前面循环找直到找到第一个字符
            while(begin < end && !IsLetter(s[begin]))
                ++begin;
            while(begin < end && !IsLetter(s[end]))
                --end;

            swap(s[begin], s[end]);
            ++begin;
            --end;
        }
        return s;
    }
};

思路总结：

这种原地交换数据的题目还是优先考虑双指针法，使用 operator [] 和下标的方式遍历字符串数组中的数据，再将封装好的检测是否是字符的函数用于判断，最后将确定是字符的前后两个指针所指向的数据利用C++中封装好的函数 swap 进行交换再继续遍历即可，直到最后 begin 大于 end 遍历结束。

4.2 大数相加

题目链接：415. 字符串相加 - 力扣（LeetCode）

题目描述：

给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。

你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。

class Solution 
{
public:
    string addStrings(string num1, string num2) 
    {
        //设定string对象作为返回值，返回最总结果
        string str;

        //预留空间，减少内存开辟，提高效率
        str.reserve(max(num1.size(), num2.size()) + 1); //考虑进位情况+1

        //分别从后面设定指针遍历字符串
        int end1 = num1.size() - 1, end2 = num2.size() - 1;
        //进位变量
        int next = 0;
        //循环运算，一位一位处理
        while(end1 >= 0 || end2 >= 0)
        {
            //取出两数组中的对应位的数据，取出后前移遍历
            int x1 = end1 >= 0 ? num1[end1--] - '0' : 0;
            int x2 = end2 >= 0 ? num2[end2--] - '0' : 0;

            //对两位数据相加，并调整ref，next
            int ref = x1 + x2 + next;   
            next = ref/10;  //进位变量            
            ref = ref%10;   //相加后的个位数字

            //每一位的计算结构尾插进一个string对象中
            str += ('0' + ref);
        }      

        //处理循环结束还存在进位的情况
        if(next == 1)
        {
            str += '1';
        }

        //将最终结果逆置
        reverse(str.begin(), str.end());

        return str;
    }
};

思路详解：

• 设定 end1，end2 两指针分别指向 num1，num2 尾部，并利用 operator [] 取出尾部数据相加，模拟人工加法。
• 计算 next = ref/10;，代表当前位相加是否产生进位，并在下一次前移的运算中加上进位一起运算 int ref = x1 + x2 + next;。
• 随着不断前移 num1，num2 中出现一个已经走过数字首部则利用三目运算符 int x1 = end1 >= 0 ? num1[end1--] - '0' : 0;，将取出的数据设定为 0 ，使得不影响后续计算。
• 最终因为 operator += 实现的是尾插操作，又因为模拟人工加法是从低位开始，所以会导致字符串逆置，需要调用 reverse 函数将字符串逆置回去。
• 最后因为没有给 str 分配空间，所以对其插入数据可能需要多次扩容，利用 reserve 函数配合 max 函数实现对其提前扩容 str.reserve(max(num1.size(), num2.size()) + 1); ，提高效率。

应用场景：

按照题目的要求很容易想到，可以将字符串转化成整型，再直接调用运算符进行计算之后再转回字符类型。这种方法虽然思路简单但是却存在大问题。

因为整型最大为 long long 也就是8字节大小，也就是最大能存储的数是 $2^{64}$ ，也就是一个20位的数据，所以在有时候需要去用科学计数法表示的极大的数据（类似于一些100位以上的数据）的时候，就会出现溢出，就没办法存储下这么大的数据了。所以为了解决这个问题就提供了一个大数运算的库，这个库的特点就是将整数存储到字符串中去，因为只要内存够字符串是一定可以存下去的。

但是有了存储的方法，至于其中各个数据的运算逻辑却是需要程序员自己进行实现。

4.3 字符串中的唯一字符

题目链接：387. 字符串中的第一个唯一字符 - 力扣（LeetCode）

题目描述：

给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1 。

class Solution 
{
public:
    int firstUniqChar(string s) 
    {
        //利用映射统计字符串中每个字符出现的次数
        int count[26] = {0};
        //范围for遍历计次
        for(auto ch : s)
        {
            count[ch - 'a']++;
        }

        //根据映射按字符串从前向后顺序找到只出现一次的字符，返回下标
        //这里需要返回下标，所以使用for循环遍历
        for(int i = 0; i < s.size(); i++)
        {
            if(count[s[i] - 'a'] == 1)
            {
                return i;
            }
        }
        return -1;
    }
};

思路介绍：

这使用了两次遍历通过映射的思想即可完成这道题。

• 第一次遍历，通过映射统计字符串中每个字符出现的次数。
• 第二次遍历，将数组中的次数映射会字符串，再从前往后遍历找到只出现一次的字符，返回下表。

注意：针对不同的场景需要使用不同的遍历方法，如第一次遍历没有什么特殊要求仅仅是完成遍历操作即推荐使用范围for，更改方便快捷。第二次遍历因为需要返回下标，所以使用for循环用 i 记录下标。

4.4 字符串最后一个单词的长度

题目链接：字符串最后一个单词的长度_牛客题霸_牛客网

题目描述：

对于给定的若干个单词组成的句子，每个单词均由大小写字母混合构成，单词间使用单个空格分隔。输出最后一个单词的长度。

#include<iostream>
#include <string>
using namespace std;

int main() 
{
    string str;
    getline(cin, str);

    //确定最后一个空格下标
    int pos = str.rfind(' ');
    //确定最后一个有效数据下标
    int end = str.size() - 1;
    //确定最后一个单词长度(一侧开一侧闭即可)
    int num = end - pos;

    cout << num << endl;

    return 0;
}

4.5 回文字符串

题目链接：125. 验证回文串 - 力扣（LeetCode）

题目描述：

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。

字母和数字都属于字母数字字符。

给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。

class Solution 
{
public:
    //确认该字符是字符或者数字
    bool IsLetterOrNumber(char ch)
    {
        return (ch >= '0' && ch <= '9')
        ||(ch >= 'a' && ch <= 'z')
        ||(ch >= 'A' && ch <= 'Z');
    }

    bool isPalindrome(string s) 
    {
        for(auto& ch : s)
        {
            //将所有大写字母转化为小写字母，便于比较
            if(ch >= 'A' && ch <= 'Z')
            {
                ch += 32;
            }
        }
		
        //双指针法
        int begin = 0, end = s.size() - 1;
        //遍历字符串找字符
        while(begin < end)
        {
            //前后未都找到字符
            while(begin < end && !IsLetterOrNumber(s[begin]))
            {
                begin++;    //继续后移寻找字符
            }
            while(begin < end && !IsLetterOrNumber(s[end]))
            {
                end--;  //继续前移寻找字符
            }

            //已经找到前后对应位置的字符，开始比较
            if(s[begin] != s[end])
            {
                return false;
            }
            else
            {
                ++begin;
                --end;      //继续遍历
            }
        }
        //遍历完成，是回文字符串 
        return true;            
    }
};

思路介绍：

• 根据回文字符串的要求，需要利用双指针一个从前一个从后遍历整个数组，所以还是采用双指针法。
• 其次为了便于前后两个字符的比较，首先需要过滤出有效字符（除空格、！、？等），还需要对字母统一大小写。
• 最后则是利用双指针利用封装好的检测是不是有效字符的函数分别找到前后对应的字符，再通过检查两字符ASCII 码值是不是一样确定是不是同一个字符，最后遍历整个字符串，确定是不是回文字符串。

5. string类的模拟实现

**注意：**下面对于 string 的模拟实现分别通过 string.h 、string.cpp 、test.cpp 这三个文件完成，并且为了在测试过程中感受和标准库中的 string 的差异，将模拟实现的 string 放在自己的命名空间中便于在 test. cpp 文件中调用测试。

5.1 string 的基本结构

前文已经提到 string 本质和顺序表一样，所以具有和顺序表相同的内部结构。

//string.h
namespace tcq
{
    class string
    {
    public:
        
    private:
        char* _str = nullptr;
        size_t _size = 0;
        size_t _capcity = 0;
    };
}

5.2 string 的构造和析构函数

5.2.1 构造函数

5.2.1.1 无参构造函数

//string.cpp
//传统写法
string::string()
	:_str(new char[1]{ '\0' })
	, _size(0)
	, _capacity(0)
{}

注意：

• 这里的 _str 初始化的时候不可以初始化为空，而是需要先加一个 \0 进去，并且 capacity 在计算容量大小的时候不会计算 \0 。
• 而且使用 new char [] 开辟空空间是为了和下面析构函数中的 delete [] 相匹配。

5.2.1.2 含参构造函数

//string.cpp
string::string(const char* str)
	:_size(strlen(str))
{
	_capacity = _size;
	_str = new char[_size + 1];

	strcpy(_str, str);
}

注意：

• 这里没有完全按照初始化列表的方式进行成员函数的初始化是为什么？

  strlen 是在运行时计算的（ sizeof 是在编译时计算），如果和无参构造函数一样的格式写初始化列表则会按照上面 string 基本结构中的成员变量的顺序先初始化 _str 但是此时 strlen 还没有计算会返回一个随机值，此时为 _str 开辟的空间就是一块随机大小的空间。

5.2.1.3 无参构造函数和带参构造函数的合并

可以用一个全缺省的构造函数合并无参构造函数和带参构造函数。

//string.cpp
string::string(const char* str = "")
	:_size(strlen(str))
{
	_capacity = _size;
	_str = new char[_size + 1];

	strcpy(_str, str);
}

注意：

• 这里的缺省参数可以直接不写，就相当于给了一个 \0 。因为C语言规定常量字符串的结尾默认有一个 \0 。

• 注意缺省参数声明和定义要分离，这里是在源文件中写的，并没有在头文件中声明。如果工程需要要求定义声明分离则注意，缺省参数只能在头文件中的声明可以给，在源文件中的定义不可以给。

  //string.cpp
  string::string(const char* str)			//定义
  	:_size(strlen(str))
  {
  	_capacity = _size;
  	_str = new char[_size + 1];
  
  	strcpy(_str, str);
  }
  
  //string.h
  string::string(const char* str = "");	//声明
  

5.2.2 析构函数

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

注意：

• 这里释放空间需要使用 delete [] ，因为此时 _str 里面可能是字符串需要释放连续的空间。

5.2.3 拷贝构造函数

//string.cpp
//s2(s1)
//传统写法
string::string(const string& s)
{
	_str = new char[s._capacity + 1];
	strcpy(_str, s._str);
	_size = s._size;
	_capacity = s._capacity;
}


//现代写法
string::string(const string& s)
{
	string tmp(s._str);
	swap(tmp);
}

注意：

• 拷贝构造函数的底层原理

  因为 string 底层是对_str 所指向的数组进行操作，所以在涉及一些拷贝的情况就不可以直接调用编译器默认的拷贝构造，因为其是深拷贝，构造出来的新的 string 底层指向的空间是同一块空间，所以需要自行实现深拷贝的拷贝构造函数。

• 拷贝构造函数的现代写法

  现代写法就不需要自己手动实现这些功能，直接调用构造函数构造出一个一模一样的字符串，再利用 swap 交换一下即可。

  但是需要注意，因为 tmp 为局部变量会在出作用域的时候调用析构函数销毁，所以需要提前将 tmp._str 赋值为 nullptr，然而在 swap 交换之后 tmp 中的 _str 正是 s2._str ，刚好 s2 需要进行拷贝构造前会先调用拷贝构造的初始化列表初始化 s2 ，但是这里没有写初始化列表，所以会按照成员变量给的缺省值进行初始化，就会将 s2.str = nullptr ，使得为空，满足交换后的要求。

  

5.3 string 的遍历

5.3.1 operator [] 配合下标遍历

//string.h
size_t size() const
{
	return _size;
}

char& operator[](size_t i)
{
	assert(i < _size);
	return _str[i];
}

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

注意：

• 这里的 operator [] 需要写两种版本一种用于处理普通参数，一种用于处理被 const 修饰的参数。
• 同时因为这里的几个重载函数都比较短，可以直接放在类里面让其变成内联函数，后续调用的时候可以提升效率。

5.3.2 普通迭代器遍历

//string.h
//typedef char* iterator;
using iterator = char*;
using iterator = const char*;

iterator begin()
{
	return _str;
}

iterator end()
{
	return _str + _size;
}

const_iterator begin() const
{
	return _str;
}

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

注意:

• 同样这里需要使用写两种函数用于接收不同参数（普通参数和被 const 修饰的参数）。
• 同样因为这里的迭代器函数内容较少，也是写在类中使其成为内联函数，提升后续调用的效率。
• 同时因为反向迭代器涉及适配器相关知识点，在后面进行讲解。

5.4 string 的插入和删除

5.4.1 reserve

//string.cpp
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;
	}
}

因为后续的插入都涉及会空间容量的处理，所以这里需要先模拟实现 resrver 。

注意：

• 这里的 reserve 在结束的时候会自动更改 capacity 中的值。

5.4.2 push_back

//string.cpp
void string::push_back(char ch)
{
	if (_size == _capacity)
	{
		reserve(_capacity == 0 ? 4 : _capacity * 2);
	}

	_str[_size] = ch;
	_size++;
}

注意：

• 因为无法判断扩容的时候字符串内部是否已经存在空间，所以不能直接对 capacity*2 处理，所以使用三目操作符位完善代码功能，这个思想和顺序表部分的扩容思想是一致的。
• 因为 push_back 用于将一个字符尾插到字符串后面，所以参数类型为 char。

5.4.3 append

//string.cpp
void string::append(const char* str)
{
	size_t len = strlen(str);
	if (_size + len > _capacity)
	{
		size_t newCapacity = 2 * _capacity;
		// 扩2倍不够，则需要多少扩多少
		if (newCapacity < _size + len)
			newCapacity = _size + len;

		reserve(newCapacity);
	}

	strcpy(_str + _size, str);
	_size += len;
}

注意：

• 因为在插入字符串的时候可能待插入的字符串，会大于此时 capacity*2 的情况，所以针对这种情况利用了 if 判断语句进行分别处理，如果扩2倍不够，则需要多少扩多少，再将新得到的合适的 newcapacity 传给 reserve 进行扩容。
• 因为 append 用于插入一段字符串到字符串后面，所以参数类型为 const char* 。为了保护字符字面值所以用 const 修饰。

5.4.4 operator +=

//string.cpp
//插入一个字符
string& string::operator+=(char ch)
{
	push_back(ch);

	return *this;
}

//插入一个字符串
string& string::operator+=(const char* str)
{
	append(str);

	return *this;
}

注意：

• 因为上面已经实现了 push_back 和 append 用于尾插字符和字符串，所以可以直接调用完成 operator += 重载函数的功能。

5.4.5 insert

//string.cpp
//插入一个字符
void string::insert(size_t pos, char ch)
{
	assert(pos <= _size);
    
    //扩容
	if (_size == _capacity)
	{
		reserve(_capacity == 0 ? 4 : _capacity * 2);
	}
    
    //后移数据
	size_t end = _size + 1;
	while (end > pos)
	{
		_str[end] = _str[end - 1];	//end前一个位置挪到end
		--end;
	}
    
    //插入数据
	_str[pos] = ch;
	_size++;
}

//插入一个字符串
void string::insert(size_t pos, const char* str)
{
	assert(pos <= _size);
	
    //扩容
	size_t len = strlen(str);
	if (_size + len > _capacity)
	{
		size_t newCapacity = 2 * _capacity;
		// 扩2倍不够，则需要多少扩多少
		if (newCapacity < _size + len)
			newCapacity = _size + len;

		reserve(newCapacity);
	}

    //后移数据
	size_t end = _size + len;
	while (end > pos + len - 1)
	{
		_str[end] = _str[end - len];	end前len个位置挪到end
		--end;
	}
    
    //插入数据
	for (size_t i = 0; i < len; i++)
	{
		_str[pos + i] = str[i];
	}

	_size += len;
}

注意：

• 在挪动数据时的注意事项：

  因为size_t 是一个无符号整数类型，当其从 0 再 – 就会越界，越界之后就是变成一个极大值（32位系统上是 2^32 - 1、64位系统上是 2^64 - 1），程序就会崩溃。需要注意！

5.4.6 erase

//string.h
namespace tcq
{
   class string
   {
   public:
   	//...
      	void erase(size_t pos, size_t len = npos);
       
       static const size_t nops;	//声明
       
   private：
       //...
   }; 
}

//string.cpp
namespace tcq
{
   const size_t string::npos = -1;	//定义
   
   void string::erase(size_t pos, size_t len)
   {
   	assert(pos < _size);

       //删大于或者等于_size - pos个字符，直接全删
   	if (len >= _size - pos)
   	{
   		_str[pos] = '\0';
   		_size = pos;
   	}
       //只删除一部分，需要挪动数据
   	else
   	{
   		// 从后往前挪，覆盖掉前面的数据即可
   		size_t end = pos + len;
   		while (end <= _size)
   		{
   			_str[end - len] = _str[end];
   			++end;
   		}
   		_size -= len;
   	}
   }
}

注意：

• 有关nops

  因为 erase 中的有一个缺省参数给的是 nops ，并且是一个静态的成员变量，静态成员变量在类里面声明，类外面定义。但是也并不能在头文件中的类的外部进行定义，因为 string.c 和 test.c 文件中都有 #include”string.h” 会在编译链接中展开从而导致一个工程中定义了两份 nops 而产生链接冲突，所以推荐放在 string.h 声明， string.c 定义。

  同时因为 nops 是 const size_t 类型的，const 类型变量在定义的时候必须初始化，

  并且，nops 十分特殊，作为静态成员变量可以在声明的时候给缺省值进行初始化，这个是 C++ 的特例。但是并不推荐这种写法，还是建议使用声明和定义分离的方式。

  //string.h
  namespace tcq
  {
      class string
      {
      public:
      	//...
         	void erase(size_t pos, size_t len = npos);
          
          static const size_t nops = -1;	//声明+定义（特殊处理）
          
      private：
          //...
      }; 
  }
  

5.5 string 的查找提取和清空

5.5.1 find

//string.cpp
//查找一个字符
size_t string::find(char ch, size_t pos)
{
	assert(pos < _size);

	for (size_t i = pos; i < _size; i++)
	{
		if (ch == _str[i])
			return i;
	}

	return npos;
}

//查找一个字符串
size_t string::find(const char* str, size_t pos)
{
	assert(pos < _size);

	const char* ptr = strstr(_str + pos, str);
	if (ptr == nullptr)
	{
		return npos;
	}
	else
	{
		return ptr - _str;	//地址转下标
	}
}

注意：

• 因为查找时可能会查找字符或者是字符串，所以对于 find 同样需要写两版。
• 在查找字符串的时候，其底层使用的是C语言库中的 strstr 函数，其主要是通过暴力匹配找到第二个参数字符串中找到第一个参数字符串，并返回首元素地址。

5.5.2 substr

//string.cpp
string string::substr(size_t pos, size_t len)
{
	assert(pos < _size);

	// 大于后面剩余串的长度，则直接取到结尾
	if (len > (_size - pos))
	{
		len = _size - pos;
	}

    //创建并初始化空间存放子串
	bit::string sub;
	sub.reserve(len);
	for (size_t i = 0; i < len; i++)
	{
		sub += _str[pos + i];
	}
 
	return sub;
}

注意：

• 这里需要对要求取出的长度 len 做出判断，如果超出字符长度直接当做全部取出，如果小于则正常开辟空间一个一个将要取出的内容拷贝到新的空间中，最后再传值返回。
• 这里的传值返回需要调用拷贝构造函数深拷贝返回。

5.5.3 clear

//string.h
void clear()
{
	_str[0] = '\0';
	_size = 0;
}

注意：

• 同样因为函数内部行数较少，可以放在头文件的 string 类中作为内联函数，方便后续调用，提升效率。
• clear 只是清除字符串中的内容，并不会将空间释放。

5.6 string 的其他接口

5.6.1 operator =

//string.cpp
//传统写法
string& string::operator=(const string& s)
{
	if (this != &s)	//防止自己给自己赋值
	{
		delete[] _str;
		_str = new char[s._capacity + 1];
		strcpy(_str, s._str);
		_size = s._size;
		_capacity = s._capacity;
	}

	return *this;	//为了连续赋值，需要有返回值
}

// 现代写法
string& string::operator=(string s)
{
	swap(s);
	return *this;
}

5.6.2 operator == / operator != / operator > / operator < / operator >= / operator <=

//string.cpp
bool operator== (const string& lhs, const string& rhs)
{
	return strcmp(lhs.c_str(), rhs.c_str()) == 0;
}

bool operator!= (const string& lhs, const string& rhs)
{
	return !(lhs == rhs);
}

bool operator> (const string& lhs, const string& rhs)
{
	return !(lhs <= rhs);
}

bool operator< (const string& lhs, const string& rhs)
{
	return strcmp(lhs.c_str(), rhs.c_str()) < 0;
}

bool operator>= (const string& lhs, const string& rhs)
{
	return !(lhs < rhs);
}

注意：

• 比较运算符重载函数不在类中实现而是在全局实现的原因。

  以上用于字符和字符串之间的互相比较的函数需要实现在全局中，不需要实现为 string 类的成员函数。因为如果实现为 string 的成员函数其第一个参数就已经固定下来一定为 string 类型的参数，这样就没有办法实现这种比较 bool operator == (const chat* lhs, const string& rhs); 。所以就要求在全局中实现

  但是在进行模拟实现的时候也不需要针对字符串和字符比较 ，字符和字符比较 ，字符串和字符串比较分别写一个运算符重载函数，只需要实现一个再通过隐式类型转换即可适应多种参数类型的情况。

5.6.3 operator << / operator >>

//string.cpp
//流插入
ostream& operator<<(ostream& os, const string& str)
{
	for (size_t i = 0; i < str.size(); i++)
	{
		os << str[i];
	}
	return os;
}

//流提取
istream& operator>>(istream& is, string& str)
{
	str.clear();//清空变量，用于后续存储输入的字符

	int i = 0;
	char buff[256];//定义在栈上，后续开空间比在堆上开空间效率高

	char ch;	//存放读取字符的临时容器
	ch = is.get();	//从流中获取字符，给ch
	while (ch != ' ' && ch != '\n')	//默认检测到空格和换行终止
	{
		// 数据先放到buff，
		buff[i++] = ch;
		if (i == 255)
		{
			buff[i] = '\0';
			str += buff;	//此时提取字符，空间是确定的，不用反复开辟
			i = 0;
		}

		ch = is.get();
	}
    
	if (i > 0)//有字符但是不满255
	{
		buff[i] = '\0';
		str += buff;
	}
	return is;
}

注意：

• 流插入流提取必须在全局实现的原因。

  因为流插入和流提取的第一个操作数的类型必须为 ostream& 或者是 istream& 。

• 为什么这里的流插入和流提取没有成为 string 的友元函数。

  因为这里没有访问 string 成员变量的需求，都可以使用 operator [] + 下标的方式访问到字符串中的数据，所以就没有必要成为 string 的友元函数。

• 流提取中使用 get 获取字符而不用 operator >> 获取字符的原因。

  因为 operator >> 默认对空格和换行都是视为两个字符之间的空格，并不会提取空格和换行，所以就导致 ch 中根本不会出现空格和换行也就无法使得 while 循环 停下。

  但是 get 也是 istream 中提供的一个接口，它可以实现对一个字符的提取，不会无视任何一个字符，这个要求是满足需求的，所以选择它。

• 流提取中引入局部数组 buff 的原因。

  如果不引入局部数组 buff 每次都将提取到的字符直接 += 在 str 后面，因为事前不知道待提取的字符长度，所以可能会会出现多次扩容影响性能。

  这里引入局部数组 buff 先一次性开辟256个字符空间，如果待提取的字符长度超过256就分批次处理，如果待提取的字符待提取的字符长度不足256则直接按照此时的字符长度开辟空间进行提取。并且局部变量定义在栈上，空间开辟效率更高而且是即用即销毁。这样不仅可以避免频繁在堆上动态开辟空间影响效率，还可以避免事先使用 reserve 开辟一个极大的空间但是提取字符很少而导致空间浪费的情况。

  并且如果认为256还是不够大，还是会频繁开辟，还可以进一步提升空间为 512 、1024均可。

5.6.4 getline

//string.h
istream& getline(istream& is, string& str, char delim = '\n');
    
//string.cpp	
istream& getline(istream& is, string& str, char delim)
{
	str.clear();

	int i = 0;
	char buff[256];

	char ch;
	ch = is.get();
	while (ch != delim)
	{
		// 放到buff
		buff[i++] = ch;
		if (i == 255)
		{
			buff[i] = '\0';
			str += buff;
			i = 0;
		}

		ch = is.get();
	}

	if (i > 0)
	{
		buff[i] = '\0';
		str += buff;
	}

	return is;
}

注意：

• getline 和 operator >> 的思路基本一致，只需要在 while 循环处的条件判断作出更改即可。
• 因为这里的最后一个参数是缺省参数，注意缺省参数只可以在声明的时候给，定义的时候不能给。

5.7 补充：三种 swap 的辨析

5.7.1 算法库中的 swap

根据算法库中 swap 提供的源码可以看出其本质就是创建一个新的临时空间，再对 a b 进行来回赋值实现的交换，但是因为 string 的赋值会调用拷贝构造，并且拷贝构造是深拷贝，如果要实现两个字符串的交换则需要析构三次、构造三次，代价极大，过于复杂。不推荐使用。

//调用
tcq::string s1("hello world");
tcq::string s2("xxxxxxxxxxxxxxxxx");

swap(s1, s2);

5.7.2 string 成员函数中的 swap

string 成员函数中的 swap 只需要交换 s1 和 s2 的指针、size 、capacity 即可。

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

5.7.3 string 定义在全局的 swap

//string.cpp
void swap(string& s1, string& s2)
{
    s1.swap(s2);
}

其底层本质还是调用 string 成员函数中的 swap 完成功能，但是这样设计了一个全局的 swap 就会防止调用上面第一个算法库中自带的 swap 。

因为算法库中的 swap 本质是一个模版，当模版和普通函数同时存在的时候就会优先使用现成的普通函数也就是这里的定义在全局的 swap 函数，就不会调用那个算法库中比较低效率的 swap。

6. 有关 string 的思考

6.1 写时拷贝

在模拟实现 string 的过程中，可以明显感受到C++中的深拷贝和浅拷贝的综合运用，深拷贝更改安全但是过程过于繁琐低效，浅拷贝更加高效但是对于空间的管理并不安全。那么有没有什么办法可以同时兼容二者的优点呢？

写时拷贝可以达到这个目的。写时拷贝就是一种拖延症，是在浅拷贝的基础之上增加了引用计数的方式来实现的。

引用计数：用来记录资源使用者的个数。在构造时，将资源的计数给成1，每增加一个对象使用该 资源，就给计数增加1，当某个对象被销毁时，先给该计数减1，然后再检查是否需要释放资源， 如果计数为1，说明该对象时资源的最后一个使用者，将该资源释放；否则就不能释放，因为还有 其他对象在使用该资源。