??本章将介绍
S
T
L
STL
STL 中的
v
e
c
t
o
r
，
q
u
e
u
e
，
p
r
i
o
r
i
t
y
_
q
u
e
u
e
，
d
e
q
u
e
，
s
e
t
，
m
u
l
t
i
s
e
t
，
m
a
p
，
b
i
t
s
e
t
vector，queue，priority\_queue，deque，set，multiset，map，bitset
vector，queue，priority_queue，deque，set，multiset，map，bitset 八个部分。
??同时还会介绍算法头文件中的部分函数。
#include <vector>（动态数组）
??
v
e
c
t
o
r
vector
vector 是
S
T
L
STL
STL 的动态数组，其内部实现基于倍增思想，在程序运行时能根据需求改变数组的大小。
??
v
e
c
t
o
r
vector
vector 支持随机访问，它的内存空间同数组般是连续的，所以索引可以在常数时间内完成。但是在中间进行插入和删除操作会造成内存块的复制，与链表不同这种操作无法在
O
(
1
)
O(1)
O(1) 完成，为保证效率元素的删减一般在末尾进行，因此我们将不会在动态数组中使用在数组中间插入和删除的功能（虽然可以）。
声明
| 代码 | 释义 |
|---|
| vector<int> a; | 相当于一个长度动态变化的
i
n
t
int
int 数组 | | vector<int> a(b); | 用b定义a | | vector<int> a(10); | 初始
10
10
10 个
0
0
0 元素 | | vector<int> a(10,6); | 初始
10
10
10 个
6
6
6 元素 |
| 代码 | 释义 |
|---|
| vector<string> a(10,“null”); | 初始
10
10
10 个
n
u
l
l
null
null 元素 | | vector<string> vec(10,“hello”); | 初始
10
10
10 个
h
e
l
l
o
hello
hello 元素 | | vector<string> b(a.begin(),a.end()); | b是a的复制 |
a用来储存坐标
struct point{int x,y;};
vector<point> a;
常用操作
push_back/pop_back
??a.push_back(x); 把元素 x 插入到vector 的尾部。
??a.pop_back(); 删除 vector 的最后一个元素。
size/empty
??a.size(); 返回 vector 的实际长度。
??a.empty(); 返回一个 bool 类型，表明 vector 是否为空。两者的时间复杂度均为
O
(
1
)
O(1)
O(1)。
??所有的
S
T
L
STL
STL 均支持这两种方法，含义也相同。后面将不会重复提到。
clear
??a.clear(); 将 vector清空。
begin/end
??a.begin(); 返回vector 中的第一个元素的迭代器。例如 a 是一个非空的 vector，则 *a.begin() 与 a[0] 的作用相同。
??a.end(); 返回 vector 的尾部，即第 n 个元素再往后的“边界”，*a.end()与 a[n] 都是越界访问。其中 n=a.size()。
??下面两份代码都遍历了 vector<int> a; 并输出其所有元素。
for(int i=0;i<a.size();i++){
cout<<a[i]<<" ";
}
for(vector<int>::iterator it=a.begin();it!=a.end();it++){
cout<<*it<<" ";
}
front/back
??a.front() 返回 vector 的第一个元素，等价于 *a.begin() 和 a[0]。
??a.back() 返回 vector 的最后一个元素，等价于 *-- a.end() 和 a[a.size()-1]。
reverse
??reverse(a.begin(), a.end()) 将 vector 翻转。
??该函数包含在 算法头文件中，其时间复杂度为
O
(
n
)
O(n)
O(n)。
sort
??sort(a.begin(), a.end()); 使用sort函数排序，从小到大排
#include <bitset>
??
b
i
t
s
e
t
bitset
bitset 可以看作一个多位二进制数，每八位占用一个字节，相当于采用了压缩状态的二进制数组，并支持基本的位运算。在估算程序运行的时间的时，我们一般以
32
32
32 位整数的运算次数为基准，因此
n
n
n 位的
b
i
t
s
e
t
bitset
bitset 执行一次位运算的复杂度可视为
n
32
\frac{n}{32}
32n?。
声明
bitset<10000> s;
??表示一个
10000
10000
10000 位的二进制数，<> 中填写位数。下面把数位记为
n
n
n。
常用操作
| 代码 | 注释 |
|---|
| 同二进制逻辑运算 | 位运算操作符 | | s[k] | 和数组相同用法 | | s.count() | 返回有多少位
1
1
1 | | s.any() | 若 s 所有位为 0 返回 false，若至少有一位为 1 则返回 true | | s.none() | 与s.any() 相反 | | s.set() | 把
s
s
s 的所有位变成
1
1
1 | | s.set(k,v) | 同等于
s
[
k
]
=
v
s[k]=v
s[k]=v | | s.reset() | 把
s
s
s 的所有位变为
0
0
0 | | s.reset(k) | 同等于
s
[
k
]
=
0
s[k]=0
s[k]=0 | | s.flip() | 把
s
s
s 的所有位取反 | | s.flip(k) | 把
s
s
s 的第
k
k
k 位取反，同等于
?
s
[
k
]
~s[k]
?s[k] |
|