一、STL简介1.1 历史沿革STL 全称标准模板库是 C 标准库里核心的组成部分它不只是一套可以直接复用的代码组件库更是一套整合了各类常用数据结构与配套算法的完整软件开发框架。STL 发展至今衍生出四个主流实现版本所有版本都起源于惠普实验室推出的原始 HP 版本这个原始版本由 Alexander Stepanov 与 Meng Lee 共同开发遵循开源规则允许任何人免费复制、修改、传播代码也支持商用开发唯一约束是衍生出的代码也必须保持开源。这一版本是后续所有 STL 实现的基础。第二个是 P.J. 版本基于 HP 版本二次开发被 Windows 平台的 Visual C 编译器采用该版本代码不允许公开与自定义修改同时存在代码可读性差、变量符号命名晦涩难懂的缺陷。第三个为 RW 版本由 Rouge Wage 公司基于 HP 版本开发配套 C Builder 编译器使用同样不支持公开修改源码代码可读性只能达到普通水平。最后是 SGI 版本由 Silicon Graphics 公司在 HP 版本基础上实现Linux 环境下的 GCC 编译器默认搭载该版本它拥有优秀的跨平台移植能力源码完全开放开发者可以自由修改、商用分发并且代码命名、编程逻辑清晰易懂可读性在所有版本里表现最佳我们后续学习 STL、翻阅底层源码时也主要以 SGI 版本作为参考标准。1.2 STL六大组件STL在面试中经常考察在工作中“踩在前人的肩膀上”也能使工作更加轻松。二、string2.1 为什么学习string我们学习 Cstring 类的核心原因可以通过对比 C 语言原生字符串直观理解C 语言里的字符串依靠末尾\0标记结束标准库提供 str 系列函数用来完成拷贝、拼接、求长等操作但这类函数和字符串数据本身相互分离不符合面向对象的封装设计思路。同时底层字符数组的内存开辟、释放、扩容都需要开发者手动管控代码稍有疏漏就容易发生数组越界访问、内存泄漏、缓冲区溢出等问题。而在日常开发和算法刷题场景里string 类有着不可替代的实用价值不论是在线 OJ 算法平台的字符串类考题还是项目实际业务开发几乎都会选用 string 类处理文本数据很少再使用 C 语言的字符数组与 str 库函数。string 封装了全套字符串操作逻辑内存自动管理、接口调用简洁安全像字符串转整形数字、大数字符串相加这类高频面试算法题也都会基于 string 类来实现大幅降低手写字符串底层逻辑的开发成本与出错概率。2.2 标准库中的string类2.2.1 构造函数使用标准库 string 类时代码开头必须引入string头文件同时搭配 using namespace std。先看string的构造函数C98中提供了7种构造函数其中无参的构造、带参的构造以及拷贝构造最为重要。接下来我们就使用一下这三个函数#includeiostream using namespace std; int main() { string s1; string s2(1111111); string s3(s2); cout s1 endl; cout s2 endl; cout s3 endl; cin s1; cout s1 endl; return 0; }string类里面已经重载了流输入和流输出操作符可以直接使用。再试试其他的构造函数#includeiostream using namespace std; int main() { string s1; string s2(hello world); string s3(s2); cout s1 endl; cout s2 endl; cout s3 endl; string s4(s2, 6); cout s4 endl; string s5(s2, 6, 3); cout s5 endl; string s6(hello world, 5); cout s6 endl; string s7(10, c); cout s7 endl; return 0; }2.2.2 operator[]与迭代器遍历string类中提供的operator[]让我们可以把字符串当成数组一样用直接通过“下标”访问和修改其中的字符还可以自动检查越界越界就会报错不像C语言有可能检查不出越界。#includeiostream using namespace std; int main() { string s2(hello world); s2[0] c; cout s2 endl; return 0; }我们可以通过size这个函数来获取字符串的大小从而轻松地遍历字符串也可以通过迭代器来遍历其中的*和都是运算符重载。所有容器都有对应的迭代器用于遍历。上述是正向迭代器还有反向迭代器如果要遍历的是常量就不能用普通迭代器要用const迭代器。2.2.3 auto和范围forC11 还提供了便捷语法 auto 关键字与范围 for 循环方便后续容器与字符串的遍历操作。它可以自动赋值自动迭代自动判断结束。它的底层就是迭代器。早期 C/C 里 auto 仅用来标记具备自动存储周期的局部变量该作用在 C11 中被完全舍弃新标准赋予它自动类型推导的全新功能。使用 auto 定义变量时必须同步给出初始值编译器会在编译阶段根据初始值自动推导出变量的实际类型没有初始化值的 auto 变量会直接触发编译报错。auto 修饰指针时 auto 与 auto * 书写效果完全一致但如果想要定义引用类型必须在 auto 后手动添加 符号同一行代码中用 auto 声明多个变量时所有变量推导得出的类型必须完全相同一旦出现类型差异就会编译失败。auto 存在多处使用限制它不能作为函数形参的类型虽然可以用作函数返回值但可读性较差日常开发中建议谨慎使用同时 auto 无法直接用来定义数组。在 STL 容器场景中 auto 有极高实用价值比如遍历 map 容器时可以替代冗长的迭代器完整类型大幅简化代码书写。范围 for 循环同样是 C11 新增语法传统 for 循环需要手动控制循环边界、下标自增逻辑书写繁琐还容易出现越界问题。范围 for 将循环内容用冒号分割前半段是接收遍历元素的变量后半段是待遍历的数组或容器底层会自动借助迭代器完成遍历、取值与终止判断无需手动管控下标。它支持普通数组、string 字符串以及所有 STL 容器遍历时配合 auto 自动推导元素类型能进一步简化代码。如果需要在循环内修改原容器、数组的数据遍历变量需要写成 auto 引用形式仅读取数据使用 auto 即可。对比传统下标循环范围 for 代码更简洁出错概率更低底层本质只是编译器将语法自动转换成迭代器遍历逻辑运行效率和传统循环没有区别。2.2.4 capacity函数size和length都是用来获取字符串长度的size更加通用保留length是为了向前兼容。max_size会返回当前系统、当前标准库实现下一个 std::string 对象理论上能容纳的最大字符总数这是理论上限不是程序实际还剩多少内存。当你使用push_back、、append、resize这类接口向字符串尾部新增字符时如果当前已存储字符数量 size 内存总容量 capacity现有内存装满就会触发自动扩容。Linux中的扩容机制有所不同Linux中的扩容是标准的二倍扩容可以用reserve来提前开好指定大小的空间来避免频繁扩容我们指定的容量大小是不包括‘\0’的。如果我们指定的容量比当前容量大一定会扩容如果我们指定的容量大小小于当前容量没有强制要求就看编译器的处理了Visual Studio不会缩Linux会缩。clear函数用于清理字符串中的数据但是不会清除容量。shrink_to_fit用于将字符串的容量缩减到它的size从而节省空间。但编译器的执行也是非强制的。2.2.5 三道例题我们已经知道了string类的许多使用方法现在来几道题练练手。仅反转字母用operator[]来解决这道题很合适。定义left和right分别指向字符串的第一个和最后一个字符left往前走right往后走两者都遇到字母时就交换。交换后继续走。注意整个字符串中都没有字母的情况要处理否则会越界访问。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) { int left 0,right s.size()-1; while(left right) { while(left right !isLetter(s[left])) { left; } while(left right !isLetter(s[right])) { --right; } swap(s[left],s[right--]); } return s; } };字符串中第一个唯一字符可以采用计数排序的思路,时间复杂度是O(N)。只需要开一个大小为26的数组就可以统计每个字符出现的次数了然后再用一个for循环找到第一个只出现一次的字符就解决了class Solution { public: int firstUniqChar(string s) { int count[26] {0}; //统计次数 for(auto ch : s) { count[ch-a] ; } for(size_t i 0;is.size();i) { if(count[s[i]-a] 1) { return i; } } return -1; } };字符串相加字符串相加需要我们手动进位。思路是按位处理每一位将字符转换为整型进行相加操作相加后%10就是和的当前位。如果有进位就存在next里面。所有位都处理完后加一个判断语句如果next不为零就再加一步插入。由于头插需要大量拷贝时间复杂度太大采用尾插后再用reverse逆转字符串是更好的方法。class Solution { public: string addStrings(string num1, string num2) { string str; int end1 num1.size() - 1, end2 num2.size() - 1; //进位 int next 0; while (end1 0 || end2 0) { int val1 end1 0 ? num1[end1--] - 0 : 0; int val2 end2 0 ? num2[end2--] - 0 : 0; int ret val1 val2 next; next ret / 10; ret ret % 10; str (0ret); } if (next 0) { str (0next); } reverse(str.begin(),str.end()); return str; } };2.2.6 修改相关接口在 C 的 string 字符串操作里我们有两大类用于添加字符、文本的接口一类只能在字符串末尾追加内容另一类可以在字符串任意位置插入内容结合示例代码就能把每一种用法、适用场景和区别全部讲明白。首先是仅能在字符串尾部追加内容的三种方式第一种是 push_back 函数它的功能十分单一只允许我们在字符串最后添加一个单独的字符不能直接传入一整段字符串文本如果传入双引号包裹的字符串程序会直接编译报错适合循环逐个拼接单个字符的场景。第二种是 append 函数和 push_back 形成互补它专门用来在字符串尾部拼接一整段连续文本直接传入双引号的字符串常量就能完成拼接适合一次性追加多字符内容。第三种是重载后的 运算符也是日常开发里使用频率最高的写法它兼容两种场景既可以追加单个字符也能直接拼接完整字符串写法简洁直观绝大多数简单的尾部拼接操作我们都会优先选用它。这三种尾部追加接口在执行时都会自动判断当前字符串内存容量是否充足如果现有空间已经存满字符就会触发 string 的自动扩容机制开辟更大的内存空间存放新文本。接下来是功能最强的 insert 插入函数它是唯一支持在字符串头部、中间、尾部任意位置添加内容的接口拥有多个重载版本覆盖了不同的使用需求。第一种重载接收数字下标和字符串第一个参数代表插入的位置下标数字 0 对应字符串最开头填入其他数字则代表在对应序号字符的前方插入不管是长文本还是单个字符组成的短字符串都可以直接作为第二个参数传入第二种重载需要传入三个参数分别是插入下标、重复次数和单个字符作用是在指定位置批量插入多个一模一样的字符不用循环多次调用函数第三种重载接收迭代器与单个字符使用 string 自带的 begin 迭代器就代表在字符串最开头插入字符这种写法和其他 STL 容器的操作逻辑保持统一适合配合迭代器遍历逻辑同步使用。这里有一个非常关键的性能细节需要注意push_back、append、 都只在字符串尾部操作不需要挪动原有字符运行效率更高但所有 insert 操作如果发生在字符串头部或者中间位置插入之后原本该位置往后的所有字符都要统一向后移动频繁在头部插入内容会带来严重的性能损耗如果业务中需要大量在文本前端拼接内容更推荐先在尾部完成全部追加最后反转字符串来实现同等效果。同时不管是尾部追加还是任意位置插入一旦操作触发 string 扩容原本绑定字符串的指针、迭代器、引用都会全部失效后续不能再继续使用。最后我们可以简单区分各类接口的选用逻辑如果只需要在字符串末尾添加内容优先使用简洁的 运算符只添加单个字符可以选用 push_back一次性拼接长文本选用 append只有需要在字符串中间、开头位置插入内容时再根据插入需求选择对应重载版本的 insert 函数。#includeiostream using namespace std; void test_string5() { string s(hello world); s.push_back( ); s.push_back(x); s.append(yyyyyy); cout s endl; s ; s 33333333333; cout s endl; s.insert(0, hello C ); cout s endl; s.insert(10, zzzz); cout s endl; s.insert(0, p); cout s endl; char ch t; s.insert(0, 1, ch); s.insert(s.begin(), ch); cout s endl; } int main() { test_string5(); return 0; }删除接口 eraseerase 拥有多组重载适配各类字符删除需求。第一种重载接收起始下标与删除字符数量能够精准删除字符串中间一段连续字符借助该写法也可实现头部、尾部删除删除首字符就从下标 0 位置删除 1 个字符删除末尾字符则以字符串长度减一作为起始下标再删除单个字符。第二种重载仅接收迭代器参数只会删除迭代器指向的单个字符begin 迭代器对应字符串首位字符可完成头删end 迭代器指向末尾空白位自减后就能定位最后一个有效字符用来实现尾删这套迭代器操作逻辑和 vector 等其他 STL 容器保持统一。第三种重载只传入单个起始下标无需填写删除长度会从该下标位置开始删除往后全部字符快速截断字符串后半段内容。替换接口 replacereplace 用于对字符串指定区间做内容替换基础使用规则为传入替换起始下标、待替换旧内容的字符长度以及用于填充的新字符串底层执行逻辑为先删除指定区间内的字符再插入新文本支持新旧内容长度不相等的替换可轻松完成单字符转多字符、长文本缩短等文本修改操作。查找接口 findfind 函数用于从指定位置向后检索目标字符或子串检索成功返回对应下标检索无匹配内容时会返回 string 内置常量 npos。利用循环搭配 find 和 replace能够遍历并替换字符串内全部目标字符但该方式运行效率很差。string 是连续内存存储结构每一次 replace 操作都会改动原有内存排布大量字符需要向后挪动若字符串较长、待替换内容较多频繁的内存挪动会带来极大性能损耗只适合短字符串少量替换的简易场景。工程开发中批量替换推荐空间换时间的思路规避原地替换的性能损耗。先创建空白临时字符串调用 reserve 接口预分配和原字符串等长的内存空间提前规避循环拼接时 string 反复自动扩容带来的开销再通过范围 for 循环遍历原字符串每一个字符遍历到需要替换的字符时向临时字符串拼接替换后的内容其余字符直接原样追加。全程仅执行尾部追加操作不存在字符移位逻辑运行效率远高于循环 replace。若需要将替换完成的结果覆盖至原字符串优先使用字符串交换操作仅修改内存指针地址相比完整字符拷贝开销几乎可以忽略。#includeiostream using namespace std; void test_string6() { string s(hello world); s.erase(6, 1); cout s endl; // 头删 s.erase(0, 1); cout s endl; s.erase(s.begin()); cout s endl; // 尾删 s.erase(--s.end()); cout s endl; s.erase(s.size() - 1, 1); cout s endl; string ss(hello world); ss.erase(6); cout ss endl; ss.replace(5, 1, %%); cout ss endl; string sss(hello world hello C); size_t pos sss.find( ); while (pos ! string::npos) { sss.replace(pos, 1, %%); cout sss endl; pos sss.find( ,pos2); } cout sss endl; //要替换的字符多的时候以上写法效率极低 //可以用空间换时间 string tmp; tmp.reserve(sss.size()); for (auto ch : sss) { if (ch ) tmp %%; else tmp ch; } cout tmp endl; //sss tmp; // //交换比拷贝赋值更高效 } int main() { test_string6(); }2.2.7 String operation系列这里的c_str主要是用来兼容C语言的。比如打开文件的这段代码就需要一个C语言的字符串我们就用c_str进行转换。#define _CRT_SECURE_NO_WARNINGS #includeiostream using namespace std; int main() { string file; cin file; FILE* fout fopen(file.c_str(), r); char ch fgetc(fout); while (ch ! EOF) { cout ch; ch fgetc(fout); } fclose(fout); }find 接口的查找顺序是从字符串开头往末尾正向遍历一旦找到目标字符或子串就立刻返回这个目标所在的下标位置不会继续向后查找。如果从头到尾都没有匹配到内容会返回 string 内置常量 npos。rfind 和 find 查找方向完全相反它从字符串最后一位字符开始反向向前遍历找到第一个匹配目标就停止并返回下标。如果字符串里存在多个相同分隔符号多层后缀文件名就是典型例子正向 find 只能拿到最靠前的分隔符而 rfind 能定位到整串里最后一个分隔符的位置方便我们拿到真正的文件后缀。substr 是 string 专门用来截取一段子字符串的函数有两种常用重载形式两种用法都会生成全新字符串不会改动原字符串本身。第一种重载只接收一个起始下标参数格式为 substr (pos)。程序会从 pos 对应的字符开始截取该位置到字符串末尾的所有字符。比如拿到小数点的下标后直接传给 substr就能一次性取出小数点后面全部内容非常适合提取文件后缀这类需求。第二种重载接收两个参数格式为 substr (pos, len)。第一个参数 pos 是截取的起始下标第二个参数 len 代表想要截取的字符个数函数只会从起始位置向后拿指定长度的字符不会一直截取到末尾。函数返回值是截取出来的新 string 对象原字符串的数据完全保留不会发生修改。如果传入的起始下标超出字符串有效范围程序会触发越界报错若起始下标合法但第二个长度参数过大超出剩余字符总数它会自动截取到字符串末尾为止不会报错。#define _CRT_SECURE_NO_WARNINGS #includeiostream using namespace std; void test_string7() { //获取后缀 string s(test.cpp); size_t pos s.find(.); string suffix s.substr(pos); cout suffix endl; s test.cpp.zip; pos s.rfind(.); suffix s.substr(pos); cout suffix endl; } int main() { test_string7(); return 0; }find_first_of功能是从字符串开头向后遍历找到第一个属于目标字符集合里的字符返回该字符下标全程正向查找只要匹配集合中任意一个字符就停止检索。 举个直观例子如果传入集合0123456789函数会从头扫描文本找到第一个数字就返回它的位置如果要过滤标点符号把所有标点放进查找集合就能快速定位第一个标点的下标。若整段字符串里没有出现集合内任意字符返回string::npos。find_last_of和 find_first_of 查找方向相反从字符串末尾反向向前遍历找到最后一个属于目标字符集合的字符并返回下标。 比如一段混合数字、字母、符号的文本想拿到末尾最后一个数字的位置就可以用这个接口处理带多层分隔符的文件名、路径时也能一次性匹配斜杠、小数点等多种分隔符号直接锁定最靠后的分隔字符。无匹配字符时同样返回 npos。find_first_not_of正向查找规则反过来找到第一个不在目标字符集合内的字符返回对应下标。 最常用场景是跳过前置无效字符比如字符串开头有一堆空格、制表符把空格和制表符放进查找集合这个函数会直接定位到第一个真正有效的文字快速跳过前面全部空白字符省去手动循环剔除空格的操作。如果整串内容全部都在查找集合中找不到不符的字符则返回 npos。find_last_not_of从字符串尾部倒序查找定位最后一个不属于目标字符集合的字符下标。 典型用途是剔除文本末尾多余空白一段文字结尾带有多个空格、换行符把空白字符作为查找集合传入就能找到最后一个有效文字的位置配合 substr 截取即可删掉尾部所有无效空白同理也能清除字符串末尾多余标点、特殊符号。全串字符都属于查找集合时返回 npos。#define _CRT_SECURE_NO_WARNINGS #includeiostream using namespace std; void SplitFilename(const std::string str) { std::cout Splitting: str \n; std::size_t found str.find_last_of(/\\); std::cout path: str.substr(0, found) \n; std::cout file: str.substr(found 1) \n; } void test_string8() { std::string str(Please, replace the vowels in this sentence by asterisks.); std::cout str \n; std::size_t found str.find_first_of(abcdef); while (found ! std::string::npos) { str[found] *; found str.find_first_of(abcdef, found 1); } std::cout str \n; std::string str1(/usr/bin/man); std::string str2(D:\\code\\learn_cpp\\learn_class\\learn_class_2\\test.cpp); SplitFilename(str1); SplitFilename(str2); } int main() { test_string8(); return 0; }2.2.8 非成员函数运算符重载两种顺序都可以得到拼接后的字符串#includeiostream using namespace std; void test_string8() { string s1(hello); string s2 s1 world; cout s2 endl; string s3 world s1; cout s3 endl; } int main() { test_string8(); return 0; }比较大小的运算符也进行了重载可以随便用。cin默认将空格、换行视为分隔符。而如果我们想让它一次读取一整行的内容就需要用到getline。比如这道题#include iostream using namespace std; int main() { string str; getline(cin,str); size_t pos str.rfind( ); cout (str.size()-(pos 1)) endl; }END