一.变量、输入输出、表达式和顺序语句1.固定格式#include<iostream>
using namespace std;
int main()
{
cout << "Hello World" << endl;
return 0;
}u
2.变量类型常用：类型字节bool – > false / true – > 0/11bytechar ‘c’, ‘a’, ’ ', ‘\n’1byteint -1247483648 ~ 21474836474bytefloat 1.23, 2.5, 1.235e2 6~7位有效数字4bytedouble 15~16位有效数字8byte更长类型字节long long //-2^63 ~ 2^63-18bytelong double //18~19位有效数字16byte3.输入输出a+bcin输入 cout输出#include<iostream>
using namespace std;
int main()
{
int a,b;
cin >> a >> b; //输入，方向 >>
cout << a + b << a * b << endl;
//输出，方向 <<,
endl->回车
return 0；
}
scanf输入 printf输出#include<cstdio>
using namespace std;
int main()
{
int a,b;
scanf("%d%d", &a, &b); //%d读入整数类型，加&符号
printf("a + b =%d\na * b= %d\n", a + b, a * b);
return 0;
}
浮点数：#include<cstdio>
using namespace std;
int main()
{
float a,b;
scanf("%f%f", &a, &b); //%d读入整数类型，加&符号
printf("a + b =%.2f\na * b= %.3f\n", a + b, a * b);
//浮点数用%f，保留几位小数就在中间加点几
return 0;
}
char型：#include<cstdio>
using namespace std;
int main()
{
char a,b;
scanf("%c%c", &a, &b); //%c读入字符型，%c会读入空格，cin不会
printf("%c%c", a , b);
return 0;
}
double/longlong型：#include<cstdio>
using namespace std;
int main()
{
double a,b;
scanf("%lf%lf", &a, &b);
printf("%lf%lf", a , b);
long long a,b;
scanf("%lld%lld", &a, &b);
printf("%lld%lld", a , b);
return 0;
}
总结int: %dfloat: %fdouble: %lfchar: %clong long: %lld4.表达式b+=a -->b = b+ab-=a -->b = b-ab*=a -->b = bab/=a -->b = b/a强制类型转换int->float float->int(取整)int ->char (ASCII字符表，相互转换)5.顺序结构从前往后，从上往下二、printf语句与判断结构1.printf输出格式使用printf时最好加头文件printf保留小数点后几位#include<cstdio>
#include<iostream>
using namespace std;
int main()
{
double f = 138682436874;
printf("%.7lf\n", f);
return 0;
}
左右对齐，保留小数点，空位补零#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
int a = 1;
int b = 23;
int c = 456;
double d = 12.45;
printf("%5d!\n", a);
//占5个空位，右对齐
printf("%-5d!\n", b); //占5个空位，左对齐
printf("%05d!\n", c); //空位填补0，右对齐
printf("%5.1lf!", d);
//占5位且保留小数位数为1
return 0;
}
2.if语句①最基本语法if-else#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
int score;
cin >> score;
if (score >= 60)
{
cout << "及格" << endl;
} //一条语句可以省略{}
else
{
cout << "不及格" << endl;
}
cout << "结束" << endl;
return 0;
}
②比较运算符
大于 a > b
小于 a < b
大于等于 a >= b
小于等于 a <= b
等于 a == b
不等于a != b
③if-else if#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
int grade;
cin >> grade;
if (grade >= 85) cout << 'A' << endl;
else //蕴含着grade<85
{
if (grade >= 70) cout << 'B' << endl;
else //蕴含着grade<70
{
if (grade >= 60) cout << 'C' << endl;
else //蕴含着grade<60
{
cout << 'D' << endl;
}
}
}
}
可优化为——————>(c和cpp中不根据缩进判断语句结束（Python），根据分号判断)
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
int grade;
cin >> grade;
if (grade >= 85) cout << 'A' << endl;
else if (grade >= 70) cout << 'B' << endl;
else if (grade >= 60) cout << 'C' << endl;
else cout << 'D' << endl;
}
3.条件表达式（1）与 && and（2）或
or（3）非 ！ not#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
int a, b, c, d;
cin >> a >> b >> c >> d;
if (a > b && (c > d
a > d)) cout << "" << endl;
if (a > b
c > d && a > d) cout << "" << endl;
if (!(a > b)) cout << "" << endl;
return 0;
}
三、C++中的循环结构循环语句——代码执行顺序1.while循环可以简单理解为循环版的if语句。if语句是判断一次，如果条件成立，则执行后面的语句；while是每次判断，如果成立，则执行循环体中的语句，否则停止。求1~100中所有数的立方和#include<iostream>
using namespace std;
int main()
{
int i = 1;
int sum = 0;
while (i <= 100)
{
sum += i * i * i;
i++;
}
cout << sum << endl;
return 0;
}
斐波那契数列(水仙花)
f(1) = 1 f(2) = 1
f(n) = f(n-1) + f(n-2) n>=3
#include<iostream>
using namespace std;
int main()
{
int a = 1, b = 1;
int n;
cin >> n;
int i = 0;
while (i < n - 1)
{
int c = a + b;
a = b;
b = c;
i++;
}
cout << a <<endl;
return 0;
}
避免写出死循环
2.do while循环do while语句与while语句非常相似。唯一的区别是，do while语句限制性循环体后检查条件。不管条件的值如何，我们都要至少执行一次循环。（不常用）3.for循环for (init-statement : condition: expression) //init语句； 条件语句； 表达式
{
statement
}
init-statement可以是声明语句、表达式、空语句，一般用来初始化循环变量；condition是条件表达式，和while中的条件表达式作用一样；可以为空，空语句表示true；expression一般负责修改循环变量，可以为空。#include <iostream>
using namespace std;
int main()
{
for (int i = 0; i < 10; i ++ )
{
cout << i << endl;
}
return 0;
}
4.跳转语句①break可以提前从循环中退出，一般与if语句搭配。例题：判断一个大于1的数是否是质数：#include <iostream>
using namespace std;
int main()
{
int n;
cin >> n;
bool is_prime = true;
for (int i = 2; i < n; i ++ )
if (n % i == 0)
{
is_prime = false;
break;
}
if (is_prime) cout << "yes" << endl;
else cout << "no" << endl;
return 0;
}
②continue可以直接跳到当前循环体的结尾。作用与if语句类似。例题：求1~100中所有偶数的和。#include <iostream>
using namespace std;
int main()
{
int sum = 0;
for (int i = 1; i <= 100; i ++ )
{
if (i % 2 == 1) continue;
sum += i;
}
cout << sum << endl;
return 0;
}
5.多层循环#include <iostream>
using namespace std;
int main()
{
for (int i = 0, k = 1; i < 10; i ++ )
{
for (int j = 0; j < 10; j ++, k ++ )
{
cout << k << ' ';
}
cout << endl;
}
return 0;
}
练习：输入一个n，打印n阶菱形。n是奇数。
n = 9时的结果：
*
***
*****
*******
*******
*****
***
*
#include <iostream>
using namespace std;
int main()
{
int n;
cin >> n;
int cx = n / 2, cy = n / 2;
for (int i = 0; i < n; i ++ )
{
for (int j = 0; j < n; j ++ )
if (abs(i - cx) + abs(j - cy) <= n / 2)
cout << '*';
else cout << ' ';
cout << endl;
}
return 0;
}
曼哈顿距离计算公式算法
四、数组1.一维数组1.1数组的定义#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int a[10], b[10];
float f[33];
double d[123];
char c[21];
return 0;
}
1.2数组的初始化#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int a[3] = {0, 1, 2};
// 含有3个元素的数组，元素分别是0, 1, 2
int b[] = {0, 1, 1};
// 长度是3的数组
int c[5] = {0, 1, 2};
// 等价于c[] = {0, 1, 2, 0, 0}，没有给出的值默认为0
char d[3] = {'a', 'b', 'c'};
// 字符数组的初始化
int f[10] = 0; // 将数组全部初始化的常用方式
return 0;
}
1.3数组元素的访问(下标访问)#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int a[3] = {0, 1, 2};
// 数组下标从0开始
cout << a[0] << ' ' << a[1] << ' ' << a[2] << endl;
a[0] = 5;
cout << a[0] << endl;
return 0;
}
数组旋转
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int n, k;
int a[100];
cin >> n >> k;
for (int i = 0; i < n; i ++ ) cin >> a[i];
reverse(a, a + k);
reverse(a + k, a + n);
reverse(a, a + n);
for (int i = 0; i < n; i ++ ) cout << a[i] << ' ';
cout << endl;
return 0;
}
2.多维数组
int a[3][4]; // 大小为3的数组，每个元素是含有4个整数的数组。
int arr[10][20][30] = {0}; // 将所有元素初始化为0// 大小为10的数组，它的每个元素是含有20个数组的数组// 这些数组的元素是含有30个整数的数组
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int b[3][4] = {
// 三个元素，每个元素都是大小为4的数组
{0, 1, 2, 3},
// 第1行的初始值
{4, 5, 6, 7},
// 第2行的初始值
{8, 9, 10, 11}
// 第3行的初始值
};
return 0;
}
五、字符串1.ASCII码每个常用字符都对应一个-128 ~ 127的数字，二者之间可以相互转化。注意：目前负数没有与之对应的字符。#include<iostream>
using namespace std;
int main()
{
char a;
printf("%d", 'a' + 3);
return 0;
}
常用ASCII值：‘A’- 'Z’是65 ~ 90，‘a’ - 'z’是97 - 122，0 - 9是 48 - 57。字符可以参与运算，运算时会将其当做整数2.字符数组
字符串就是字符数组加上结束符’\0’。
可以使用字符串来初始化字符数组，但此时要注意，每个字符串结尾会暗含一个’\0’字符，因此字符数组的长度至少要比字符串的长度多 11 ！
2.1输入输出#include <iostream>
using namespace std;
int main()
{
char str[100];
cin >> str;
// 输入字符串时，遇到空格或者回车就会停止
cout << str << endl;
// 输出字符串时，遇到空格或者回车不会停止，遇到'\0'时停止
printf("%s\n", str);
return 0;
}
读入一行字符串，包括空格#include <iostream>
using namespace std;
int main()
{
char str[100];
fgets(str, 100, stdin);
// gets函数在新版C++中被移除了，因为不安全。
// 可以用fgets代替，但注意fgets不会删除行末的回车字符
string s;
getline(cin, s);
//读入字符串
cout << str << endl;
return 0;
}
2.2常用操作下面函数需要引入头文件#include<string.h>
(1) strlen(str)，求字符串的长度(2) strcmp(a, b)，比较两个字符串的大小，a < b返回-1，a == b返回0，a > b返回1。这里的比较方式是字典序！(3) strcpy(a, b)，将字符串b复制给从a开始的字符数组。3.标准库类型string引入头文件#include<string>
3.1定义和初始化#include <iostream>
#include <string>
using namespace std;
int main()
{
string s1;
// 默认初始化，s1是一个空字符串
string s2 = s1;
// s2是s1的副本，注意s2只是与s1的值相同，并不指向同一段地址
string s3 = "hiya";
// s3是该字符串字面值的副本
string s4(10, 'c');
// s4的内容是 "cccccccccc"
return 0;
}
//scanf无法读入string，但printf可以输出
3.2string操作（1）读写#include <iostream>
#include <string>
using namespace std;
int main()
{
string s1, s2;
cin >> s1 >> s2;
cout << s1 << s2 << endl;
return 0;
}
注意：不能用printf直接输出string，需要写成：printf(“%s”, s.c_str());（2）getline#include <iostream>
#include <string>
using namespace std;
int main()
{
string s;
getline(cin, s);
cout << s << endl;
return 0;
}
（3）string的empty和size操作（注意size是无符号整数，因此 s.size() <= -1一定成立）#include <iostream>
#include <string>
using namespace std;
int main()
{
string s1, s2 = "abc";
cout << s1.empty() << endl; //empty,如果是空返回0，不是空返回1
cout << s2.empty() << endl;
cout << s2.size() << endl;//求长度，时间复杂度O(1)
return 0;
}
（4）string的比较支持 >, <, >=, <=, ==, !=等所有比较操作，按字典序进行比较。（5）为string对象赋值string s1(10, 'c'), s2;
// s1的内容是 cccccccccc；s2是一个空字符串
s1 = s2;
// 赋值：用s2的副本替换s1的副本
// 此时s1和s2都是空字符串
（6）两个string对象相加string s1 = "hello,
"", s2 = "world\n";
string s3 = s1 + s2;
// s3的内容是 hello, world\n
s1 += s2;
// s1 = s1 + s2
（7）字面值和string对象相加做加法运算时，字面值和字符都会被转化成string对象，因此直接相加就是将这些字面值串联起来当把string对象和字符字面值及字符串字面值混在一条语句中使用时，必须确保每个加法运算符的两侧的运算对象至少有一个是stringstring s4 = s1 + ", ";
// 正确：把一个string对象和有一个字面值相加
string s5 = "hello" + ", "; // 错误：两个运算对象都不是string
string s6 = s1 + ", " + "world";
// 正确，每个加法运算都有一个运算符是string
string s7 = "hello" + ", " + s2;
// 错误：不能把字面值直接相加，运算是从左到右进行的
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结构体关键字：struct2.指针和引用指针指向存放变量的值的地址。因此我们可以通过指针来修改变量的值。#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;
}
八、STL1.#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/emptysize函数返回vector的实际长度（包含的元素个数）empty函数返回一个bool类型，表明vector是否为空。二者的时间复杂度都是 O(1)。所有的STL容器都支持这两个方法，含义也相同，之后我们就不再重复给出。1.3 clearclear函数把vector清空。1.4 迭代器迭代器就像STL容器的“指针”，可以用星号*操作符解除引用。一个保存int的vector的迭代器声明方法为：vector<int>::iterator it;
vector的迭代器是“随机访问迭代器”，可以把vector的迭代器与一个整数相加减，其行为和指针的移动类似。可以把vector的两个迭代器相减，其结果也和指针相减类似，得到两个迭代器对应下标之间的距离。1.5 begin/endbegin函数返回指向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/backfront函数返回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 循环队列queuepush
// 从队尾插入
pop
// 从队头弹出
front
// 返回队头元素
back
// 返回队尾元素
2.3 优先队列priority_queuepush
// 把元素插入堆
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 inserts.insert(x)把一个元素x插入到集合s中，时间复杂度为O(logn)。在set中，若元素已存在，则不会重复插入该元素，对集合的状态无影响。5.6 finds.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 counts.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 findh.find(x)在变量名为h的map中查找key为x的二元组。6.5 []操作符h[key]返回key映射的value的引用，时间复杂度为O(logn)。[]操作符是map最吸引人的地方。我们可以很方便地通过h[key]来得到key对应的value，还可以对h[key]进行赋值操作，改变key对应的value。}