北理工视频笔记一：C++ STL

B站北理工视频链接：https://www.bilibili.com/video/BV1pE411E7RV

< iostream>头文件是c++中用于输入输出的文件，在大部分编译器下会包括c语言中<stdio.h>的内容，c语言的头文件在c++中全部可以使用，但是要把后缀.h去掉，在头文件前面加上c，例：

#include<stdlib.h> #include<math.h> #include<string.h> #include<ctype.h> //要换成： #include<cstdlib> #include<cmath> #include<cstring> #include<cctype>

但是不换也不会报错. c++中，用标准库的东西都要加上 std::,但是加入

using namespace std;

加入这行代码就不用加入std::了，但是起名时容易和库函数冲突（prev,next,sort,count都不能取）。 cin判断EOF

int n,m; while(cin>>n>>m) { }

输入的时候，这样写可以判断EOF，在比赛中为了快速签到，会用到cin，可以不用写成

int a; while(scanf("%d",&a)!=EOF) { }

cin的速度比scanf慢不少（哪怕关闭了同步），1e5的数据用cin读入就可能会TLE，此时建议用scanf.

输出小数用printf更加方便，c++格式输出要用到< iomanip >头文件，用cout.setprecision(int digit)来修改精度.

C++标准库

C标准库常用函数回顾

cstring

strlen()字符串长度 strcmp()字符串比较 strcpy()字符串拷贝 memset()暴力清空，无论是字符数组还是整型数组，统统看成同样的数组进行赋值：memset(str,0,sizeof(str)); 或者引用0x3f3f3f来初始话数组，尤其是整数数组： memset(str,0x3f3f3f,sizeof(str)); memcpy()暴力拷贝

< cmath >

三角函数、指数函数、浮点取整函数

< cstdlib >

qsort() C语言快排 rand() 随机数 malloc() free() C语言动态分配内存

< ctime >

time(0),从1970年到现在的秒数（配合随机数）,一般用于初始化随机种子 srand(time(0)); clock()程序启动到目前位置的毫秒数：程序实行之前clock一次，运行完后clock一次 int a=clock(); strlen(str); ...; cout<<clock()-a;

< cctype >

isdigit(),isalpha(),判断字符是否为数字、大小写字母

C++STL < vector >

vector可以被看成一个“超级数组”，既可以和C语言的数组一样用下标访问，也可以像链表一样动态改变长度 2.定义：包含头文件< vector >,定义为vector<数据类型>数组名(数组长度),相当于一个普通数组 #include<iostream> #include<vector> using namespace std; vector<int>arr1(100);//定义：vector<数据类型>数组名(数组大小); //作为一个普通数组时，等价于: int arr2[100];

3.定义:vector<数据类型>数组名；push_back():在数组末尾添加元素

#include<iostream> #include <vector> using namespace std; vector<int>list; int main() { list.push_back(1);//则list[0]=1; list.push_back(2);//list[1]=2; list.push_back(3); return 0; }

vector的添加

#include<iostream> #include <vector> using namespace std; vector<int>arr(100); vector<int>list; int main() { for(int i=0;i<100;i++) { scanf("%d",&arr[i]; cout<<arr[i]<<endl; } for(int i=0;i<100;i++) { int a; cin>>a; list.push_back(a); printf("%d\n",list[i]); } return 0; }

vector遍历

for(int i=0;i<arr1.size();i++) { printf("%d\n",arr1[i]); }

迭代器(iterator)：

vector<int>arr1(100); int arr2[100]; vector<int>::interator p=arr1.begin(); printf("%d",*p);//输出p[0]即arr1[0] p++;//表示其指向下一个元素 //迭代器与普通指针使用方法对比 vector<int>::iterator p1; int *p2; for(p1=arr1.begin();p1!=arr1.end();p1++) { cout<<*p1<<endl; } int i; for(p2=arr2,i=0;i<100;i++,p2++) { cout<<*p2<<endl; }

vector常见操作：

list.size();//数组元素个数O(1) list.clear();//一键清空数组，使得其size变成0，相当于把链表删除O(n) list.empty();//数组是否为空，即size是否为0O(1) list.begin();//数组的首元素迭代器O(1) list,end();//数组最后一个元素的下一个元素的迭代器O(1) //该元素实际在数组中不存在 list.erase(p1);//删除数组某个迭代器所在位置的数字O(n1) list.push_back(1);//往数组后面添加元素O(1) list.pop_back();//删除数组最后一个元素O(1)

< string >

字符串string可以看成一个特殊的vector，string和c语言字符串的关系就和vector和普通数组的关系一样

string str1="hello"; char str2[]="world"; string str3; str3.push_back('!'); cout<<str1<<" "<<str2<<str3<<endl;

vector有的操作string基本都有，唯一区别是size的复杂度，所有参数为字符串的地方既可以是string也可以是C字符串

