1 C++STL

摘要：在本文中，我们可以快速掌握关于C++基本语法以及STL库的常见函数，我们还会谈论ACM的一些比赛细节。

作者：来自ArimaMisaki创作

全文目录：

1.1 快速了解C++

1.1.1 基本概念

我们以最简单的一段代码为例开始讲解。

#include <iostream>
using namespace std;
int main(){
	cout << "hello world" <<endl;
	return 0;
}

• C++中用于输入输出的头文件为iostream，类似于C中大的stdio.h。在大部分编译器中会包含<stdio.h>文件。
• C语言的头文件在C++里全部可以使用，但是要把.h后缀去掉，在头文件前面加上c。
• C++中，用标准库的东西前面都要加上std::。但是如果加上using namespace std导入命名空间，则下面的代码无需加上std::，虽然这样便捷，但起名的时候容易和库函数起冲突。
• cout是C++中用于输出的对象，类似于C中的printf，所有标准数据类型都可以用cout输出。
• endl等于回车"\n"，但有些细节上的不同。这样写的可读性更好一点。

1.1.2 输出

#include <iostream>
using namespace std;
int main(){
	int a = 1;
	string b = "hello";
	cout << a << endl;
	cout << b << endl;
	cin.get();
	return 0;
}

• C++中输出使用cin，相当于C中的scanf，所有标准数据类型都可以用cin输入。

• >> 和<<代表输入流的方向。

• cin.getline(读取字符串,读取字符数)用于读取一行，但要加入读取的字符数上限。

1.1.3 输入输出流的使用细节

• 如果不是打ACM，则建议使用C++提供的输入输出。
• cin的速度比scanf慢不少，1e5以上的数据用cin读入就可能会TLE，此时建议用scanf。
• 输出小数用printf更方便一点，C++格式输出要用到<iomanip>头文件，用cout.setprecistion(int digit)来修改精度。
• 使用cin可以快速解决EOF问题，EOF是文件结束符的意思，我们都知道字符串本质是字符数组，如果使用scanf是没有自动结束功能的，但是cin可以帮我们做到这件事。

1.2 语法特性

1.2.1 新增的布尔类型

• C语言是没有布尔类型的，C++添加了新的基本数据类型bool，有true和false两个值。
• 逻辑中用true来代替非0，false来代替0能有效提高程序可读性。

1.2.2 动态开辟内存

int* number = new int;
int* arr = new int[100];
int* carr = (int*)malloc(100*sizeof(int));

• 与C中的malloc类似，C++中用new来动态开辟内存，new写起来更加简明一些。
• C++不支持变长数组。
• 平常写题的代码可以不用释放内存，但是自己手动释放是一个非常好的习惯。

1.2.3 引用

void swapInt(int&a, int&b){
	int c = a;
	a = b;
	b = c;
}

int main(){
	int a = 1,b =2;
	swapInt(a,b);
}

• C++中使用&来创建引用。可以把引用当成一个不能改变指向对象的指针，或者你可以说他是地址的别名。
• 引用多数情况在函数传参的时候才会用到，以简化指针的代码。

1.2.4 函数重载

int add(int a, int b){
	return a+b;
}
int add(int a){
	return a;
}
int minus(int a,int b = 0){
	return a-b;
}

int main(){
	add(0);
	add(0,0);
	minus(0);
	minus(0,0);
}

• C++中，函数是以函数名+参数列表来区分的，也就是说，两个函数可以名字相同，但参数列表和返回值不同。
• 函数的部分参数可以缺省，没有提供参数时用缺省值代替。
• 函数重载在dfs使用非常方便。

1.2.5 struct

struct node{
	int number;
	node* next;
};
//struct node* head;
node* head;

• 结构不用再和C语言一样在前面加一个struct，可以直接使用结构的名字。

struct node{
	int number;
	node* next;
	node(int _number = 0,node* _next = nullptr){
		number = _number;
		next = _next;
	}
};

int main(){
	node a = node(0);
    node* b = new node(1,&a);
}

• struct中可以加入与结构同名，无返回值的构造函数。在创建struct的时候会自动调用构造函数。
• 构造函数与缺省参数配合使用会让代码更简洁。

1.3 C++标准库

1.3.1 C语言的标准库

<cstring>

<cmath>

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

<cstdlib>

<ctime>

<cctype>

1.3.2 C++STL容器

1.3.2.1 vector向量

vector简介

vector<int> arr1(100);
vector<int> arr2;
vector<int> arr3 = {1,2,3,4,5};
vector<int> arr4{1,2,3,4,5};
int arr2[100];

vector<int> list;
list.push_back(1);

• vector可以看做一个超级数组，但它本质是个容器。
• vector即可以和C语言的数组一样用下标访问，也可以像链表一样动态改变长度。
• push_back()可以往vector的尾部塞入元素。
• size()可以返回vector的长度。

vector的遍历

• 通过for循环遍历。
• 通过增强for循环遍历。增强for循环的语法为for(遍历:容器){语句}。

迭代器

vector<int> arr1(100);
int arr2[100];

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也可以使用指针来访问遍历每一个元素。STL的指针被称为迭代器。

C++的迭代器需要指明类型，如需要访问整型向量的迭代器写作vector<int>::iterator p1;。

begin()是首元素迭代器，begin默认在容器的首元素的地址。end同理，默认在容器的尾元素的下一个地址。

