博客内容来自这里，优化了排版，减缩了内容。
可变数组 vector
数组加强版。
头文件：
#include <vector>
初始化：
#include <iostream>
#include <vector>
using namespace std;
int main()
{
// 几种初始化的方法
vector<int> a; // 定义一个vector 未初始化 输出》 0
vector<int> a(3); // 定义一个长度为3的vector 未初始化 输出》0 0 0
vector<int> a(10, 3); // 定义一个长度为10，且每个数赋值为3
// 将向量b中从下标0 1 2（共三个）的元素赋值给a，a的类型为int型
// 它的初始化不和数组一样
vector<int> a(b.begin(), b.begin + 3);
// 从数组中获得初值
int b[7] = {1, 2, 3, 4, 5, 6, 7};
vector<int> a(b,b+7）;
for(auto x : a)
{
// 遍历输出
cout << x << " ";
}
return 0;
}
函数
a.size(); // 返回元素个数
a.resize(); // 改变大小
a.empty(); // 判断a是否为空，空则返回true，非空则返回false
a.front(); // 返回a的第1个元素,当且仅当a存在a.back();//返回vector的最后一个数
a.clear(); // 清空a中的元素
a.pop_back(); // 删除a向量的最后一个元素a.push_back(5);//在a的最后一个向量后插入一个元素，其值为5
a.begin(); // vector的第0个数a.end();// vector的最后一个的数的后面一个数//通常与for循环结合使用
a.erase(p); // 从a中删除迭代器p指定的元素，p必须指向c中的一个真实元素，不能是最后一个元素end()
a.erase(b, e); // 从a中删除迭代器对b和e所表示的范围中的元素，返回evector<int>
a = {1, 2, 3, 4, 5};
reverse(a.begin(), a.end()); // a的值为5，4，3，2，1 倒置
支持比较运算
比较操作==，!=，<，<=，>，>=
int main()
{
// 支持比较运算
vector<int> a(4, 3), b(3, 4);
// a: 3 3 3 b:4 4 4
// 比较原理字典序 (根据最前面那个判断，如果一样就往后比较)
if (a < b)
{
puts("a < b");
}
return 0;
}
遍历
int main()
{
vector<int> a;
for (int i = 0; i < 10; i++)
{
a.push_back(i);
}
// 三种遍历vector的方法
for (int i = 0; i < a.size(); i++)
{
cout << a[i] << ' ';
}
cout << endl;
for (auto i = a.begin(); i != a.end(); i++)
{
cout << *i << ' ';
}
cout << endl;
// C++11的新语法
for (auto x : a)
{
cout << x << ' ';
}
cout << endl;
return 0;
}
坐标 pair
可以理解为（x,y）数学中的坐标表示
小技巧：使用typedef定义
typedef pair<int, int> PII
头文件
#include<utility>
初始化
使用：pair<first数据类型,second的数据类型>元素名。pair中只有两个元素，first和second。
//两种方法初始化
pair<string,int> p("hello",1);
p = make_pair("hello",1);
函数
p("hello", 1);
p.first; // 第一个元素 =hello
p.second; // 第二个元素 = 1
嵌套
vector<vector<pair<int, int>>>; // 与vector结合【再写个vector结合即可】
// 套娃操作 用pair存储3个数据
pair<int, pair<int, int>> p(1, {2, 3});
string
支持比较操作符>,>=,<,<=,==,!=
头文件
#include <string>
初始化
string a = "ac";
函数
-
substr()很有用,特别是求子串的时候
#include <iostream>
#include <string>
using namespace std;
int main()
{
string a = "ac";
a += "w"; // 支持比较操作符>,>=,<,<=,==,!=
cout << a << endl; // 输出子串a :acw
a += "ing";
cout << a << endl;
// 以字符串数组理解
cout << a.substr(0, 3) << endl; // 当第一个数是0 则后一位数:输出从头开始的长度为3的子串
cout << a.substr(0, 3) << endl; // 当第一个数是1 则输出下标为1 到下标为3的子串
cout << a.substr(0, 9) << endl; // 如果超出长度范围 则输出原子串
cout << a.substr(1) << endl; // 从下标为1开始输出
cout << a.substr(0) << endl; // 原子串
printf("%s\\n", a.c_str()); // 如果用printf输出
return 0;
}
c_str()
// 返回这个string对应的字符数组的头指针
string s = "Hello World!";
printf("%s", s.c_str()); //输出 "Hello World!"
push_back()和insert()
// 尾插一个字符
a.push_back('a');
// insert(pos,char):在制定的位置pos前插入字符char
a.insert(a.begin(), '1'); // 输出 1a
// 插入字符串
string str2 = "hello";
string s2 = "weakhaha";
str2.insert(0, s2, 1, 3); // 将字符串s2从下标为1的e开始数3个字符，分别是eak，插入原串的下标为0的字符h前
-
empty()判断
a是否为空，空则返回true，非空则返回false。 -
size()、length()都是返回字母个数
-
clear()把字符串清空。
队列和优先队列 queue和priority_queue
队列是一种数据结构原理：先进先出，元素从一端入队，从另一端出队，就像是排队。
优先队列和队列特性不同：按优先级排序和获取。
头文件
#include < queue >//都在这个头文件
初始化
// queue <类型> 变量名
// priority_queue <类型> 变量名;
queue<int> q; // 定义一个名为q队列
priority_queue<int> q; // 默认是大根堆
// 定义小根堆小根堆：priority_queue <类型,vecotr <类型>,greater <类型>> 变量名
函数
q.size(); // 这个队列的长度
q.empty(); // 用于判断这个队列是否为空，空则返回true，非空则返回false
q.push(); // 往队尾插入一个元素
q.pop(); // 队列：把队头弹出；优先队列 ：弹出堆顶元素
q.front(); // 返回队头元素
q.back(); // 返回队尾元素
q.top(); // 返回堆顶元素
q = queue<int>(); // 清空
栈 stack
头文件
#include <stack>
初始化
//stack<类型> 名字;
stack<int> s;
函数
s.size(); // 返回这个栈的长度
s.push(); // 向栈顶插入一个元素
s.top(); // 返回栈顶元素
s.pop(); // 弹出栈顶元素
双向队列 deque
头文件
#include <deque>
初始化
deque<int> dq;//定义一个int类型的双向队列
函数
dq.size(); // 返回这个双端队列的长度
dq.empty(); // 返回这个队列是否为空，空则返回true，非空则返回false
dq.clear(); // 清空这个双端队列
dq.front(); // 返回第一个元素
dq.back(); // 返回最后一个元素
dq.push_back(); // 向最后插入一个元素
dq.pop_back(); // 弹出最后一个元素
dq.push_front(); // 向队首插入一个元素
dq.pop_front(); // 弹出第一个元素
dq.begin(); // 双端队列的第0个数
dq.end(); // 双端队列的最后一个的数的后面一个数
集合 set
map和multiset集合与映射也是两个常用的容器,set类似于数学上的集合。
头文件
#include<set>
初始化
set<string> s;//string 集合
区别
set不允许元素重复，如果有重复就会被忽略，但multiset允许.
函数
s.size(); // 返回元素个数
s.empty(); // 返回set是否是空的
s.clear(); // 清空
s.begin(); // 第0个数，支持++或--，返回前驱和后继
s.end(); // 最后一个的数的后面一个数，支持++或--，返回前驱和后继
s.insert(); // 插入一个数
s.find(); // 查找一个数
s.count(); // 返回某一个数的个数
s.erase(x); // 删除所以x 时间复杂度 O(k + logn)
s.erase(s.begin(), s.end()); // 删除一个迭代器
s.lower_bound(x); // 返回大于等于x的最小的数的迭代器 核心操作
upper_bound(x); // 返回大于x的最小的数的迭代器 不存在返回end()
映射 map
map就是从键（key）到值（value）的映射。因为重载了[ ]运算符，map像是数组的“高级版”。例如可以用一个map<string，int>month_name来表示“月份名字到月份编号”的映射，然后用month_name[“July”]=7这样的方式来赋值。
头文件
#include <map>
初始化
这个初始化有点不同 还是小技巧搭配typedef简化
map<string,int> m = { "A", 10 };
函数
m.insert(); // 插入一个数，插入的数是一个pair
m.erase();
// （1）输入是pair
// （2）输入一个迭代器，删除这个迭代器
m.find(); // 查找一个数
m.lower_bound(x); // 返回大于等于x的最小的数的迭代器
m.upper_bound(x); // 返回大于x的最小的数的迭代器
映射
时间复杂度O(logn)
#include <iostream>
#include <string>
#include<map>
using namespace std;
int main()
{
map<string,int> a;
a["abc"] = 1;//把字符串"abc" 映射为1
cout << a["abc"] << endl; //查找abc 程序输出 1
return 0;
}
应用
#include <iostream>
#include <string>
#include <map>
using namespace std;
int main()
{
map<string, int> a;
a["abc"] = 1; // 把字符串"abc" 映射为1
cout << a["abc"] << endl; // 查找abc 程序输出 1
return 0;
}
哈希表 unordered
头文件
#include<unordered_set>
#include<unordered_map>
#include<unordered_muliset>
#include<unordered_multimap>
//头文件就是加上对应名称
优势
和上面map和set类似，增删改查的时间复杂度是O(1)
缺点
不支持lower_bound()和upper_bound()
压位 bitset
它是一种类似数组的结构，它的每一个元素只能是0或1，每个元素仅用1bit空间,用于节省空间， 并且可以直接用01串赋值，可以理解为一个二进制的数组
头文件
#include<bitset>
初始化
bitset<4> bs; // 无参构造，长度为４，默认每一位为０
bitset<8> b(12); // 长度为８，二进制保存，前面用０补充
string s = "100101"; // 01串赋值bitset<10>
bs(s); // 长度为10，前面用０补充
支持操作
~取反，&与，|与或，^异或 >>，<<移动==，!=
[]取0/1
函数
b.count(); // 返回1的个数
b.any(); // 判断是否至少有一个1
b.none(); // 判断是否全为0
b.set(); // 把所有位置赋值为1
b.set(k, v); // 将第k位变成v
b.reset(); // 把所有位变成0
b.flip(); // 把所有位取反，等价于~
b.flip(k); // 把第k位取反
算法库 Algorithm
头文件
#include<algorithm>
常用函数
sort()
【具有和快排一样的速度】时间复杂度O(n*logn)。
int a[5] = {4,2,1,3,5};
vector<int> b(a,a+5);
sort(a,a+5);//搭配数组 从小到大排序
sort(b.begin(),b.end());
__gcd()
最大公约数、最大公约数小题。
#include <cstdio>
#include <algorithm>
using namespace std;
int n, m;
int main()
{
scanf("%d %d", &n, &m);
int k = __gcd(n, m); // 最大公约数
printf("%d ", k);
printf("%d", n * m / k); // 最小公倍数
return 0;
}
max()、min()
max(a,b);//返回最大值
min(a,b);//返回最小值
swap()
swap(a,b);//交换a和b
-
lower_bound()与upper_bound()[二分查找]时间复杂度
O(log n),使用之前一定要先排序。 -
reverse()
ector<int> v={1,2,3,4,5};
reverse(v.begin(),v.end());//v的值为5，4，3，2，1 倒置
find()
//在a中的从a.begin()（包括它）到a.end()（不包括它）的元素中查找10，//若存在返回其在向量中的位置 find(a.begin(),a.end(),10);
erase()
//从c中删除迭代器p指定的元素，p必须指向c中的一个真实元素，不能等于c.end()
c.erase(p)
//从c中删除迭代器对b和e所表示的范围中的元素，返回e
c.erase(b,e)
语法小技巧
- 连续读取
while (cin >> a >> b) { ...}
- 加快
cin和cout的速度
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
- 万能头
缺点 耗时#include <bits/stdc++.h>
#define INF 0x3f3f3f3f; //无穷大 10^9 #define x first ;//结合pair#define y second;
exit(0)
-
头文件
#include <stdlib.h>
Debug技巧：使用exit(0)中断程序，如果没出现问题，则继续往下exit(0),直到发现问题，则Debug在附近通常用于调试无输出的程序
- 无穷大
0x3f3f3f3f的十进制为1061109567，和INT_MAX一个数量级，即109数量级，而一般场合下的数据都是小于109的。
0x3f3f3f3f * 2 = 2122219134，无穷大相加依然不会溢出。
可以使用memset(array, 0x3f, sizeof(array))来为数组设初值为0x3f3f3f3f，因为这个数的每个字节都是0x3f。
评论区