C++知识整理day5容器——string容器

0.前置知识–STL简介

STL(standard template libaray-标准模板库)：是C++标准库的重要组成部分，不仅是一个可复用的组件库，而且是一个包罗数据结构与算法的软件框架。
STL的六大组件：

我们之前在数据结构阶段学了很多，包括顺序表、链表、栈、队列、二叉树等等；在之后我们在做算法题时，需要用到哪个数据结构，靠我们手写是不太现实的，C++帮我们封装了很多的容器，本质上他们都是给我们实现好的一个个类，我们直接使用即可。当然我们也要学习他的底层，这是很重要的。
本节我们先来学习一下string类。这里有个小知识点，其实string类是不属于STL里的容器的。因为string类的出现是比容器早很多的，因为需要频繁使用字符串。所以string类在设计的时候，不是设计的很好。

string类的内容大概是这样，有size，也有capacity，当然里面有很多的成员方法。（其实里面也有buffer数组，了解一下）

1.为什么要学习string类？

C语言中，字符串是以’\0’结尾的一些字符的集合，为了操作方便，C标准库中提供了一些str系列的库函数，但是这些库函数与字符串是分离开的，不太符合OOP的思想，而且底层空间需要用户自己管理，稍不留神可能还会越界访问。比如说strcpy，我们必须有足够的空间让他来拷贝，他的空间大小是固定的，不想string，他的本质就是一个类，是可以自动扩容的。

2.auto关键字和范围for

2.1 auto关键字

1. 使用auto修饰的变量，是具有自动存储器的局部变量，后来这个不重要了。C++11中，标准委员会变废为宝赋予了auto全新的含义即：auto不再是一个存储类型指示符，而是作为一个新的类型指示符来指示编译器，auto声明的变量必须由编译器在编译时期推导而得。

2. 用auto声明指针类型时，用auto和auto*没有任何区别，但用auto声明引用类型时则必须加&
   

3. 当在同一行声明多个变量时，这些变量必须是相同的类型，否则编译器将会报错，因为编译器实际只对第一个类型进行推导，然后用推导出来的类型定义其他变量。
   

4. auto不能作为函数的参数，可以做返回值，但是建议谨慎使用
   
   

5. auto不能直接用来声明数组
   
   Q：写了类型本来就不费事，还要使用auto干什么？
   A：等到后面写容器迭代器的，就会很好用。

2.2 范围for

1. 对于一个有范围的集合而言，由程序员来说明循环的范围是多余的，有时候还会容易犯错误。因此C++11中引入了基于范围的for循环。for循环后的括号由冒号“ ：”分为两部分：第一部分是范围内用于迭代的变量，第二部分则表示被迭代的范围，自动迭代，自动取数据，自动判断结束。
2. 范围for可以作用到数组和容器对象上进行遍历
3. 范围for的底层很简单，容器遍历实际就是替换为迭代器，这个从汇编层也可以看到

示例：

int a[5] = { 1, 2, 3, 4 ,5 };for (auto x : a){cout << x << ' ';}cout << endl;

注意：上面我们写的是auto x : a 其底层是将数组a对应下标的值赋值给x，x只是一个临时拷贝的对象，改变x的值不会影响到数组a，我们若是想改变数组a的值，我们就需要使用引用的概念，示例：

3.string类常用的接口

推荐大家去C++的官网学习对应的接口:https://cplusplus.com/

3.1 string类对象常见的构造

注：这里解释一下npos，npos默认值是-1，即拷贝到字符串str的末尾，当npos大于字符串长度时不会报错，会拷贝完这个字符串。npos是一个静态成员变量，他的类型是size_t。

示例：

string s1();//构造一个空的字符串string s2("hello world!");//用C-string来构造string对象string s3(s2);//拷贝构造string s4(s2, 6);//npos默认值是-1string s5("hello world", 5);//拷贝前五个字符string s6(5, 'x');cout << s1 << endl;cout << s2 << endl;cout << s3 << endl;cout << s4 << endl;cout << s5 << endl;cout << s6 << endl;

3.2 string类对象的访问

示例：

