一幅长文细学算法（一）——C++STL
【摘要】
1 C++STL
摘要：在本文中，我们可以快速掌握关于C++基本语法以及STL库的常见函数，我们还会谈论ACM的一些比赛细节。
作者：来自ArimaMisaki创作
全文目录：
...
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;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 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;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
-
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));
- 1
- 2
- 3
- 与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);
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 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);
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- C++中，函数是以函数名+参数列表来区分的，也就是说，两个函数可以名字相同，但参数列表和返回值不同。
- 函数的部分参数可以缺省，没有提供参数时用缺省值代替。
- 函数重载在dfs使用非常方便。
1.2.5 struct
struct node{
int number;
node* next;
};
//struct node* head;
node* head;
- 1
- 2
- 3
- 4
- 5
- 6
- 结构不用再和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);
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- struct中可以加入与结构同名，无返回值的构造函数。在创建struct的时候会自动调用构造函数。
- 构造函数与缺省参数配合使用会让代码更简洁。
1.3 C++标准库
1.3.1 C语言的标准库
<cstring>
| 函数 | 说明 |
|---|---|
| strlen() | 字符串长度 |
| strcmp() | 字符串比较 |
| strcpy() | 字符串拷贝 |
| memset() | 暴力清空 |
| memcpy() | 暴力拷贝 |
<cmath>
三角函数、指数函数、浮点取整函数
<cstdlib>
| 函数 | 说明 |
|---|---|
| qsort() | C语言快排，调用复杂一般不用而使用C++的排序 |
| rand() | 随机数 |
| malloc() | 申请内存 |
| free() | 释放内存 |
<ctime>
| 函数 | 说明 |
|---|---|
| time(0) | 从1970年到现在的描述，常配合随机数用于初始化 |
| clock() | 程序启动到目前为止的毫秒数 |
<cctype>
| 函数 | 说明 |
|---|---|
| isdigit() | 判断字符是否为数字 |
| isalpha() | 判断大小写字母 |
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);
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 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;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
与普通的数组类似，vector也可以使用指针来访问遍历每一个元素。STL的指针被称为迭代器。
C++的迭代器需要指明类型，如需要访问整型向量的迭代器写作vector<int>::iterator p1;。
begin()是首元素迭代器，begin默认在容器的首元素的地址。end同理，默认在容器的尾元素的下一个地址。
vector基本操作
声明：vector<int> list;
| 函数 | 说明 |
|---|---|
| list.size() | 数组元素个数，复杂度O(1) |
| list.clear() | 一键清空数组，而非删除数组，复杂度O(n) |
| list.empty() | 判空，复杂度O(1) |
| list.begin() | 首元素迭代器，复杂度O(1) |
| list.end() | 尾元素的下一位元素的迭代器，复杂度O(1) |
| list.erase() | 删除数组某个迭代器所在位置的数字，复杂度O(n) |
| list.push_back() | 往数组后添加元素，复杂度O(1) |
| list.pop_back() | 删除数组最后一个元素，复杂度O(1) |
1.3.2.2 string字符串
string简介
string str1 = "hello";
char str2[] = "world";
string str3;
str3.push_back('!');
cout << str1 << " " << str2 << str3 << endl;
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 字符串string可以看成一个特殊的vector。
- string和c语言字符串的关系就和vector和普通数组的关系一样。
- C++中的字符串可以很方便的拼接。
- vector有的操作string基本都有，唯一的区别就是size的复杂度。
- 所有参数为字符串的地方既可以是string也可以是C字符串。
string基本操作
声明：string str = “hello”
| 函数 | 说明 |
|---|---|
| str.length() | 等同于str.size()，复杂度O(n) |
| str.insert(1,“a”) | 在下标为1处插入字符或字符串，复杂度O(1) |
| str.insert(str.begin,‘a’) | 在迭代器处插入一个字符，复杂度O(n) |
| str.c_str() | 返回C语言风格的字符串，复杂度O(n) |
| str.append(str2) | 把str2拼接到str后面，复杂度O(n) |
| str.compare(str2) | 比较字符串 |
| str += str2 | 相当于拼接 |
| str += ‘a’ | 相当于push_back |
1.3.2.3 stack栈
stack<int> sta;
sta.push(1);
int topElement = sta.top();
sta.pop();
sta.empty();
sta.size();
- 1
- 2
- 3
- 4
- 5
- 6
- 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
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
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
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 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);
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- <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("小明");
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- <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;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
注：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);
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 和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);
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 如果是自己定义的结构体是需要自己写比较函数的。
- 如上述代码，比较函数先比较一个点的x坐标，x坐标相同的情况下比较y坐标。
1.3.3.2 其他的算法函数
| 函数 | 说明 |
|---|---|
| max(1,2) | 返回最大值，复杂度为O(1) |
| min(1,2) | 返回最小值，复杂度为O(1) |
| min_element(arr.begin(),arr.end()) | 数组最大指针，复杂度为O(n) |
| max_element(arr.begin(),arr.end()) | 数组最小指针，复杂度为O(n) |
| nth_element(arr.begin(),arr.begin()+n,arr.end()) | 查看排好序后的第n个位置里面的数据，复杂度为O(n) |
| swap(arr[0],arr[1]) | 用于交换两个数据，复杂度为O(1) |
| reverse(arr.begin(),arr.end()) | 用于反转数组，复杂度为O(n) |
| unique(arr.begin(),arr.end()) | 大多数用于离散化的情况，能使得数组的前面部分变得独一无二，重复的数据放于数组的后面部分。复杂度为O(n) |
| binary_search(arr.begin(),arr.end(),1) | 在排好序的数组中进行二分查找，搜索对应元素是否存在，返回布尔值。时间复杂度为O(logn) |
| lower_bound(arr.begin(),arr.end(),2) | 在排好序的数组中返回第一个大于等于你所给定的值的位置。时间复杂度为O(logn) |
| upper_bound(arr.begin(),arr.end(),2) | 在排好序的数组中返回第一个大于你所给定的值的位置。时间复杂度为O(logn) |
1.4 注意事项须知
1.4.1 打比赛的技巧
如果不想记忆C++的所有库函数，我们可以使用以下语句：
#include <bits/stdc++.h>
- 1
它可以帮我们包含所有的头文件，Visual Studio用不了。
1.4.2 学习STL的正确姿势
使用Reference - C++ Reference (cplusplus.com)查看STL的正确用法。
使用编译器自动补全自己摸索细节。
1.4.3 其他算法竞赛的细节
- 1s时限内能做的运算次数大约为1e8，根据复杂度来算是否会超时
- C++输出double时不能用%lf，要用%f，不然会WA到哭
- 注意多组用例时的EOF、初始化。初始化的常数时间也得估计好
- 数据范围及运算结果均在1e9以内时，可以令const int INF = 0x3f3f3f3f表示无穷大值，并且可以用memset(arr,INF,sizeof(arr))来令数组初始化为无穷大。
- 在使用循环时请尽量使用++i，而非i++，这样的速度会快一点点，有时候有些题就卡这么点时间。
- 如果有一个函数经常被使用到，尽量将其保存为全局变量来使用而非经常去调用它，否则会比较耗时。
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 输出超出限制/输出超限)
文章来源: blog.csdn.net，作者：ArimaMisaki，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/chengyuhaomei520/article/details/126606400
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）