为什么要学习c++？
在写很多题目时， 我们会用到很多的数据结构或者常规的一些方法，因为这些东西过于常用，但是对于c语言来说，支持的东西少之又少，而c++对于这些常用的东西进行了封装，从而使在使用的时候不必重复造“轮子”，所以c++的一些库函数和STL是有必要学习的
vector变长数组
vector是变长数组，支持随机访问，不支持在任意位置 O(1）插入。为了保证效率，元素的增删一般应该在末尾进行。
using namespace std;
int main ()
{
/*
用法于普通数组一致
a.push_back(x)把元素x插入到vector a的尾部。
b.pop_back()删除vector a的最后一个元素
size表示vector现在存在的空间
clear清空数组，恢复到v1声明状态
begin/end:
begin函数返回指向vector中第一个元素的迭代器。例如a是一个非空的vector，则*a.begin()与a[0]的作用相同。
所有的容器都可以视作一个“前闭后开”的结构，end函数返回vector的尾部，即第n 个元素再往后的“边界”。
*a.end()与a[n]都是越界访问，其中n = a.size()。
*/
vector<int> v1; //声明了一个容器
vector<int> v2(10, 0); //声明了一个容器并开辟10个空间，每个空间数字是0
// v1[2] ++;//错误因为现在vector里面没有空间，相当于一个大小为0的数组
v2[2] ++;//正确，已经开辟了10个空间
cout << v1.size() << " " << v2.size() << endl;
for(int i = 0; i < 10; i ++) v1.push_back(1); //相当于开辟一个元素并赋值
cout << v1.size() << endl;
v1.pop_back(); //收回一个空间
cout << v1.size() << endl;
//这里给出三种遍历方式
// for (int i = 0; i < v1.size(); i ++)
// cout << v1[i] << endl;
for (vector<int>::iterator it = v1.begin(); it != v1.end(); it ++)
cout << *it << endl;
for(auto x : v1) cout << x << endl;
return 0;
}
pair<int, int>
/*
first, 第一个元素
second, 第二个元素
支持比较运算，以first为第一关键字，以second为第二关键字（字典序）
*/
using namespace std;
int main()
{
pair<int, int> p[11];
for(int i = 10; i >= 0; i --) p[10 - i] = {i, 1};
sort(p, p + 11);
for(int i = 0; i <= 10; i ++) cout << p[i].first << " " << p[i].second << endl;
return 0;
}
queue/priority_queue
/*
queue, 队列
顾名思义：就是一个遵循先进先出的一种数据结构
size()
empty()
push() 向队尾插入一个元素
front() 返回队头元素
back() 返回队尾元素
pop() 弹出队头元素
由于于queue高度类似，不进行代码展示，可自我尝试
priority_queue, 优先队列，默认是大根堆
priority_queue<int> q;
维护一个有序的序列
size()
empty()
push() 插入一个元素
top() 返回堆顶元素
pop() 弹出堆顶元素
定义成小根堆的方式：priority_queue<int, vector<int>, greater<int>> q;
*/
using namespace std;
int main()
{
queue<int> q;
for(int i = 0; i < 10; i ++) q.push(i);
cout << q.back() << endl;
//遍历队列
while(!q.empty())
{
cout << q.front() << " ";
q.pop();
}
}
stack/deque
于上面queue类似，参考以上自己实现其相关功能
stack, 栈
size()
empty()
push() 向栈顶插入一个元素
top() 返回栈顶元素
pop() 弹出栈顶元素
deque, 双端队列
size()
empty()
clear()
front()/back()
push_back()/pop_back()
push_front()/pop_front()
begin()/end()
[]
哈希表与红黑树
set[[]
map[[]
set, map, multiset, multimap, 基于平衡二叉树（红黑树），动态维护有序序列
size()
empty()
clear()
begin()/end()
++, -- 返回前驱和后继，时间复杂度 O(logn)
set/multiset
insert() 插入一个数
find() 查找一个数
count() 返回某一个数的个数
erase()
(1) 输入是一个数x，删除所有x O(k + logn)
(2) 输入一个迭代器，删除这个迭代器
lower_bound()/upper_bound()
lower_bound(x) 返回大于等于x的最小的数的迭代器
upper_bound(x) 返回大于x的最小的数的迭代器
map/multimap
insert() 插入的数是一个pair
erase() 输入的参数是pair或者迭代器
find()
[] 注意multimap不支持此操作。 时间复杂度是 O(logn)
lower_bound()/upper_bound()
unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表
和上面类似，增删改查的时间复杂度是 O(1)
不支持 lower_bound()/upper_bound()， 迭代器的++，--
库函数
reverse
翻转vector
reverse(a.begin(), a.end());
翻转一个数组，元素存放在下标1 ~ n：
reverse(a + 1, a + n + 1);
unique
返回去重（只去掉相邻的相同元素）之后的尾迭代器（或指针），仍然为前闭后开，即这个迭代器是去重之后末尾元素的下一个位置。该函数常用于离散化，利用迭代器（或指针）的减法，可计算出去重后的元素个数。
把一个vector去重：
int m = unique(a.begin(), a.end()) – a.begin();
把一个数组去重，元素存放在下标1 ~ n：
int m = unique(a + 1, a + n + 1) – (a + 1);
sort
对两个迭代器（或指针）指定的部分进行快速排序。可以在第三个参数传入定义大小比较的函数，或者重载“小于号”运算符。
把一个int数组（元素存放在下标1 ~ n）从大到小排序，传入比较函数：
int a[MAX_SIZE];
bool cmp(int a, int b)
{
return a > b;
}
sort(a + 1, a + n + 1, cmp);
把自定义的结构体vector排序，重载“小于号”运算符：
struct Rec
{
int id, x, y;
};
vector<Rec> a;
bool operator <(const Rec &a, const Rec &b)
{
return a.x < b.x || a.x == b.x && a.y < b.y;
}
sort(a.begin(), a.end());
lower_bound/upper_bound
lower_bound的第三个参数传入一个元素x，在两个迭代器（指针）指定的部分上执行二分查找，返回指向第一个大于等于x的元素的位置的迭代器（指针）。
upper_bound的用法和lower_bound大致相同，唯一的区别是查找第一个大于x的元素。当然，两个迭代器（指针）指定的部分应该是提前排好序的。
在有序int数组（元素存放在下标1 ~ n）中查找大于等于x的最小整数的下标：
int i = lower_bound(a + 1, a + 1 + n, x) - a;
在有序vector<int>中查找小于等于x的最大整数（假设一定存在）：
int y = *--upper_bound(a.begin(), a.end(), x);
题目
题目过于难找，但是是很多题目基础，故本次无题目，搞懂基本操作即可