string s("hello world");for (int i = 0; i < s.size(); i++){cout << s[i];}cout << endl;for (int i = 0; i < s.size(); i++){cout << s.at(i);}cout << endl;cout << "s.front():" << s.front() << endl;cout << "s.back():" << s.back() << endl;

Q：使用下标[]和at()有什么区别吗？
A：对于访问字符串，如果越界了的话，[]会直接报错，终止程序运行，而at可以通过抛异常来解决，示例：

对于at()访问越界的字符串，我们只要通过捕异常就可以让程序继续运行。

而通过下标[]来获取越界的字符，会直接终止程序。

3.3 string类对象的遍历–迭代器

通过上面下标的方式也可以遍历字符串，这里我们主要讲解一下通过迭代器来遍历。

Q：既然下标可以遍历，为什么还要使用那么复杂的迭代器来遍历？
A：对于这种顺序结构我们当然优先使用下标来遍历，但是对于像链表这样非顺序结构的，那我们那就只能通过迭代器来遍历链表啦。

示例：

string s("hello world");//1.正向遍历string::iterator it = s.begin();while (it != s.end()){cout << *it;++it;}cout << endl;//2.反向遍历string::reverse_iterator rit = s.rbegin();while (rit != s.rend()){cout << *it;++it;//注意：这里也是++}cout << endl;

补充：

对于被const修饰的字符串：

const string s1("hello world");//3.被const修饰的正向遍历string::const_iterator it = s1.begin();//这样写也可//string::const_iterator it = s1.cbegin();while (it != s1.end()){cout << *it;++it;}cout << endl;//4.被const修饰的反向遍历string::const_reverse_iterator rit = s1.rbegin();//这样写也可//string::const_iterator it = s1.crbegin();while (rit != s1.rend()){cout << *rit;++rit;}cout << endl;

3.4 string类对象的容量操作

Q：为什么string既设计了size，也设计了length？
A：这就涉及到了string的历史，我们之前说过，string类是在STL之前就设计出来了的，字符串的大小更适合使用length，但是之后STL的诞生，都统一使用了size，所以string有两个计算长度的。

示例：


这里的容量是15，若加上‘\0’，则是16，每一个编译器的扩容原理不一样，有的是1.5倍，有的是2倍。

我们重点学后三个：

1. reserve：为string类预留空间
   Q：为什么要预留空间？
   A：如果我们知道这个类大概要多少空间，我们就不需要一步步扩容了，扩容是有时间成本的。reserve主要是对capacity作用，若是reserve预留的空间小于size，则他不会缩小size，示例：
   
2. resize：主要是作用于size，若是n小于原本的size，则会缩减字符，对capacity没有影响，若是n大于原本的size，会使用字符c填充，没有给c，会用’\0’填充，可能会扩大capacity。
   
3. shrink_to_fit：缩容
   

3.5 string类的修改操作

注意：

1. 在string尾部追加字符时，s.push_back( c ) / s.append(1, c) （比较怪，必须这么写）/ s += 'c’三种的实现方式差不多，一般情况下string类的+=操作用的比较多，+=操作不仅可以连接单个字符，还可以连接字符串。
2. 对string操作时，如果能够大概预估到放多少字符，可以先通过reserve把空间预留好。

对于insert和erase参数有很多类型，可以使用下标，也可以通过迭代器。


示例：

	string str = "to be question";string str2 = "the ";string str3 = "or not to be";string::iterator it;// used in the same order as described above:str.insert(6, str2);// to be (the )questionstr.insert(6, str3, 3, 4);// to be (not )the questionstr.insert(10, "that is cool", 8);// to be not (that is )the questionstr.insert(10, "to be ");// to be not (to be )that is the questionstr.insert(15, 1, ':');// to be not to be(:) that is the questionit = str.insert(str.begin() + 5, ','); // to be(,) not to be: that is the questionstr.insert(str.end(), 3, '.');// to be, not to be: that is the question(...)str.insert(it + 2, str3.begin(), str3.begin() + 3);// (or )cout << str << '\n';string str("This is an example sentence.");cout << str << '\n';// "This is an example sentence."str.erase(10, 8);                        //            ^^^^^^^^cout << str << '\n';// "This is an sentence."str.erase(str.begin() + 9);               //           ^cout << str << '\n';// "This is a sentence."str.erase(str.begin() + 5, str.end() - 9);  //       ^^^^^cout << str << '\n';// "This sentence."