string str="hello"; str.length();str.size();//O(n) str.insert(1,"aaa");//在下标为1处插入一个字符或字符串O(1) str.insert(str.begin(),'a');//在迭代器处插入一个字符O(n) str.c_str();//返回C语言字符串，用于printf O(n) str.append(str2);//把str2拼接到str后面O(n) str.compare(str2);//strcmp(str,str2) str==str2;//strcmp(str,str2)==0 str+=str2;//str.append(str2); str+='a';//str.push_back('a'); reverse(str.begin(),str.end());//可以实现对str的反转，如12345变成54321 #include <iostream> #include <string> using namespace std; int main() { string str="hello"; string str2="hello"; str.insert(1,"aaa"); cout<<"在下标为1处插入字符串\"aaa\"："<<str<<endl; // str2.insert(str2.begin()+1,"aaa");//不能这么使用，str2.begin()是一个常指针 ，只能插入字符不能插入字符串 str2.insert(str2.begin()+1,'a'); cout<<"在迭代器+1处插入字符\'a\'："<<str2<<endl; str.erase(2); cout<<"在下标为2处调用erase函数："<<str<<endl; str2.erase(str2.begin()+2); cout<<"在迭代器+2处调用erase函数："<<str2<<endl; str.insert(str.begin(),'g'); // str.insert(0,'g');//会报错 cout<<str<<endl; return 0; }

运行结果：

运行结果说明： 1.insert（）函数插入字符串只能用下标，不能用str.begin()+下标，插入字符必须用str.begin()+下标，不能直接用下标； 2.erase()函数，使用下标时会将该下标以及其后面的字符全都删除，只剩下该下标前面的字符串，而使用str.begin()+下标时只会删除该下标对应的字符，不会对其后面的字符串产生影响。

< algorithm >

algorithm和之前的两个头文件不同，它没有定义什么新的类型，而是定义了很多使用的算法，极大简化了代码量。 sort快速排序

int arr[]={2,3,1,5,4}; int n=5; //参数 //排序开始指针 //排序结束指针（最后一个元素的下一个元素的指针） //复杂度O(nlgn) sort(arr,arr+n); for(int i=0;i<n;i++) { //1 2 3 4 5 printf("%d\n",arr[i]); } //如果是vector： vector<int>arr2{2,3,1,5,4}; sort(arr2.begin(),arr2.end());

如果是vector：

vector<int>arr; arr.push_back(2); arr.push_back(3); arr.push_back(1); sort(arr.begin(),arr.end()); // 1 2 3 for(int i=0;i<arr.size();i++) { printf("%d\n",arr[i]); } for(vector<int>::iterator it=arr.begin();it!=arr.end();it++) { printf("%d\n",*it); }

和C语言qsort一样，sort可以使用自定义的比较函数，比较函数参数是两待比较参量，返回值是比较的bool值，内部排序是按小于关系来的，排序结果是升序的，如果像下面的代码一样按大于关系比较，则可以得到降序的排序结果。

#include <iostream> #include <algorithm> #include <vector> using namespace std; vector<int>arr{2,3,1,5,4}; int cmp(int a,int b) { return a>b; } int main() { sort(arr.begin(),arr.end(),cmp);//则其将会按照从大到小的顺序排序 for(vector<int>iterator::it=arr.begin;it!=arr.end();it++) { printf("%d\n",*it); } return 0; }

注意：自己定义的结构体一定要写比较函数。例如：比较函数是先比较一个点的x坐标，x坐标相等的情况下比较y坐标的大小。

struct Point { int x,y; }; Point points[1111]; bool cmp(Point a,Point b) { if(a.x!=b.x) { return a.x<b.x; } return a.y<b.y; }

也可以这么写：

struct Point { int x,y; }; Point points[1111]; bool operator<(Point a,Point b)//进行<的运算符重载 { if(a.x!=b.x) { return a.x<b.x; } return a.y<b.y; } int main() { sort(points,points+10); //进行<的运算符重载之后，就可以用小于号来比较两个结构体 //由于sort函数默认使用的是小于关系，所以sort使用的函数依据也可以省略不写 }

其他algorithm函数

