3.3 处理string对象中的字符
可以将string对象当成字符数组来处理
练习：密码翻译，输入一个只包含小写字母的字符串，将其中的每个字母替换成它的后继字母，如果原字母是’z’，则替换成’a’
#include<iostream> using namespace std; int main() { string s; getline(cin, s); for (auto &c : s) if (c >= 'a' && c <= 'z') c = (c - 'a' + 1) % 26 + 'a'; else if ( c >= 'A' && c <= 'Z' ) c = (c - 'A' + 1) % 26 + 'A'; cout << s <<endl; return 0; }
六、cpp中的函数
1.函数基础
一个典型的函数定义包括以下部分：返回类型、函数名字、由0个或多个形参组成的列表以及函数体。
int fact(int val) { int ret = 1; while (val > 1) ret *= val -- ; return ret; }
函数名字是fact，它作用于一个整型参数，返回一个整型值。return语句负责结束fact并返回ret的值。
1.1调用函数
int main() { int j = fact(5); cout << "5! is " << j << endl; return 0; }
函数的调用完成两项工作：一是用实参初始化函数对应的形参，二是将控制权转移给被调用函数。此时，主调函数的执行被暂时中断，被调函数开始执行。
1.2形参和实参
实参是形参的初始值。第一个实参初始化第一个形参，第二个实参初始化第二个形参，依次类推。形参和实参的类型和个数必须匹配。
形参也可以设置默认值，但所有默认值必须是最后几个。当传入的实参个数少于形参个数时，最后没有被传入值的形参会使用默认值。
fact("hello"); // 错误：实参类型不正确 fact(); // 错误：实参数量不足 fact(42, 10, 0); // 错误：实参数量过多 fact(3.14); // 正确：该实参能转换成int类型，等价于fact(3);
1.3函数的形参列表
//可以为空但不能省略 void f1() {/* …. */} // 隐式地定义空形参列表 void f2(void) {/* … */} // 显式地定义空形参列表
形参列表中的形参通常用逗号隔开，其中每个形参都是含有一个声明符的声明。即使两个形参的类型一样，也必须把两个类型都写出来：
int f3(int v1, v2) {/* … */} // 错误 int f4(int v1, int v2) {/* … */} // 正确
1.4函数返回类型
大多数类型都能用作函数的返回类型。一种特殊的返回类型是void，它表示函数不返回任何值。函数的返回类型不能是数组类型或函数类型，但可以是指向数组或者函数的指针。
1.5局部变量、全局变量、静态变量
局部变量只可以在函数内部使用，全局变量可以在所有函数内使用。当局部变量与全局变量重名时，会优先使用局部变量。
静态变量：static 等于在函数内部开了一个只有函数能用的全局变量
2.参数传递
2.1传值参数
当初始化一个非引用类型的变量时，初始值被拷贝给变量。此时，对变量的改动不会影响初始值。
#include <iostream> using namespace std; int f(int x) { x = 5; } int main() { int x = 10; f(x); cout << x << endl; return 0; }
2.2传引用参数
当函数的形参为引用类型时，对形参的修改会影响实参的值。使用引用的作用：避免拷贝、让函数返回额外信息。
#include <iostream> using namespace std; int f(int &x) { x = 5; } int main() { int x = 10; f(x); cout << x << endl; return 0; }
3.数组形参
在函数中对数组中的值的修改，会影响函数外面的数组。
一维数组形参写法
// 尽管形式不同，但这三个print函数是等价的 void print(int *a) {/* … */} void print(int a[]) {/* … */} void print(int a[10]) {/* … */}
void print(int a[]) { for (int i = 0; i < 10; i ++ ) cout << a[i] << endl; } int main() { int a[10]; for (int i = 0; i < 10; i ++ ) a[i] = i; print(a); return 0; }
多维数组形参的写法：
// 多维数组中，除了第一维之外，其余维度的大小必须指定 void print(int (*a)[10]) {/* … */} void print(int a[][10]) {/* … */}
void print(int a[][10]) { for (int i = 0; i < 10; i ++ ) { for (int j = 0; j < 10; j ++ ) cout << a[i][j] << ' '; cout << endl; } } int main() { int a[10][10]; for (int i = 0; i < 10; i ++ ) for (int j = 0; j < 10; j ++ ) a[i][j] = j; print(a); return 0; }
3.返回类型和return语句
return语句终止当前正在执行的函数并将控制权返回到调用该函数的地方。return语句有两种形式：
return; return expression;
3.1无返回值函数
没有返回值的return语句只能用在返回类型是void的函数中。返回void的函数不要求非得有return语句，因为在这类函数的最后一句后面会隐式地执行return。
通常情况下，void函数如果想在它的中间位置提前退出，可以使用return语句。return的这种用法有点类似于我们用break语句退出循环。
3.2有返回值的函数
只要函数的返回类型不是void，则该函数内的每条return语句必须返回一个值。return语句返回值的类型必须与函数的返回类型相同，或者能隐式地转换函数的返回类型。
4.函数递归
函数调用前要先声明
递归函数需要有结束条件，否则会进入死循环
在一个函数内部，也可以调用其本身
七、类、结构体、指针、引用
1.类与结构体
类中的变量和函数被统一称为类的成员变量。
private后面的内容是私有成员变量，在类的外部不能访问；public后面的内容是公有成员变量，在类的外部可以访问。
结构体和类的作用是一样的。不同点在于类默认是private，结构体默认是public。
类关键字：class
结构体关键字：struct
2.指针和引用
指针指向存放变量的值的地址。因此我们可以通过指针来修改变量的值。
#include <iostream> using namespace std; int main() { int a = 10; int *p = &a; *p += 5; cout << a << endl; return 0; }
数组名是一种特殊的指针。指针可以做运算:
#include <iostream> using namespace std; int main() { int a[5] = {1, 2, 3, 4, 5}; for (int i = 0; i < 5; i ++ ) cout << *(a + i) << endl; return 0; }
引用和指针类似，相当于给变量起了个别名。
#include <iostream> using namespace std; int main() { int a = 10; int &p = a; //引用（别名），a变p也变 p += 5; cout << a << endl; return 0; }
3.链表
#include <iostream> using namespace std; struct Node { int val; Node* next; } *head; int main() { for (int i = 1; i <= 5; i ++ ) { Node* p = new Node(); //new 动态开辟一个结构体 p->val = i; p->next = head; head = p; } /*-> 和 . 的区别： 当p为一个变量时，调用成员变量需要用.next 当p为一个指针变量时，调用成员变量需要用-> */ //auto自动判断变量类型，等价于Node* //auto p = new Node(1); //Node* p = new Node(1); for (Node* p = head; p; p = p->next) cout << p->val << ' '; cout << endl; return 0; }
八、STL
1.#include <vector>
vector是变长数组，支持随机访问，不支持在任意位置 O(1) 插入。为了保证效率，元素的增删一般应该在末尾进行。
1.1 声明
#include <vector> // 头文件 vector<int> a; // 相当于一个长度动态变化的int数组 vector<int> b[233]; // 相当于第一维长233，第二位长度动态变化的int数组 struct rec{…}; vector<rec> c; // 自定义的结构体类型也可以保存在vector中
1.2 size/empty
size函数返回vector的实际长度（包含的元素个数）
empty函数返回一个bool类型，表明vector是否为空。二者的时间复杂度都是 O(1)。
所有的STL容器都支持这两个方法，含义也相同，之后我们就不再重复给出。
1.3 clear
clear函数把vector清空。
1.4 迭代器
迭代器就像STL容器的“指针”，可以用星号*操作符解除引用。
一个保存int的vector的迭代器声明方法为：
vector<int>::iterator it;
vector的迭代器是“随机访问迭代器”，可以把vector的迭代器与一个整数相加减，其行为和指针的移动类似。可以把vector的两个迭代器相减，其结果也和指针相减类似，得到两个迭代器对应下标之间的距离。
1.5 begin/end
begin函数返回指向vector中第一个元素的迭代器。例如a是一个非空的vector，则*a.begin()与a[0]的作用相同。
所有的容器都可以视作一个“前闭后开”的结构，end函数返回vector的尾部，即第n 个元素再往后的“边界”。*a.end()与a[n]都是越界访问，其中n = a.size()。
下面两份代码都遍历了vector<int> a，并输出它的所有元素。
for (int i = 0; i < a.size(); i ++) cout << a[i] << endl;
for (vector<int>::iterator it = a.begin(); it != a.end(); it ++) cout << *it << endl;
1.6 front/back
front函数返回vector的第一个元素，等价于*a.begin()和a[0]。
back函数返回vector的最后一个元素，等价于*--a.end()和a[a.size() – 1]。
1.7 push_back()和pop_back()
a.push_back(x)把元素x插入到vector a的尾部。
b.pop_back()删除vector a的最后一个元素。
2.#include <queue>
头文件queue主要包括循环队列queue和优先队列priority_queue两个容器。
2.1 声明
queue<int> q; struct rec{…}; queue<rec> q; //结构体rec中必须定义小于号 priority_queue<int> q; // 大根堆 priority_queue<int, vector<int>, greater<int>> q; // 小根堆 priority_queue<pair<int, int>>q;
2.2 循环队列queue
push // 从队尾插入 pop // 从队头弹出 front // 返回队头元素 back // 返回队尾元素
2.3 优先队列priority_queue
push // 把元素插入堆 pop // 删除堆顶元素 top // 查询堆顶元素（最大值）
3.#include <stack>
头文件stack包含栈。声明和前面的容器类似。
push // 向栈顶插入 pop // 弹出栈顶元素
4.#include <deque>
双端队列deque是一个支持在两端高效插入或删除元素的连续线性存储空间。它就像是vector和queue的结合。与vector相比，deque在头部增删元素仅需要O(1) 的时间；与queue相比，deque像数组一样支持随机访问。
[] // 随机访问 begin/end // 返回deque的头/尾迭代器 front/back // 队头/队尾元素 push_back // 从队尾入队 push_front // 从队头入队 pop_back // 从队尾出队 pop_front // 从队头出队 clear // 清空队列
5.#include <set>
头文件set主要包括set和multiset两个容器，分别是“有序集合”和“有序多重集合”，即前者的元素不能重复，而后者可以包含若干个相等的元素。set和multiset的内部实现是一棵红黑树，它们支持的函数基本相同。
5.1 声明
set<int> s; struct rec{…}; set<rec> s; // 结构体rec中必须定义小于号 multiset<double> s;
5.2 size/empty/clear
与vector类似
5.3 迭代器
set和multiset的迭代器称为“双向访问迭代器”，不支持“随机访问”，支持星号*解除引用，仅支持++和--两个与算术相关的操作。
设it是一个迭代器，例如set<int>::iterator it;
若把it ++，则it会指向“下一个”元素。这里的“下一个”元素是指在元素从小到大排序的结果中，排在it下一名的元素。同理，若把it --，则it将会指向排在“上一个”的元素。
5.4 begin/end
返回集合的首、尾迭代器，时间复杂度均为 O(1)。
s.begin()是指向集合中最小元素的迭代器。
s.end()是指向集合中最大元素的下一个位置的迭代器。换言之，就像vector一样，是一个“前闭后开”的形式。因此-- s.end()是指向集合中最大元素的迭代器。
5.5 insert
s.insert(x)把一个元素x插入到集合s中，时间复杂度为O(logn)。
在set中，若元素已存在，则不会重复插入该元素，对集合的状态无影响。
5.6 find
s.find(x)在集合s中查找等于x的元素，并返回指向该元素的迭代器。若不存在，则返回s.end()`。时间复杂度为 O(logn)。
5.7 lower_bound/upper_bound
这两个函数的用法与find类似，但查找的条件略有不同，时间复杂度为O(logn)。
s.lower_bound(x)查找大于等于x的元素中最小的一个，并返回指向该元素的迭代器。
s.upper_bound(x)查找大于x的元素中最小的一个，并返回指向该元素的迭代器。
5.8 erase
设it是一个迭代器，s.erase(it)从s中删除迭代器it指向的元素，时间复杂度为 O(logn)。
设x是一个元素，s.erase(x)从s中删除所有等于x的元素，时间复杂度为 O(k+logn)，其中 k 是被删除的元素个数。
5.9 count
s.count(x)返回集合s中等于x的元素个数，时间复杂度为O(k+logn)，其中 k 为元素x的个数。
6.#include <map>
map容器是一个键值对key-value的映射，其内部实现是一棵以key为关键码的红黑树。Map的key和value可以是任意类型，其中key必须定义小于号运算符。
6.1 声明
map<key_type, value_type> name; //例如： map<long long, bool> vis; map<string, int> hash; map<pair<int, int>, vector<int>> test;
6.2 size/empty/clear/begin/end
均与set类似。
6.3 insert/erase
与set类似，但其参数均是pair<key_type, value_type>。
6.4 find
h.find(x)在变量名为h的map中查找key为x的二元组。
6.5 []操作符
h[key]返回key映射的value的引用，时间复杂度为O(logn)。
[]操作符是map最吸引人的地方。我们可以很方便地通过h[key]来得到key对应的value，还可以对h[key]进行赋值操作，改变key对应的value。