vector基本操作

声明：vector<int> list;

1.3.2.2 string字符串

string简介

string str1 = "hello";
char str2[] = "world";
string str3;

str3.push_back('!');

cout << str1 << " " << str2 << str3 << endl;

• 字符串string可以看成一个特殊的vector。
• string和c语言字符串的关系就和vector和普通数组的关系一样。
• C++中的字符串可以很方便的拼接。
• vector有的操作string基本都有，唯一的区别就是size的复杂度。
• 所有参数为字符串的地方既可以是string也可以是C字符串。

string基本操作

声明：string str = “hello”

1.3.2.3 stack栈

stack<int> sta;
sta.push(1);
int topElement = sta.top();
sta.pop();
sta.empty();
sta.size();

• STL大部分数据结构和vector一样，都会自带size()和empty()函数
• stack操作包括入、出、获取栈顶元素，复杂度都是O(1)

1.3.2.4 queue队列

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();
que.size();

1.3.2.5 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

• set用于保存很多很多元素，能够在O(logn)的时间内查找、删除、添加某个元素
• 迭代器中的++和–能够在O(logn)的时间里找到第一个比它大（小）的数
• set自带去重，而multiset允许元素重复，通过count可以获得某个元素的数量
• set是用红黑平衡树实现的

1.3.2.6 map 映射

pair<int,int> origin;
origin = make_mair(0,0);
origin.first == origin.second;
origin.swap;

pair<string , int>id;
id = make_pair("somebody",110);

• <map>包含了数据结构pair数对。它可以由任意两种类型构成。
• 如果我们不像以pair<string,int>id这样的方式写出数据结构，则可以使用make_pair方法来构造一个数对并返回。
• pair自带了比较函数，默认先比第一个元素再比较第二个。

pair<string,int> id;
id = make_pair("somebody",110);

map<string,int> studentHeight;
studentHeight["小明"] = 170;
studentHeight["小红"] = 150;
studentHeight.insert(id);
studentHeight.erase("小明");

• <map>的第二个数据结构是map映射
• map可以看成一个超级数组，我们可以把字符串或者其他类型当成数组的下标
• 插入、查询、删除操作复杂度都是O(logn)
• map内部使用了pair，所以我们也可以通过insert一个pair来插入
• map可以使用大括号加大括号的方式初始化。

1.3.2.7 bitset 位集合

1.3.2.8 multiset哈希集合和multimap哈希表

<unordered_set>和<unordered_map>分别是<set>和<map>的另外一种实现版本，前者使用哈希函数，可以达到O(1)的随机存取，后者使用的是红黑二叉搜索树，存取速度为O(logn)。

有些毒瘤题目会卡map的时间，用unordered_map

1.3.3 Algorithm算法函数

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

1.3.3.1 sort快排

sort的基本使用

语法：sort(数组首元素地址,数位尾元素的下一位地址)

int arr[] {2,3,1,5,4};
int n = 5;

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

/*----------------*/

vector<int> arr;
arr.push_back(2);
arr.push_back(3);
arr.push_back(1);
sort(arr.begin(),arr.end());

for(int var : arr){
	cout << var << endl;
}

注：C++sort排序的复杂度是O(nlogn)

降序排列

bool cmpInt(int a, int b){
	return a>b;
}
vector<int> arr;
arr.push_back(2);
arr.push_back(3);
arr.push_back(1);
sort(arr.begin(),arr.end(),cmpInt);

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

结构体的排序

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;
}

int main(){
	sort(points,points +10,cmp);
}

• 如果是自己定义的结构体是需要自己写比较函数的。
• 如上述代码，比较函数先比较一个点的x坐标，x坐标相同的情况下比较y坐标。

1.3.3.2 其他的算法函数

1.4 注意事项须知

1.4.1 打比赛的技巧

如果不想记忆C++的所有库函数，我们可以使用以下语句：

#include <bits/stdc++.h>

它可以帮我们包含所有的头文件，Visual Studio用不了。

1.4.2 学习STL的正确姿势

使用Reference - C++ Reference (cplusplus.com)查看STL的正确用法。

使用编译器自动补全自己摸索细节。

1.4.3 其他算法竞赛的细节

1. 1s时限内能做的运算次数大约为1e8，根据复杂度来算是否会超时
2. C++输出double时不能用%lf，要用%f，不然会WA到哭
3. 注意多组用例时的EOF、初始化。初始化的常数时间也得估计好
4. 数据范围及运算结果均在1e9以内时，可以令const int INF = 0x3f3f3f3f表示无穷大值，并且可以用memset(arr,INF,sizeof(arr))来令数组初始化为无穷大。
5. 在使用循环时请尽量使用++i，而非i++，这样的速度会快一点点，有时候有些题就卡这么点时间。
6. 如果有一个函数经常被使用到，尽量将其保存为全局变量来使用而非经常去调用它，否则会比较耗时。

1.4.4 算法竞赛中常见的提示

• AC-Accepted 答案正确/通过

• WA-Wrong Answer 答案错误

• RE-Runtime Error 运行时错误

• CE-Complie Error 编译错误

• TLE-Time Limit Exceed 超出时间限制/超时

• MLE-Memory Limit Exceed 超出内存限制

• PE-Presentation Error 格式错误

• OLE-Output Limit Exceed 输出超出限制/输出超限)