//最大最小值O(1) min(1,2);max(1ll,2ll);//必须比较两个同类型的值，不然其会报错，比如必须都是int或者必须都是long long //数组最大最小指针O(n) min_element(arr.begin(),arr.end()); max_element(arr.begin(),arr.end()); //把数组中第n小（从0开始算）的数放到第n个位置 //类似快排，但是其只是进行部分排序，并且保证它左边的数比它小，右边的数比它大 //O(n) //比如{2,3,4,1,5}在n取1时，2会在2的位置上，左边的数都会比2小，右边的数都会比2大，其会变成{1,2,4,3,5} nth_elelment(arr.begin(),arr.begin()+n,arr.end()); //交换任意两个同类型变量 //O(1) swap(arr[0],arr[1]) //反转数组,比如结果是倒序的字符串要输出正确的顺序，可以直接用reverse O(n) reverse(arr.begin(),arr.end()); //假设arr已经被排好了序 //使arr中不出现重复的数字（去重） //返回去重后数组的结束指针 //O(n) //unique需要在sort之后使用 //unique大多数情况下是用于离散化的 //使用unique得到的结果是数组中有多少个非重复元素，并将重复元素剔除放到数组的后面（此时假设有n个元素，有m个非重复元素，则从第m+1个元素开始之后的元素都变得无效） int newLength=unique(arr.begin(),arr.end())-arr.begin(); //二分查找，查找对应元素是否存在 //O(logn) vector<int>arr{1,2,2,3}; bool isExist = binart_search(arr.begin(),arr.end(),1);//true //lower_bound一般被用来二分查找 //两个函数都是在做一件事 //如果把一个树插入有序数组，它应插到哪个位置 //lower_bound返回第一个插入位置的指针，upper_bound返回最后一个位置的指针 //O(logn) vector<int>arr{1,2,2,3}; int a=lower_bound(arr.begin(),arr.end(),2)-arr.begin();//则会插入到1 2之间，但是arr仍然是{1,2,2,3},不会变成{1,2,2,2,3},此时a是1，即如果插入会插入到arr[1]的位置 a=upper_bound(arr.begin(),arr.end(),2)-arr.begin();//插入到2和3之间，此时a是3

< set >

< map >

map是c++的一个标准容器，它提供了很好的一对一的关系，在一些程序中建立一个map可以起到事半功倍的效果。

map最基本的构造函数

map<string,int>mapstring; map<int,string>mapint; map<string,char>mapstring; map<char ,strinf>mapchar; map<char,int>mapchar; map<int,char>mapint;

map添加数据

map<int,string>maplive; maplive.insert(pair<int,string>(102,"alive")); maplive.insert(map<int,string>::value_type(321,"hai")); maplive[112]="April";//map中最简单最常用的插入添加 list的赋值：

1.通过构造函数：

其他标准库

STL大部分数据结构和vector一样，都会自带size()和empty()函数 1.< stack > · 先进后出，satck操作包括入、出、获取栈顶元素，复杂度是O(1) stack<int>sta;//定义 sta.push(1);//入 int topElement = sta.top();//获取栈顶元素 sta.pop();//出 sta.empty(); sta.size(); 2.< queue > ·< queue >包含queue和priority_queue（优先队列）两种数据结构，二者用法和stack完全相同 · 先进先出 queue<int>que; que.push(1); int frontElement =que.front(); que.pop();//出 que.empty(); que.size(); priority_queue<int>que2; que2.push(1); int minElement =que2.top(); que2.pop(); que2.empty(); que2.size(); 3.< set > · < set >包含set(集合)、multiset（多重集） · set用来保存很多很多元素，并能够在O(logn)的时间内查找、删除、添加某个元素 · 迭代器的++和–能够在O(logn)的事件里找到第一个比它大（小）的数 · set自带去重，而multiset允许元素重复，通过count可以获得某个元素的数量 · set是用某种平衡树实现的 set<int>st; st.insert(1); st.find(1); st.erase(1); multiset<int>mst; mst.insert(1); mst.insert(1); mst.count(1);//2,因为前面重复地插入了2个2 4.< map >（映射） · 把两个同类型或者不同类型的数据绑定在一起，比如下列小明和他的身高 pair<string,int> pr{"小明",180}; pair<int,int>point(1,2);//一个点的坐标

//map可以让任何数据当作数组的下标 pair<string,int>id; id=make_pair("somebody",110); map<string,int> studentHeight; studentHeight["小明"]=170; studentHeight["小红"]=150; studentHeight.insert(id); studentHeight.erase("小明"); //也可以用{A,B}初始话，例如： map<string,int>height { {"1",1},{"2",2} };

4.< bitset >位集合 bitset是一个只由0和1构成的数组，其占用空间小，bitset不仅可以和数组一样用下标访问，还可以及进行位运算

bitset<1000>bst; bst[0]=1;bst.set(0); bst[0]=0;bst.reset(0); bst<<1;bst>>1;bst^=1;bst&=1; bst.count();//1的个数 bst.to_string(); bst.to_ullong();

5.< functional >在ACM中只是配合priority_queue一起使用 6.< complex >C++中的复数类 7.< unordered_set > < unordered_map > 分别是< set >和< map >的另一种实现版本。这两种数据结构不允许按大小遍历元素，但能O(1)地访问和添加一个元素。 这两个数据是基于哈希的，对于每种对象都要提供一个计算哈希函数的方法。基础类型、标准库类型都自带了哈希函数，不用自己写，用起来和普通的set、map一样，但对自己定义的结构构建unordered_set , unordered_map时要额外提供一个哈希函数，有些题目会卡map的时间，但是用unordered_map就能过。

以上头文件都不需要记忆，只要

include<bits/stdc++.h>

就能包含所有C++标准头文件（除Visual Studio）。

STL的学习网站 利用编译器得到STL自动补全功能，有函数名猜测函数的用途，并实践出真知。