注意：insert和erase要谨慎使用，他的时间复杂度是O(n)的
g.cn/direct/e53fe183586f40bdbd3a9598c4eb5d93.png)

string str;string base = "The quick brown fox jumps over a lazy dog.";str.assign(base);cout << str << endl;str.assign(base, 10, 9);cout << str << endl;str.assign("pangrams are cool", 7);cout << str << endl;str.assign("c-string");cout << str << endl;str.assign(10, '*');cout << str << endl;str.assign(base.begin() + 16, base.end() - 12);cout << str << endl;

其实，像insert、erase、replace里面参数构造都是差不多，都是类似构造的类型，而且时间复杂度都是O(n)的。

3.7 string类对象字符串操作

1. c_str()
   我们为什么想把我们的string类转换成C语言中的字符串（就是string类中的成员函数char*），是因为C语言中的字符串是以’\0’结束的，我们很好控制它。示例：
2. copy()：用string类对象给char*字符串拷贝。注意他的返回值是拷贝的长度
   
   
3. substr()
   
   
4. 各种find操作

string file1("test.cpp");size_t pos1 = file1.find('.');if (pos1 != string::npos)//npos是个静态成员变量，类型是size_t{string str1 = file1.substr(pos1);cout << str1 << endl;}string file2("test.cpp.tar.zip");size_t pos2 = file2.rfind('.');if (pos2 != string::npos){string str2 = file2.substr(pos2);cout << str2 << endl;}string str("Please, replace the vowels in this sentence by asterisks.");size_t found = str.find_first_not_of("aeiou");while (found != string::npos){str[found] = '*';found = str.find_first_not_of("aeiou", found + 1);}cout << str << endl;

3.8 string类对象的非成员函数

这里的函数为什么要设计成非成员函数的，是因为他不像让第一个参数默认是this指针。

这里，我们重点说一下getline函数，它是获取一整行字符；我们知道scanf和cin遇到空格和换行都会停止读取，但是很多string字符串中是有很多空格的，我们不得不使用getline函数。而且getline函数可以指定遇到什么字符停止读取，默认是’\n’换行。

3.9 string类对象的静态成员变量

就是我们上面提到过的npos

4.小试牛刀–例题

4.1 字符串中第一个出现唯一的字符

class Solution {
public:int firstUniqChar(string s) {int count[26];for(auto c : s){count[c - 'a']++;}for(int i = 0; i < s.size(); i++){if(count[s[i] - 'a'] == 1) return i;}return -1;}
};

4.2 反转字符串

class Solution {
public:void reverseString(vector<char>& s) {int i = 0, j = s.size() - 1;while(i < j){swap(s[i++], s[j--]);}}
};

4.3 仅仅反转字母

class Solution {
public:bool IsLetters(char c){if((c >= 'a' && c <= 'z') || (c >= 'A'&& c <= 'Z'))return true;return false;}string reverseOnlyLetters(string s) {int i = 0, j = s.size() - 1;while(i < j){while(i < j && !IsLetters(s[i])) i++;while(i < j && !IsLetters(s[j])) j--;swap(s[i], s[j]);i++, j--;}return s;}
};

4.4 字符串相加

class Solution {
public:string addStrings(string num1, string num2) {string s;int n1 = num1.size() - 1;int n2 = num2.size() - 1;int ret = 0;//个位相加的值int t = 0;//进位while(n1 >= 0 && n2 >= 0){ret = t + (num1[n1--] - '0') + (num2[n2--] - '0');t = ret / 10;ret %= 10;s.push_back('0' + ret);}while(n1 >= 0){ret = t + (num1[n1--] - '0');t = ret / 10;ret %= 10;s.push_back('0' + ret);}while(n2 >= 0){ret = t + (num2[n2--] - '0');t = ret / 10;ret %= 10;s.push_back('0' + ret);}if(t == 1) s.push_back('0' + 1);reverse(s.begin(), s.end());return s;}
};