stl clear() 没写的迭代器都没有这个函数
vector 变长数组, 倍增的思想
size() 返回元素个数
empty() 返回是否为空
clear() 清空
front()/ back() 返回头与尾
rease(a, b) 删除从a开始到b-1的元素
begin()/end()第0个数/最后一个数的下一个位值
vector<int> a;
vector<int> a(n); 长度为n
vector<int> a(n, b) 长度为n个b的数
支持比较运算,按字典序比较
pair
first, second
支持比较排序,按字典序,以first为第一关键字,second为第二关键字
构造一个pair: `p = make_pair(10, "yxc");` 在c++11中 `p = {10, "yxc"};`
`pair<int, pair<int,int>> p;` 存三个东西
string, 字符串, substr, c_str()返回头指针
size()/ length() 都是返回字符串长度
empty()
clear()
支持 +
substr(a, len) 返回从下标从a开始长度为len的子串
substr(a) 返回从a开始到串尾的子串
queue ,对列
size()
empty()
push() 向队尾插入一个元素
front() 返回队头元素
back() 返回队尾元素
pop() 弹出对头元素
`q = queue<int>();` 重新构造一个用来清空对列
priority_queue, 优先队列(用堆实现的—默认大根堆) 需要#include<queue>
push()
top()
pop()
push(-x) 定义小根堆
`priority_queue<int, vector<int>, greater<int>> heap;` 定义小根堆
stack, 栈
top()
push()
pop()
size()
empty()
deque, 双端对列 速度稍微慢一些
size()
empty()
clear()
front()
back()
push_back()/ pop_back()
push_front()/ pop_front()
begin()/ end() 迭代器
[]
set, map, multiset(可以有重复元素的), multimap, 基于平衡二叉树(红黑树), 动态维护有序序列
size()
empty()
begin()/ end() 支持++ / -- 操作 返回前驱与后继 _**时间复杂度是O(logn)**_
<set> 包含set, 与multiset
set/multiset
insert()
find() 不存在返回end()迭代器
count(x) 返回某个数x的个数
erase()
(1) 输入是一个数, 删除所有x O(k + logn) -- k是x的个数
(2) 输入是一个迭代器, 删除这个迭代器
lower_bound()/upper_bound()
lower_bound(x) 返回 >= x 的最小的迭代器
upper_bound(x) 返回 > x 的最小的迭代器 不存在返回end()
map/multimap
insert() 插入的数是一个pair
erase() 输入的参数是pair或者迭代器
find()
[] _**时间复杂度是O(logn)**_
`map<string, int> a; a["yxc"] = 1; cout << a["yxc"]; `
unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表
和上面的类似,增删改查的时间复杂度是O(1)
不支持 lower_bound()/ upper_bound() 和 迭代器的++, –
bitset, 压位
bitset<10000> s;
~ 取反, &, | , ^ 异或
>> << == !=
[]
count() 返回有多少个1
any() 判断是否至少有一个1
none() 判断是否全为8
set() 把所有位置成1
set( k, v) 将第k位变成v
reset() 把所有位变成O
flip() 等价于~
flip(k) 把第k位取反