vector

变长数组。倍增思想。

系统为某一程序分配空间时，所需时间与分配的空间大小无关，与申请次数有关。

初始时，为 vector 申请 32 个空间长度，当空间占满后，申请 2 倍大小的空间，然后将原来的 32 个空间中的内容复制到新的空间中，继续使用新的空间。

复制元素均摊后时间复杂度为 O(1)O(1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <vector>
#include <iostream>
using namespace std;

int main () {
  // 最简单用法，初始化一个 vector
  vector<int> a;
  // 初始化一个长度为 10 的 vector
  vector<int> b(10);
  // 初始化一个长度为 10 的 vector，并将其中的元素都设置成 3
  vector<int> c(10, 3);
  // 初始化一个二维 vector，大小为 m * n
  vector<vector<int>> res(m, vector<int>(n));

  // 所有容器都有这两个方法，时间复杂度 O(1)。
  // 求 a 中元素的个数
  a.size();
  // a 是否为空，为空时返回 true
  a.empty();
  // 清空
  a.clear();
  // 返回 vector 第一个数
  a.front();
  // 返回 vector 最后一个数
  a.back();
  // 向 vector 最后添加一个数
  a.push_back();
  // 删除 vector 最后一个数
  a.pop_back();
  // vector 迭代器，指向第一个数
  a.begin();
  // vector 迭代器，指向最后一个数的下一个位置
  a.end();
  // 支持随机寻址，如果传入的下标长度超过 vector 容量，会报错
  a[5];

  // 遍历方式
  for(int i=0;i<a.size();i++) cout << a << ' ';
  cout << endl;

  // 迭代器方式
  // 可以写成 auto i = a.begin()
  for(vector<int>::iterator i = a.begin();i!=a.end();i++) cout << a << ' ';
  cout << endl;

  // 范围遍历，C++11 新语法，速度快
  for(auto x: a) cout << a << ' ';
  cout << endl;

  // 支持比较运算，按照字典序比较
  vector<int> m(4, 3);
  vector<int> n(3, 4);
  if(m < n) puts("m < n");

  return 0;
}

pair

存储一个二元组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <vector>
#include <iostream>
using namespace std;

int main () {
  pair<int, string> p;
  // 存储三个元素
  pair<int, pair<int, string>> p2;
  // 初始化
  p = make_pair(3, "abc");
  p = {4, "def"};
  // 取第一个元素
  p.first;
  // 取第二个元素
  p.second;
  // 支持比较运算，以 first 为第一关键字，以 second 为第二关键字，进行比较，也是按照字典序
  return 0;
}

string

字符串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <vector>
#include <iostream>
using namespace std;

int main () {
  string s;
  s.size();
  s.empty();
  s.clear();
  // 拼接一个字符
  s += 'a';
  // 拼接一个字符串
  s += "abc";

  // 从下标 i 开始截取 j 个字符
  s.subtr(i, j);
  // 用 printf 输出字符串时，需要调用 c_str()
  printf("%s", s.c_str());
  return 0;
}

常用操作

substr

从下标 i 开始截取 j 个字符。

c_str

返回一个 char*，指向字符串起始位置。

queue

队列

常用操作

没有 clear 函数。

push

向队尾插入一个元素。

front

返回队头元素。

pop

弹出队头元素。

priority_queue

优先队列，是一个堆。默认是大根堆。

1
2
3
4
5
6
7
8
9
10
11
12
#include <vector>
#include <queue>
#include <iostream>
using namespace std;

int main () {
  // 大根堆
  priority_queue<int> q;
  // 小根堆，需要引入 <vector>
  priority_queue<int, vector<int>, greater<int>> p;
  return 0;
}

常用操作

没有 clear 函数。

push

向堆中插入一个元素。

top

返回堆顶元素。

pop

弹出堆顶元素。

stack

栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <stack>
#include <iostream>
using namespace std;

int main () {
  stack<int> stk;
  // 向栈中插入一个元素
  stk.push(3);
  // 返回栈顶元素
  stk.top();
  // 弹出栈顶元素
  stk.pop();
  return 0;
}

常用操作

没有 clear 函数。

push

向栈中插入一个元素。

top

返回栈顶元素。

pop

弹出栈顶元素。

deque

双端队列，队头队尾都可以插入删除，支持随机访问。加强版的 vector。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <deque>
#include <iostream>
using namespace std;

int main () {
  deque<int> a;
  // 返回队首元素
  a.front();
  // 返回队尾元素
  a.back();
  // 向队尾增加一个元素
  a.push_back();
  // 从队尾删除一个元素
  a.pop_back();
  // 向队首增加一个元素
  a.push_front();
  // 从队首删除一个元素
  a.pop_front();
  // 支持随机寻址
  a[5];
  return 0;
}

set, map, multiset, multimap

基于平衡二叉树（红黑树）实现，动态维护一个有序序列。

增删改查操作时间复杂度为 O(log(n))O(log(n))。支持跟排序有关的操作。

set/multiset

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <set>
#include <iostream>
using namespace std;

int main () {
  set<int> s;
  s.insert(5);
  s.insert(6);
  s.insert(7);
  s.insert(8);
  s.find(5);
  s.count(5);
  // erase(x) 可以输入一个数 x，会删除集合中所有的 x；也可以输入一个迭代器，删除这个迭代器指向的数
  s.erase(5);
  // lower_bound(x) 返回大于等于 x 的第一个数（也可以说是最小的数）的迭代器
  s.lower_bound(6);
  // upper_bound(x) 返回大于 x 的第一个数（也可以说是最小的数）的迭代器
  s.upper_bound(6);
  return 0;
}

常用操作

insert

插入一个数。

find

查找一个数，返回迭代器。

count

统计一个数出现的次数。

erase

erase(x) 可以输入一个数 x，会删除集合中所有的 x；也可以输入一个迭代器，删除这个迭代器指向的数。

lower_bound

lower_bound(x) 返回大于等于 x 的第一个数（也可以说是最小的数）的迭代器。

upper_bound

upper_bound(x) 返回大于 x 的第一个数（也可以说是最小的数）的迭代器。

begin

迭代器支持 -- 和 ++ 操作。返回当前节点在有序序列中的前驱和后继。时间复杂度为 O(log(n))O(log(n))。

end

迭代器支持 -- 和 ++ 操作。返回当前节点在有序序列中的前驱和后继。时间复杂度为 O(log(n))O(log(n))。

map/multimap

map 用于做映射。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <map>
#include <iostream>
using namespace std;

int main () {
  map<string, int> a;
  // 定义映射关系
  a["abc"] = 1;
  // 访问
  cout << a["abc"] << endl;
  // 支持解构赋值
  for(auto [k, v]: a) cout << k << "->" << v << endl;
  return 0;
}

常用操作

insert

输入的内容是一个 pair。

erase

输入参数可以为 pair 或迭代器。

find

查找一个数，返回迭代器。

lower_bound

lower_bound(x) 返回大于等于 x 的第一个数（也可以说是最小的数）的迭代器。

upper_bound

upper_bound(x) 返回大于 x 的第一个数（也可以说是最小的数）的迭代器。

随机访问 []

可以像使用数组一样使用 map。时间复杂度为 O(log(n))O(log(n))。

unordered_set, unordered_map, unordered_multiset, unordered_multimap

基于哈希表实现。与上面类似，不支持 lower_bound/upper_bound，不支持迭代器的 --、++。增删改查操作时间复杂度为 O(1)O(1)。

bitset

压位

比布尔数组省 8 倍的内存。用于压缩存储 bool 类型的数据。bool 数组每个元素占 1 个字节。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bitset>
#include <iostream>
using namespace std;

int main () {
  // 创建一个 10000 位的 bitset
  bitset<10000> s;
  bitset<10000> t;
  // 支持按位操作
  ~s;
  s | t;
  s & t;
  s ^ t;
  s >>= 3;
  t <<= 2;
  // 支持比较运算符
  s == t;
  s != t;
  // 返回 s 中 1 的个数
  s.count();
  // 判断 s 中是否至少有一个 1
  s.any();
  // 判断 s 中是否全为 0
  s.none();
  // 把 s 的所有位置成 1
  s.set();
  // 将第 k 位设置为 v
  s.set(k, v);
  // 把 s 的所有位置成 0
  s.reset();
  // 把 s 的所有位取反，等价于 ~s
  s.flip();
  // 把 s 的第 k 位取反
  s.flip(k);
  return 0;
}