STL
Vector
Vector 是一种序列容器，允许在运行时动态地插入和删除元素。使用时需要包含
<vector>头文件。
size返回 vector 的实际长度，empty函数返回一个 bool 类型，表明 vector 是否为空。- 二者的时间复杂度都是 O(1)。所有的 STL 容器都支持这两个方法。
- 迭代器就像 STL 容器的指针，可以用
*操作符解除引用。 - Vector 的迭代器是'随机访问迭代器'，可以把 vector 的迭代器与一个整数相加减，其行为和指针的移动类似。可以把 vector 的两个迭代器相减，其结果也和指针相减类似，得到两个迭代器对应下标之间的距离。
begin()函数返回指向 vector 中的第一个元素的迭代器。end()函数返回 vector 的尾部，就是最后一个元素的下一个。front()表示返回 vector 的第一个元素。back()表示返回 vector 的最后一个元素。push_back(x)表示在 vector 的末尾插入元素 x。pop_back()表示删除 vector 的末尾元素。
Vector 实例
#include <iostream>
#include <vector>
using namespace std;
int main() {
// 创建 vector a
vector<int> a;
// 添加元素
a.push_back(1);
a.push_back(2);
a.push_back(3);
a.push_back(4);
a.push_back(5);
// 获取 vector a 的长度并判断是否非空
int len = a.size();
bool is_empty = a.empty();
cout << len << " " << is_empty << endl;
// 返回第一个和最后一个元素
int first = a.front();
int last = a.back();
cout << first << " " << last << endl;
// 删除最后一个元素
a.pop_back();
// 删除指定的某个元素-----删除第三个元素
a.erase(a.begin() + 2);
// 更新第一个和最后一个元素
first = a.front();
last = a.back();
cout << first << " " << last << endl;
// 使用迭代器遍历 vector----输出 vector a 中的所有元素
for (vector<int>::iterator it = a.begin(); it != a.end(); it++) {
cout << *it << endl;
}
// 通过下标访问元素
cout << a[2] << endl;
// 清空所有元素
a.clear();
// 获取 vector a 的长度并判断是否非空
len = a.size();
is_empty = a.empty();
cout << len << " " << is_empty << endl;
return 0;
}
Vector 声明
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> a; // 一个长度是动态变化的 int 数组
vector<int> b[233]; // 第一维长度是 233，第二维是动态变化的 int 数组
return 0;
}
Queue
使用时需要包含
<queue>头文件。Queue 主要包括循环队列 queue 和优先队列 priority_queue 两个容器。遵循元素在队首添加，队尾移出的规则。
优先队列 Priority_Queue
实例
#include <iostream>
#include <queue>
using namespace std;
int main() {
// 创建优先队列
priority_queue<int> q;
// 添加元素
q.push(1);
q.push(2);
q.push(3);
q.push(4);
q.push(5);
// 创建一个临时队列 m------默认是最大堆（也就是升序排列）
priority_queue<int> m = q;
while (!m.empty()) {
cout << m.top() << endl;
m.pop();
}
// 删除队首元素
q.pop();
q.pop();
// 输出 q 队列元素
while (!q.empty()) {
cout << q.top() << endl;
q.pop();
}
return 0;
}
常用函数
top函数：返回队列顶部的元素（并不删除）。pop函数：移除队列顶部的元素。push函数：向队列中添加一个元素。
循环队列 Queue
实例
#include <iostream>
#include <queue>
using namespace std;
int main() {
// 创建 queue
queue<int> q;
// 添加元素
q.push(1);
q.push(2);
q.push(3);
q.push(4);
// 创建一个临时队列 m
queue<int> m = q;
// 遍历所有元素
while (!m.empty()) {
// 如果队列不为空，则输出队首元素
cout << m.front() << endl;
// 输出之后弹出队首元素
m.pop();
}
// 输出 q 队列的队首和队尾元素
cout << q.front() << endl;
cout << q.back() << endl;
// 输出 q 队列的长度
cout << q.size() << endl;
return 0;
}
常用函数
back函数：返回队尾元素。front函数：返回队首元素。pop函数：移除队首元素。push函数：在队尾添加一个元素。
声明
#include <iostream>
#include <queue>
using namespace std;
int main() {
queue<int> q;
priority_queue<int> a; // 大根堆
priority_queue<int, vector<int>, greater<int>> b; // 小根堆
priority_queue<pair<int, int>> c;
return 0;
}
Stack
使用时需要包含
<stack>头文件。
实例
#include <iostream>
#include <stack>
using namespace std;
int main() {
// 创建 stack
stack<int> s;
// 栈顶添加元素
s.push(1);
s.push(2);
s.push(3);
s.push(4);
// 遍历元素
stack<int> t = s;
while (!t.empty()) {
cout << t.top() << endl;
t.pop();
}
// 删除 s 的栈顶元素
s.pop();
s.pop();
// 删除 s 中的元素
while (!s.empty()) {
cout << s.top() << endl;
s.pop();
}
return 0;
}
常用函数
top函数：返回栈顶元素，但不删除。pop函数：移除栈顶元素。push函数：在栈顶添加一个元素。
Deque
实例
#include <iostream>
#include <deque>
using namespace std;
int main() {
// 创建队列
deque<int> q;
// 添加元素
q.push_front(1);
q.push_back(2);
q.push_front(3);
q.push_back(4);
int len = q.size();
bool is_empty = q.empty();
cout << len << " " << is_empty << endl;
// 遍历所有元素
for (deque<int>::iterator it = q.begin(); it != q.end(); it++) {
cout << *it << endl;
}
// 删除元素
q.pop_back();
q.pop_front();
len = q.size();
is_empty = q.empty();
cout << len << " " << is_empty << endl;
// 遍历所有元素
for (deque<int>::iterator it = q.begin(); it != q.end(); it++) {
cout << *it << endl;
}
// 清空
q.clear();
len = q.size();
is_empty = q.empty();
cout << len << " " << is_empty << endl;
return 0;
}
常用函数
clear函数：清空队列。pop_front和pop_back函数：从队头出队，从队尾出队。push_front和push_back函数：从队头入队，从队尾入队。front和back函数：返回队头和队尾元素。begin和end函数：返回 deque 的头为迭代器。
声明
#include <iostream>
#include <deque>
using namespace std;
int main() {
deque<int> q;
return 0;
}
Set
使用时需要包含
<set>头文件。
size()用来获取容器的长度。empty()用来判断容器是否非空。clear()用来清空容器元素。- Set 和 multiset 的迭代器称为'双向访问迭代器'，不支持'随机访问'，支持星号
*解除引用，仅支持++和--两个与算术相关的操作。 - 设
it是一个迭代器，例如set<int>::iterator it;。 - 若把
it++，则it会指向'下一个'元素。这里的'下一个'元素是指在元素从小到大排序的结果中，排在it下一名的元素。同理，若把it--，则it将会指向排在'上一个'的元素。 - 返回首、尾迭代器，时间复杂度均为 O(1)。
s.begin()是指向集合中最小元素的迭代器。s.end()是指向集合中最大元素的下一个位置的迭代器。s.insert(x)把一个元素 x 插入到集合 s 中，时间复杂度为 O(logn)。- 在 set 中，若元素已存在，则不会重复插入该元素，对集合的状态无影响。
- 这两个函数的用法与 find 类似，但查找的条件略有不同，时间复杂度为 O(logn)。
s.lower_bound(x)查找大于等于 x 的元素中最小的一个，并返回指向该元素的迭代器。s.upper_bound(x)查找大于 x 的元素中最小的一个，并返回指向该元素的迭代器。- 设
it是一个迭代器，s.erase(it)从 s 中删除迭代器 it 指向的元素，时间复杂度为 O(logn)。 - 设 x 是一个元素，
s.erase(x)从 s 中删除所有等于 x 的元素，时间复杂度为 O(k+logn)，其中 k 是被删除的元素个数。
实例
#include <iostream>
#include <set>
using namespace std;
int main() {
// 创建实例
set<int> s;
// 添加元素
s.insert(1);
s.insert(2);
s.insert(3);
s.insert(4);
s.insert(5);
// 获取长度并判断是否非空
int len = s.size();
bool is_empty = s.empty();
cout << len << " " << is_empty << endl;
// 遍历元素 (输出)
for (set<int>::iterator it = s.begin(); it != s.end(); it++) {
cout << *it << endl;
}
// 删除元素
s.erase(3);
len = s.size();
is_empty = s.empty();
cout << len << " " << is_empty << endl;
// 遍历元素 (输出)
for (set<int>::iterator it = s.begin(); it != s.end(); it++) {
cout << *it << endl;
}
// 查找元素 2
if (s.find(2) != s.end()) {
cout << "2 is yes" << endl;
} else {
cout << "2 is no" << endl;
}
// 输出出现的次数
int count = s.count(0);
cout << count << endl;
return 0;
}
常用函数
count函数：返回集合 s 中等于 x 的元素个数，时间复杂度为 O(k+logn)，其中 k 为元素 x 的个数。erase函数：删除元素。lower_bound和upper_bound函数：二分查找边界。find函数：在集合 s 中查找等于 x 的元素，并返回指向该元素的迭代器。若不存在，则返回 s.end()。时间复杂度为 O(logn)。insert函数：插入元素。begin和end函数：返回首尾迭代器。size、empty、clear函数：基本容器操作。
声明
#include <iostream>
#include <set>
using namespace std;
int main() {
set<int> s;
return 0;
}
Map
使用时需要包含
<map>头文件。
实例
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main() {
// 创建一个 map 容器，存储员工的姓名和年龄
map<string, int> employees;
// 插入员工信息
employees.insert(make_pair("Alice", 30));
employees.insert(make_pair("Bob", 25));
employees.insert(make_pair("Charlie", 35));
// 遍历 map 并打印员工信息
for (map<string, int>::iterator it = employees.begin(); it != employees.end(); ++it) {
// it->first 是键，it->second 是值
cout << it->first << ":" << it->second << endl;
}
// 获取长度并判断是否非空
int len = employees.size();
bool is_empty = employees.empty();
cout << len << " " << is_empty << endl;
// 查找键值
map<string, int>::iterator it = employees.find("Bob");
if (it != employees.end()) {
if (it->second == 25) {
cout << "Bob: 25 is yes" << endl;
} else {
cout << "Bob: 25 is no" << endl;
}
} else {
cout << "Bob: 25 is no" << endl;
}
// 清空
employees.clear();
len = employees.size();
is_empty = employees.empty();
cout << len << " " << is_empty << endl;
return 0;
}
常用函数
find函数：在变量名为 h 的 map 中查找 key 为 x 的二元组。insert和erase函数：与 set 类似，但其参数均是 pair<key_type, value_type>。size、empty、clear、begin、end函数：和 set 类似。
声明
Map 容器是一个键值对 key-value 的映射，其内部实现是一棵以 key 为关键码的红黑树。Map 的 key 和 value 可以是任意类型，其中 key 必须定义小于号运算符。
#include <iostream>
#include <map>
using namespace std;
int main() {
map<long long, bool> vis;
return 0;
}
位运算
位运算符号
| 符号 | 含义 |
|---|---|
| & | 与 |
| | | 或 |
| ~ | 非 |
| ^ | 异或 |
| >> | 右移 |
| << | 左移 |
常见操作
Lowbit(x) = x & -x，返回 x 的最后一位 1
#include <iostream>
#include <string>
using namespace std;
int main() {
int num;
cin >> num;
int lowbit = num & -num;
cout << lowbit << endl;
return 0;
}
求 x 的第 k 位数字 x >> k & 1
#include <iostream>
#include <string>
using namespace std;
int main() {
int num;
cin >> num;
int k;
cin >> k;
cout << ((num >> k) & 1) << endl;
return 0;
}
常用库函数
Reverse 函数
将元素进行翻转。例子：翻转数组和 vector。
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
int a[10] = {1, 2, 3, 4, 5, 6, 5, 4, 3, 2};
for (int i = 0; i < 10; i++) {
cout << a[i] << endl;
}
cout << endl;
// 翻转数组
reverse(a, a + 10);
for (int i = 0; i < 10; i++) {
cout << a[i] << endl;
}
cout << endl;
vector<int> q;
// 添加元素
q.push_back(1);
q.push_back(2);
q.push_back(3);
q.push_back(4);
// 输出
for (vector<int>::iterator it = q.begin(); it != q.end(); it++) {
cout << *it << endl;
}
cout << endl;
// 翻转 vector q
reverse(q.begin(), q.end());
// 输出
for (vector<int>::iterator it = q.begin(); it != q.end(); it++) {
cout << *it << endl;
}
return 0;
}
Unique 函数
返回去重（只去掉相邻的相同元素）之后的尾迭代器（或指针），仍然为前闭后开，即这个迭代器是去重之后末尾元素的下一个位置。该函数常用于离散化，利用迭代器（或指针）的减法，可计算出去重后的元素个数。
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
vector<int> q;
// 添加元素
q.push_back(1);
q.push_back(2);
q.push_back(2);
q.push_back(2);
q.push_back(3);
q.push_back(3);
q.push_back(4);
// 输出
for (vector<int>::iterator it = q.begin(); it != q.end(); it++) {
cout << *it << endl;
}
cout << endl;
// 去重 vector q
vector<int>::iterator new_end = unique(q.begin(), q.end());
q.erase(new_end, q.end());
// 输出不重复元素的数量
int m = q.size();
cout << "Number of unique elements: " << m << endl;
// 去重后的元素
cout << "After removing duplicates: ";
for (vector<int>::iterator it = q.begin(); it != q.end(); it++) {
cout << *it << " ";
}
cout << endl;
return 0;
}
Random_Shuffle 函数
用法与 reverse 相同。随机打乱。
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
vector<int> a;
// 添加元素
a.push_back(1);
a.push_back(2);
a.push_back(3);
a.push_back(4);
a.push_back(5);
// 输出
for (vector<int>::iterator it = a.begin(); it != a.end(); it++) {
cout << *it << endl;
}
cout << endl;
// 随机打乱
random_shuffle(a.begin(), a.end());
// 输出
for (vector<int>::iterator it = a.begin(); it != a.end(); it++) {
cout << *it << endl;
}
return 0;
}
Sort 函数
对两个迭代器（或指针）指定的部分进行快速排序。默认是升序排列。
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int a[10] = {1, 2, 3, 2, 1, 4, 3, 2, 1, 10};
// 默认是升序排列
sort(a, a + 10);
for (int i = 0; i < 10; i++) {
cout << a[i] << endl;
}
cout << endl;
// 这种是降序排列
sort(a, a + 10, greater<int>());
for (int i = 0; i < 10; i++) {
cout << a[i] << endl;
}
return 0;
}
Lower_Bound/Upper_Bound 函数
lower_bound的第三个参数传入一个元素 x，在两个迭代器（指针）指定的部分上执行二分查找，返回指向第一个大于等于 x 的元素的位置的迭代器（指针）。upper_bound的用法和 lower_bound 大致相同，唯一的区别是查找第一个大于 x 的元素。当然，两个迭代器（指针）指定的部分应该是提前排好序的。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int a[10] = {1, 3, 5, 7, 9, 2, 4, 6, 8, 10};
// 排序
sort(a, a + 10);
// 在已排序的数组中找到>=5 的最小整数的下标
int i = lower_bound(a, a + 10, 5) - a;
cout << i << endl;
// 在已排序的数组中找到>5 的最小整数的下标
int j = upper_bound(a, a + 10, 5) - a;
cout << j << endl;
return 0;
}