c++:STL:string
1. STL简介
1.1 什么是STL
STL(standard template libaray- 标准模板库 ) ： 是 C++ 标准库的重要组成部分，不仅是一个可复用的组件库，而且是一个包罗数据结构与算法的软件框架。
1.2 STL的六大组件
STL有六大组件，其中现在最重要的是容器和算法两类，容器其实就是数据结构
2.String
2.1auto关键字
（1）auto相当于是一种百变的类型，他可以自动识别变量的类型是什么
这里我们使用auto关键字，他会自动识别i的类型，然后声明出整形J，进行正确的赋值
用 auto 声明指针类型时，用 auto 和 auto* 没有任何区别，但用 auto 声明引用类型时则必须加 &如果我们不加&符号，会导致auto识别出来的是整形，而不是引用
auto不能直接用来声明数组
（2）当在同一行声明多个变量时，这些变量必须是相同的类型，否则编译器将会报错，因为编译器实际只对第一个类型进行推导，然后用推导出来的类型定义其他变量。
我们看到这里的c和f是不同的类型，所以我们在同一行声明他们的时候auto会识别第一个变量c的类型，也就是整形（相当于 int a = c, b = f），然而f是double类型的，所以会报错
auto 不能作为函数的参数，可以做返回值，但是建议谨慎使用，主要是为了防止出现找很多层才能找到数据的类型的情况发生。
（3）auto主要用于数据的类型长度非常长的时候，可以大大简短代码
如果我们不用auto，就需要完整的写出被注释掉的那一大段类型名
2.2范围for
对于一个 有范围的集合 而言，由程序员来说明循环的范围是多余的，有时候还会容易犯错误。因此 C++11中引入了基于范围的 for 循环。 for 循环后的括号由冒号 “ ： ” 分为两部分：第一部分是范围 内用于迭代的变量，第二部分则表示被迭代的范围 ，自动迭代，自动取数据，自动判断结束。对内置类型：
这里我们用了范围for来遍历整形数组，他会自动依次读取数组中的元素，然后赋值给e。范围for不仅可以遍历内置类型也可以作用到容器对象上进行遍历接下来我们看看自定义类型的遍历：
这里我们利用了auto类型来给e声明，auto其实就可以用于这种情况。思考：如果我改变e的值，字符串的内容是不是也会改变呢？
事实证明，改变e的值不会改变字符串的值，因为e只是一个变量，他既不是引用也不是指针，所以没办法改变对象的值。反思：如果我们需要在遍历的时候改变对象的值，那么我们就需要将e声明为引用类型。
但是我们在给自定义类型进行赋值的时候，需要调用多次拷贝构造，如果改成引用类型就可以有效提高效率，而如果我们又不想改变对象本身，我们就需要加上const。
上面的写法是适用于不改变对象本身的遍历行为。
总结：
对于内置类型不需要改变内容：类型（eg：int e/auto e）
对于内置类型需要改变内容：指针（eg：int* e/auto* e）
对于自定义类型不需要改变内容：const auto& e
对于自定义类型需要改变内容：auto& e范围 for 的底层很简单，容器遍历实际就是替换为迭代器，这个从汇编层也可以看到。
2.3构造函数
2.3.1重点掌握
（1）string（）：默认构造
作用：构造一个长度为0的空字符串
如果加上了小括号，我们就会把它当成函数声明，而不是实例化对象。
（2）string（const char* s）：常量字符串初始化
作用：利用常量字符串给对象初始化
（3）string (const string& s)：拷贝构造
作用：通过已有字符串对象给字符串对象初始化
这里我们用的是字符串类型给b对象初始化
2.3.2掌握
（1）string (const string& str, size_t pos, size_t len = npos)：精准拷贝作用：从str字符串的pos位置开始，复制len个字符，如果没有指定就复制到结尾
（2）string (const char* s, size_t n)：从第n个元素开始拷贝作用：用常量字符串s的前n个字符给新的对象初始化
2.4遍历
2.4.1下标加方括号（有const版本和非const版本）
我们可以像使用数组一样对string类进行操作，这是利用了方括号的运算符重载完成的。
这里我们可以看到有个运算符重载，他底层就是通过获取下标信息，然后把对应字符的引用返回去。这里又能体现出引用的作用了，正是引用做返回值可以实现修改原数据才能实现模拟数组的使用效果。
2.4.2迭代器
要用类域指定，是一个类型（像指针但是不一定是指针，可以是通过运算符重载*来实现指针的用法）
使用迭代器之前我们还需要学两个string类中的方法
（1）begin（）：用于返回字符串第一个字符的地址
（2）end（）：用于返回字符串最后一个字符的地址
我们看到迭代器it的用法和指针一样，这是因为要么他就是指针，要么他是指针封装的类
const版本的迭代器：
注意const的修饰方法
从位置上看，他是位于iterator前面，这是因为修饰的不是迭代器本身，而是迭代器指向的对象
从方式上看，他需要加个下划线_。
2.4.3反向迭代器
反向迭代器顾名思义就是反着遍历
那么也就有反向的开始和结束
（1）rbegin（）：返回反向的第一个字符的地址
（2）rend（）：返回反向结束的字符的地址
反向迭代器的名字是：reverse_iterator.
2.4.4 范围for
之前提到的范围for也是很重要的遍历方式，单纯访问的话范围for是最方便的
2.5容量操作
2.5.1重点掌握
（1）size（）：可以返回字符串有效字符个数（比起length更好）
size就是大小的意思
（2）empty（）：判空的方法，如果字符串为空返回true，非空返回false
这里的非0代表true，也就是他是空的，而因为我们用了clear所以的确如此。
（3）clear（）：清空字符串（一般不释放空间）
这里我们先用了clear把str的内容给清空了，所以字符串长度为0，然后我们看到capacity是没有变化的，说明空间没有释放
（4）reserve（）：调整容量大小到指定大小，但是也不会调整到和指定的容量完全相同，要满足对齐规则（缩容非强制，扩容强制）
我们看到这里一旦超过了原本的capacity就会扩容，而小于capacity的都没有缩容，这是因为缩容比较浪费时间，而c++也没有强制规定这个方法要缩容。
在其他系统中可能会实现缩容，但是有一个绝对的条件就是这个方法是不会修改数据内容的，如果缩容后的容量还小于size就最多缩容到size
他的一个应用是减少扩容量提高效率：前提是提前知道要开多少空间，那我们提前开好空间就会减少扩容
（5）resize（）：调整size大小（一定改变size）
小于size：删除数据到指定size大小，不缩容
大于size小于capacity：插入数据，没有指定就插入/0,不缩容
大于capacity:扩容然后插入数据。
要指定数据就直接加在后面即可
（6）关于扩容：
在VS中string的扩容是1.5倍来扩容的，但是因为我们实际上使用的字符串都不会很长，如果频繁申请释放空间就会显得效率低下，所以实际上我们会用空间换时间。
具体来说就是创建了一个字符数组在类string中，当我们的字符串长度小于16的时候就直接存在字符数组中，如果大于16就开辟空间去使用开辟的空间（初始开的空间是字符数组长度的两倍），然后舍弃掉字符数组。虽然浪费了一点空间，但是在实际应用的绝大多数时间我们的效率是提高了的。
那么我们的扩容是一定得1.5倍或者2倍吗？
并不是，只是在实际使用的时候，2倍或1.5倍比较实用，如果一次性开多了就会导致空间浪费，开少了就会导致效率低下
2.5.2掌握
（1）length（）：和size一样可以返回有效字符个数
不过length只适用于部分数据结构，比如链表。因为只有部分数据结构有长度的概念，但是size是个数，所有的数据结构都有个数的概念。
（2）capacity（）：字符串的有效字符容量大小
这里的capacity是15，但是其实他的真实容量是16，因为每个字符串都在结尾默认有/0，所以有效的字符容量就要比实际的容量小一。
（3）shrink_to_fit()：异地缩容，将容量缩小到和自身大小一样
异地缩容的原因：因为不支持从开的空间的中间某个部分进行释放，所以只能在别的地方开一个与自身有效数据大小相同的空间，然后拷贝数据，最后释放原来的空间。
2.6修改操作
2.6.1重点掌握
（1）operator+=：可以实现常量字符串和非常量字符串和字符的链接
在视觉上：很直观看起来，并且用起来也很方便。且string自动管理空间，不需要我们再写代码加空间
（2）c_str():在字符串加上/0，与c语言兼容，返回c形式的字符串
如果我们需要调用C语言的接口，这个时候我们就需要用C语言的字符串形式，加上\0，此时我们调用c_str就行
（3）find ()：寻找指定的字符或者字符串
这里是从str的第一个位置（下标为0）的位置开始找字符1，然后返回它的索引（下标）。
如果没找到会返回整形的最大值。
我们来完成一个小功能：将字符串的空格替换为+
方法一：结合find和replace
逻辑：通过循环进行寻找-》替换的过程
利用find来找到需要替换的位置给到pos变量，然后利用replace进行替换。
注意点：
1.为了提高效率，我们每次都从上一次替换的位置开始find
2.为了防止最后找不到空格时pos变成-1导致替换出错，加个if判断
方法二：空间换时间
我们字符串对象，进行遍历，如果没遇到空格就直接+=上，遇到空格就加上+，这样子就实现了替换的结果。
不过我们的空间复杂度也就变成n了，时间复杂度从n^2变成n。
这并没有什么问题，因为现在计算机的内存空间很大，空间换时间是被允许的
（4）substr（）：从pos位置开始取n个字符串
他可以用于取后缀的情景
这里我们用find找到’.’的位置，然后用substr取pos位置开始的字符，如果指定个数就按照指定的个数来（eg：str.substr(pos,2)）,没有就默认取完
那如果我们的后缀有很多个，但是只取最后一个呢？
那我们就要用rfind从后开始找‘.’
rfind会从字符串的后面开始查找
（5）insert（）：在指定位置插入字符串或者字符（效率较低）
插入字符需要在第二个参数位置填入需要插入的个数
（6）erase（）：从指定位置开始删除指定个数的数据（效率较低）
2.6.2掌握
（1）push_back():尾插单个字符
（2）append（）：尾插常量字符串（最常用的就是这个用法）
(3)assign():更精细的赋值
（4）replace（）：替换
这里我们的replace就是从str的下标为0的位置开始替换，使用str2来替换前两个字符。
但是我们极少用replace，因为他的效率绝大多数情况下很低。
如果替换部分和被替换部分大小一致，直接拷贝就行。
如果不一样就需要挪动数据，而挪动数据的时间复杂度是n^2.
（5）getline（）:获取一行的字符串，哪怕中间有空格
2.6.3了解
（1）find_first_of():寻找指定的字符串中的任意字符，找到了就返回索引
（2）find_first_not_of():寻找指定的字符串中没有的任意字符
2.7访问操作
（1）operator[ ]:就是前面讲过的下标加方括号的访问方式
它出错的反馈是断言报错，会让程序停下
（2）at（）：他的访问也是返回引用，也就是允许修改访问数据
他的出错反馈是抛异常，不会让程序停下
一般情况下，我们不希望程序停下，因为现在所有的大程序都是；一直运行的，如果突然程序停下会造成很严重的后果。所以抛异常这种能告知程序员错误却又不会停下程序的报错机制就很好
3.简单模拟实现string的核心接口
（1）构造函数：
我们先实现带参的构造，因为使用字符串初始化的情况很常见
逻辑：根据字符串的大小创造对应大小的空间给到m_a（string类内部的字符指针），然后把数据通过strcpy复制给m_a指向的空间
对于size和capacity就直接用字符串大小来赋值即可
反思：strlen使用了三次，会不会太浪费时间了？可以怎么修改？
由于strlen是从字符串头部开始搜索/0，所以这里进行了三次遍历，确实浪费了时间
我们或许可以尝试调整成员变量声明的顺序来减少遍历
这样子我们只需要第一次遍历完后给到size，然后利用size去给其他变量使用即可
但是这样子也会有个问题，那就是如果某个人修改了你的成员变量的顺序就会导致程序报错，为了避免这种不易查找的问题，我们换个方法去实现减少遍历
我们可以在函数体内进行初始化
这样子我们就不用担心顺序被打乱而导致的问题了。
反思：虽然我们之前说尽量要在初始化列表里面初始化，但是这并不是绝对的。我们要按照实际的需求来，没有特殊需求就按照之前讲的。
无参构造：
无参构造有个需要注意的点，他不是给一个空指针，而是创建一个空间，给/0。因为我们无参构造要构造出来的是一个空的字符串，那么空的字符串也是有空间的，里面存的是/0.
反思: 我们能不能用一个构造函数实现带参和无参构造函数的功能呢？
使用全缺省构造函数就可以了
（2）析构函数
（3）尾插函数
接下来我们实现push_back和append，因为实现了这两个之后我们的+=操作也就可以通过复用实现。
在实现尾插之前，我们先要写一个扩容函数，因为可能会涉及容量扩充
实现reserve函数：
当我们的num大于现在的capacity的时候进行扩容
开多一个字节空间是因为num是有效字符个数，我们还要考虑到/0.
注意：要记得释放原本的空间，然后更新数据
接下来实现push_back
在扩容的时候还要考虑到特殊情况，当我们的字符串为空的时候，capacity是0，乘2以后还是0，所以在capacity是0的时候要传的是4，只要用上三目运算符即可。
然后我们给size位置赋值ch实现尾插，但是此时我们把/0给覆盖掉了，所以在size++后还要给个\0
接下来实现append
如果我们的size加字符串的大小小于两倍capacity，那么就可以按两倍来扩容。
如果是大于两倍capacity，那么我们就需要按照size+字符串大小来扩容。
字符串的尾插我们利用strcpy直接复制，要注意的是我们的复制地址是m_a+size，因为要从尾部开始复制，然后更新size
注意：
1.不直接按照size+strlen（str）来扩容的原因是：为了防止频繁扩容（当字符串长度较小的时候会导致频繁扩容）
2.为什么是从m_a+size的地址开始复制？
因为这涉及指针的移动，加一表示指针向后移动一位（这里的一位是从下标的角度来的，实际上移动的地址数量还要看指针指向的数据的类型）
接下来实现+=函数
由于前面已经实现了字符和字符串的尾插，所以这里可以直接复用push_back和append
（4）插入函数与删除函数
4.1接下来写insert字符
先判断容量，然后移动数据，最后插入数据
1.判断容量：这里和前面的append的逻辑是一样的
2.移动数据：需要从后面的数据开始移动n个位，因为从前面开始移动可能会覆盖后面的数据
3.插入数据：顺着插入就行了
4.更新size
实际上这里也存在一些问题，当我们头插的时候就出问题了
当我们头插完数据之后，end会减一，而此时end的值是0，正常来说减一之后会变成负一，然后退出while循环，可是这里我们的end是size_t的类型，所以不会小于零而是变成整形最大值，那这样会有两个问题
其一，访问权限冲突：越界过多去访问数组了（越界几百还不容易查出来，越界太多就会）
其二，陷入死循环：因为当pos是0的时候end永远不可能比pos小。
解决方法尝试
将end改为int型？
我们看到就算将end改为int也还是出问题了，明明都是小于零的数，但是却还是没退出循环。这是因为pos是size_t类型的数据，而size_t数据的容量要比int型的要大，所以int会自动类型转换成size_t类型。也就是说在比较的时候end就不是负数了，而是很大的正数，所以不会结束循环。
虽然说我们把pos也改成int可以实现，但是这样子如果用户一开始就给pos输入负数就需要单独处理，比较麻烦，而且这也和库里面的格式不一样，所以我们需要换一种方法。
我们可以考虑把end的位置设置为size+n（挪移后的位置），这样子就可以避免出现让end为负数的情况了。
这样写我们是可以通过n为0的情况的，但是这样子就可以了吗？
虽然我们是来解决n=0情况出现的问题的，但是实际上，我们不仅仅需要解决n为0的情况，还要考虑这样改变后其他情况是否仍然可行
当我们移动的位数是大于一的时候，会出现问题，因为end移动完之后和pos相差n-1，所以我们要改进一下
4.2 接下来通过复用insert字符的形式实现insert字符串
我们如果直接实现insert字符串，他的逻辑和insert字符是高度相似的，所以我们考虑复用
而复用的思想就是通过之前写过的方法去简单的实现某些功能
要实现字符串插入有三步骤
1.容量判断
2.挪动数据
3.插入数据
而我们可以通过复用插入字符实现前面两个比较复杂的功能，然后最后一个插入部分就很简单了
4.3 erase函数
分两种情况
第一种：要删除的长度大于剩下的长度的
全部删除（将pos位置设置为\0，并更新数据即可）
第二种：要删除的长度小于剩下的长度
需要把后面的数据挪上来，直接用strcpy就行
（5）find函数
1.找字符
要找的字符的个数就是：size-pos，满足左闭右开减掉之后就是两者间数据个数
2.找字符串
这里使用strstr进行子串匹配，
对于strstr：如果匹配成功就返回对应地址，失败就返回nullptr。
当我们匹配不到字符串：返回-1也就是最大整数
当我们匹配成功：返回对应的下标（地址相减就是下标值了）
（6）size（）与 capacity（）
对于size和capacity，我们直接返回string对象中的m_size和m_capacity就行了
（7）实现访问遍历
方法一：下标加方括号实现访问遍历的方法，我们有两种函数。
其一是非const版本的，这个版本可以支持通过类似数组的方式改变对象的数据。
其二是const版本的，这个版本只能支持访问而不支持修改。
方法二：迭代器实现遍历。
封装为iterator类型的内置类型或者自定义类型必须实现++后可以访问到下一个数据，且*之后可以访问数据本身
对于底层是数组的自定义类型：访问的时候用指针++就可以，所以这里指针可以封装为iterator类型。
而begin（）和end（）在这里就直接等于数组的首地址和尾地址了（当然在链表结构中就不是了）
我们这里看到，实现迭代器之后我们的范围for也可以使用了，其实就是因为范围for就是迭代器封装后的成果
（8）实现substr
首先我们需要判断给的pos位置是否准确
以及给的len是否大于剩下的字符串长度
如果大于：代表要删完，那我们直接把leftlen（剩下的长度）全部给到len
如果小于：那就按照给的len
最后创建一个新的对象去存字符串，然后返回
但是这里出问题了，我们发现a正常来说应该是合法的字符，可是这里却显示乱码。
这还是因为我们进行的是浅拷贝，把str局部变量释放掉的地址给到了a，所以显示乱码。
解决方法就是写一个深拷贝的拷贝构造。
拷贝构造传统写法：这里我们直接申请一块和str一样的空间，然后strcpy上去就完成深拷贝了
传统写法就是我们直接新建一个数组然后把值拷贝上去
而现代写法指的是它的复用程度更高，更具有普适性
具体来说就是现代写法是通过更多的函数复用来实现功能，从而一种写法可以跨越某个具体的类，推广到其他类的一种写法
现代写法的写法就是利用str的数组先构造一个新的s，然后把s的所有值都和m_a的值交换。这里就是复用了利用字符串进行构造的构造函数
而有人会有疑问我们的s是局部变量，他的空间会销毁，那我们的m_a是不是也会销毁？
其实不然，因为s和新构造的字符串全部值都交换了，所以指向的地址也交换了，s指向的就是nullptr而不是原本的空间了
疑问：但是好像现代写法的行数也没有减少很多，还是这么多行，为什么说它更简洁，更可推广？
因为我们的swap还可以实现两个自定义类型直接交换，这样子就更简洁了，而且复用程度更高
（9）运算符重载
1.0赋值重载（传统写法）
赋值重载要关注两类情况
其一：自己给自己赋值（单独用if语句判断）
其二：其他对象给自己赋值
由于该场景是给已经初始化的对象赋值，所以我们要先释放原来申请的字符空间，然后开辟一个和赋值对象capacity大小一样的空间，利用strcpy复制进去，最后更新相关数据。
1.1现代写法
这里我们复用了拷贝构造来实现赋值重载
疑问一：为什么参数部分变成了string str
因为我们的最终目的是让*this获得一个和赋值对象内容一样但地址不同的空间，所以我们需要构造一个新的字符串对象，且该对象是用赋值对象拷贝来的，然后交换*this和该对象即可
不要引用：避免改变赋值对象本身
不加const：需要和*this交换，加了就无法交换了
疑问二：为什么不用if判断*this和参数是否相等了
因为*this不可能和参数相等，参数是在*this存在之后新构造的，所以他们不可能相等
2.等于与不等于
3.大于小于
4.流插入
这里我们直接使用范围for去访问输出即可，这里的e实际上就是字符类型的
疑问1：为什么str这里不涉及权限放大？
因为我们写了一个const版本的迭代器，所以可以使用const类型的数据进行访问
疑问2：为什么e的类型就是字符类型的？给的不是自定义类型的地址吗？
因为我们的范围for就是迭代器封装的，底层是在begin（）给的地址（str中m_a地址）和end（）(str中m_a尾部地址)地址之间进行遍历，而我们迭代器里面给的地址就是字符数组的地址，所以我们遍历的就是字符类型数据
所以这里的流插入是std里面提供的重载好的流插入函数
5.流提取
由于库里面的流提取实现了先删除原本字符串的功能，所以我们这里也用erase去实现一下。
然后我们get去实现获取字符串，遇到空格或者换行就退出循环。
疑问：为什么不用cin去实现获取字符串？
因为cin和scanf都不能识别空格，所以用他们会出现问题。
但是极端情况下这种方法的效率也有点低，所以我们改进一下方法
这里我们如果采用reserve的方法去控制开辟的空间会有问题
给大了：浪费实际str的空间
给小了：频繁扩容浪费时间
所以我们采取空间换时间的方法
具体来说就是在栈上开临时的空间（buff字符数组），然后在读取阶段把数据加在buff数组上，然后buff满了再+=到str上，这样子可以减少str+=的次数。
最后出循环如果i>0说明还有数据在buff数组里，再+=给str即可
核心就是减少str的频繁扩容提高效率（因为用了栈开空间替代堆开空间，而栈开空间很快）
（10）geiline实现
getline和流提取的不同点是：遇到终止符才停止提取，而这个终止符可以是任意字符，没有指定就是默认\0
4.注意点
1.我们这里没有用模板去实现string，所以是可以分开两个文件的，把函数的定义放到.cpp文件中，把类的声明放在.h文件中。但是要用同一个命名空间封装起来
2.我们如果有多个.cpp文件需要用到.h文件，此时普通的函数（static成员变量也是）就不能定义在.h之中，因为这样子会导致最后的可执行程序中出现两次函数的定义。
5.引用计数的写实拷贝（本质上是浅拷贝）
这个方法使用了两个
第一个是引用计数的变量：用于解决浅拷贝析构多次的问题
如果有对象指向了该空间，那么引用计数变量++
如果需要析构，当引用计数变量为1（说明只有一个对象指向该空间），则析构并让变量为0，否则不析构但是让变量--
第二个是写实拷贝：用于解决浅拷贝多次修改数据的问题
如果引用计数是1，那么直接可以修改数据
如果大于1，先让引用计数--（因为该对象不再指向该空间，而是指向新开的空间），然后对空间进行深拷贝，把新的空间的引用计数置为1，然后才可以修改数据
这种方法在编译器优化不足或者甚至没优化的情况下应用
因为该方法的核心思想-------赌
赌不会开空间，那么他就可以提高效率
就算开空间了也不会亏，最差也是和深拷贝持平
但是为什么他在拷贝的部分的用法被淘汰了？
这涉及进程和线程部分
6.关于swap函数
string可以用的swap一共有三种，他们都可以实现swap的功能，但是效率有不同
（1）string实现的swap
这是专门针对string写的swap函数，提前知道swap底层如何实现，所以效率较高
但是不可给其他对象模仿使用，不具有泛用性
（2）库实现的模板swap
这是库对所有变量，对象写的swap模板，泛用性高，但是由于不能提前知道底层有什么，所以针对性较低，效率可能会较低
就以string为例，T为string类型
我们看到这里有一次拷贝构造，两次赋值重载，说明他进行了三次深拷贝，效率很低
（3）库的swap函数重载
这是库针对string变量实现的swap函数，可以实现和string自己实现的swap函数一样的效果，且实现方法也是一样的。
这确保了程序员在使用的时候可以一招鲜吃遍天，只要都用库的swap就行，只要是可以优化的函数，库都优化过了
疑问：这个swap和上一个库通用的swap用法完全一样，怎么确保就是用的是这个呢？
因为有现成的匹配的函数在，就会优先使用现成的函数
