STL
vector 动态数组
<vector>
vector <int> v; // 定义
vector <int> :: iterator it; // 定义迭代器
v.push_back(x); // 在数组末尾插入新元素
v.pop_back(); // 在数组末尾弹出新元素
v.front(); // 返回头部元素
v.back(); // 返回尾部元素
v.begin(); // 返回首位元素的迭代器
v.end(); // 返回末尾元素的迭代器
v.size(); // 返回数组内元素个数
v.empty(); // 判断是否为空
v.clear(); // 清空
for (auto x : d) { // d数组的值不改变
x ++;
}
for (auto &x : d) { // d数组的值改变
x ++;
}
queue 队列
<queue>
queue <int> q; // 定义
q.push(x); // 在队尾插入元素 O(1)
q.pop(); // 在队首弹出元素O(1)
q.front(); // 返回队首元素
q.back(); // 返回队尾元素
q.size(); // 返回队列内元素个数
q.empty(); // 判断是否为空
priority_queue 优先队列(堆)
<queue>
priority_queue <int> q; // 大根堆 数字大的优先级高
priority_queue <int, vector <int>, greater <int> > q; // 小根堆
或 通过大根堆进行两次取反
基本函数同queue
q.push(); // O(logn)
q.pop(); // O(logn)
q.top() // 堆顶元素
struct node { // 重载运算符
int l, r;
bool operator < (const node &b) const {
if (l == b.l) return r < b.r;
else l < b.l;
}
}
priority_queue <node> q;
q.push((node){x, y}); // 插入元素
node now = q.top(); // 堆顶元素
int xx = now.x, yy = now.y; // 取单个元素
// 排序
node a[] = {(node){4, 7}, (node){1, 3}, (node){2, 3}, (node){1, 5}};
sort(a, a + 4);
deque 双端队列
<deque>
deque <int> d; // 定义
d.begin(); d.end(); // 返回队首队尾元素的迭代器
d.front(); d.back(); // 返回队首队尾元素
d.push_front(); d.push_back(); // 分别向队首 队尾插入元素
d.pop_front(); d.pop_back(); // 分别删除队首 队尾的元素
d.clear(); // 清空队列
stack 栈
<stack>
stack <int> st; // 定义
st.push(x); // 栈顶插入元素
st.pop(); // 栈顶弹出元素
st.top(); // 返回栈顶元素
st.size(); // 返回栈的大小
st.empty(); // 判断是否为空
string 字符串
<string>
string s; // 定义
s.length(); s.size(); // 返回字符串长度
set 集合
有序性 不可重复性
<set>
set <int> s; // 定义
s.insert(x); // 插入元素 O(logn)
s.erase(x); // 删除x元素 O(logn)
s.begin(); s.end(); // 返回首尾的迭代器
s.size(); // 返回集合大小
s.empty(); // 判空
s.clear(); // 清空
s.find(); // 返回集合内元素x的迭代器
s.lower_bound(x); s.upper_bound(x); // 分别返回集合中大于等于和大于x的第一个元素
multiset 可重集合
有序性 可重复性
<set>
multiset <int> s; // 定义
s.erase(x); // 删除集合内所有值为x的元素
s.erase(it); // 删除迭代器为it的元素
s.count(x); // 返回值为x的元素个数
if ((it == s.find(a)) != s.end()) s.erase(it); // 删除一个元素
bitset 二进制数
<bitset>
bitset <100000> b; // 定义 二进制数的长度
b.count(); // 返回1的个数
b.any(); b.none; // 若至少有一位为1 前者为1 后者为0
b.set(); // 全部置为1
b.reset(); // 全部置为0
b.set(x, y); // 把第x个数字变为y
b.reset(x); // 把第x个数字变为0
b.flip(); // 全部按位取反
b.flip(x); // 把第x个数字取反
b[x] = true; // 赋值
同时支持基本的位运算符号的直接应用，如b <<= 1;
map 映射
<map>
map <string, int> mp; // 定义
m.insert(make_pair("abcd", 5)); // 插入元素
cout << mp.first << " " << mp.second; // 输出元素
m["abcd"]++; // 统计累加
m.begin(); m.end(); // 返回首尾迭代器
m.size(); // 返回当前映射关系数量
m.clear(); // 清空
m.find(x); // 返回从x指出的映射的迭代器
m.count(x);//返回是否有从x指出的映射
pair <int, int> mp[100]; // pair类型
cout << mp[x].first << " " << mp[x].second; // 输出
二分查找
lower_bound(a + 1, a + 1 + n, x) - a; // 返回 a 数组中第一个大于等于 x 的元素的下标
upper_bound(a + 1, a + 1 + n, x) - a; // 返回 a 数组中第一个大于 x 的元素的下标
// 若没有满足条件的元素, 返回尾指针, 即 a + 1 + n