STL
vector (动态数组)
初始化:
vector<int> a;
vector<int> a(10); 长度为10的vector
vector<int> a(10, 3) 长度为10 并且每个数都为3
vector<int> a(a1) 用a1 初始化a
vector<int> a[10] 定义了10个vector
用法:
a.size() 元素的个数
a.empty() 判断是否为空
a.clear() 清空
a.front()/back() 返回第一个数/最后一个数
a.pop_back() 删掉最后一个数
a.push_back() 加入一个数
begin()/end()
[]
pair
定义 初始化:
pair<int, string> q;
q = make_pair(10, "abc");
用法:
pair<int, int>
first, 第一个元素
second, 第二个元素
支持比较运算,以first为第一关键字,以second为第二关键字(字典序)
queue (队列) [先进先出]
用法:
size()
empty()
push() 向队尾插入一个元素
front() 返回队头元素
back() 返回队尾元素
pop() 弹出队头元素
优先队列 (堆)
priority_queue<int> q; 按降序排列
priority_queue<int, vector<int>, greater<int> > q; 按升序排列
stack 栈 [后进先出]
用法:
size()
empty()
push() 向栈顶插入一个元素
top() 返回栈顶元素
pop() 弹出栈顶元素
deque 双端队列 [可以在两端添加] (不常用)
size()
empty()
clear()
front()/back()
push_back()/pop_back()
push_front()/pop_front()
begin()/end()
[]
set, map, multiset, multimap
set 里无重复元素且排好序, multiset 里可有重复元素
map 类似
size()
empty()
clear()
begin()/end()
++, -- 返回前驱和后继,时间复杂度 O(logn)
set/multiset
set<int> s;
insert() 插入一个数
find() 查找一个数
count() 返回某一个数的个数
erase()
(1) 输入是一个数x,删除所有x O(k + logn) [k是x的个数]
(2) 输入一个迭代器,删除这个迭代器
lower_bound()/upper_bound()
lower_bound(x) 返回大于等于x的最小的数的迭代器
upper_bound(x) 返回大于x的最小的数的迭代器
map/multimap
map<int, string> s;
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(), 迭代器的++,--
bitset 状压
bitset, 圧位
bitset<10000> s;
~, &, |, ^
>>, <<
==, !=
[]
count() 返回有多少个1
any() 判断是否至少有一个1
none() 判断是否全为0
set() 把所有位置成1
set(k, v) 将第k位变成v
reset() 把所有位变成0
flip() 等价于~
flip(k) 把第k位取反