STL进阶 | OI笔记

$STL$ 容器

$vector$ 变长数组

包含在 < vector > 头文件中

基本思想：倍增

系统为某一程序分配空间时，所用时间与空间大小无关，只与申请次数有关。因此 vector 为保证效率，需要尽可能减少申请次数。**vector 使用倍增的思想分配空间**

vector 在定义时，先开辟一定长度的空间，当元素个数大于当前数组长度时，开一个两倍于该长度的空间，再将原数组复制进新数组

由此可知，当开辟一个长度为 n 的 vector 数组时，需进行 log2n 次开辟空间的操作，总复制次数为 n，平均插入每个数的时间复杂度是 O(1)

定义

vector<int> a;

vector<int> a(N);
// 定义一个长度为 N 的 vector 数组，初始化为0

vector<int> a(10, 3);
// 定义一个长度为 10 的 vector 数组，每个元素的值均为 3
vector<string> a(10, "wangk");

vector<int> a[10];
// 定义 10 个 vector 数组

操作函数

O(1):

a.size();
// 返回 a 数组中元素的个数
// 注意：size 函数为无符号类型，即使用 a.size() - 1 有 RE 风险

a.empty();
// 判断 a 数组是否为空

a.front();
// 返回 a 数组的第一个元素

a.back();
// 返回 a 数组的最后一个元素

a.push_back(x);
a.emplace_back(x);
// 向 a 数组最后插入一个元素 x

a.pop_back();
// 删除 a 数组最后一个元素

O(n)；

a.clear();
// 清空 a 数组，容量不变

a.erase(begin, end);
// 删除 [begin, end) 区域内元素

迭代器：

a.begin();
// 返回 a 数组第 0 个元素

a.end();
// 返回 a 数组最后一个元素的下一个位置

• vector 还支持随机寻址。即可以使用
  a[2] 访问 a 数组第 3 个元素

遍历 vector 数组

for (int i = 0; i < a.size(); i ++) 
    cout << a[i] << endl;

for (vector<int> :: iterator i = a.begin(); i != a.end(); i ++)
    cout << *i << endl;

for (auto x : a)
    cout << x << endl;

• vector 还支持按照字典序比较两数组，直接使用运算符比较即可

---

$pair$ 二元组

定义：

pair<int, string> a;

a = make_pair(10, "Hello");

a = {10, "World"};

操作函数

a.first();
// 取 a 的第一个元素

a.second();
// 取 a 的第二个元素

• 支持比较远算，与 vector 一样是按照字典序排序，以 first 为第一关键字，以 second 为第二关键字

ps: 一些奇技淫巧

如果有三个关键字需存储，我们仅需：

pair<int, pair<int, int>> a;

即在 p 中存入了三个整型变量

---

$string$ 字符串

定义

string a;

操作函数

a.size(); || a.length();
// 返回字符串长度

a.empty();
// 返回字符串是否为空

a.clear();
// 清空字符串

a.substr(l ,n);
// 返回从 l 开始长度为 n 的字串
// 注：l 参数从 0 开始

a.c_str();
// 返回 a 存储字符串的起始地址，多用于输出

• 字符串可以支持 + 运算，使用 a + b 即可将 a 和 b 两个字符串首位拼接在一起

---

$queue$ 队列

包含在 < queue > 头文件中

定义

queue<int> q;

q = queue<int>();

操作函数

a.size();
// 返回队列中元素的个数，O(1)

a.empty();
// 判断队列是否为空

a.push();
// 向队尾插入一个元素

a.pop();
// 删除队头一个元素

a.front();
// 返回队头元素

a.back();
// 返回队尾元素

$deque$ 双端队列

常数和空间都极大，不建议使用

操作函数

$O(1)$

a.size();
// 返回队列中元素的个数

a.empty();
// 判断队列是否为空

a.clear();
// 清空队列

a.front();
// 返回队列最左侧元素

a.back();
// 返回队列最右侧元素

a.push_back(x);
// 在队列右侧插入元素 x 

a.pop_back();
// 在队列右侧删除一个元素

a.push_front(x);
// 在队列左侧插入元素 x 

a.pop_front();
// 在队列左侧删除一个元素

迭代器：

a.begin();
// 返回队列最左侧首元素

a.end();
// 返回队列最右侧元素的下一个位置

• deque 还支持随机寻址。即可以使用
  a[2] 访问队列 a 从左往右数第 3 个元素

$priority_queue$ 优先队列 / 堆

具体的实现方式，可见[[2022.11.12 - 堆]]

定义

priority_queue<int> heap;
// 定义大根堆(从大到小排序，以最大值为根节点)

heap.push(-x);
// 在大根堆进行此操作，即可将 x 的绝对值按照从小到大排序(小根堆)

priority_queue<int, vector<int>, greater<int> > heap;
// 定义小根堆(从小到大排序，以最小值为根节点)

操作函数

heap.push();
// 向堆中插入一个元素

heap.pop();
// 删除堆顶一个元素

heap.top();
// 返回堆顶元素

heap.emplace(x);
// 创建一个堆，并将元素插入堆

---

$stack$ 栈

定义

stack<int> heap;

操作函数

heap.push();
// 向栈顶插入一个元素

heap.pop();
// 删除栈顶一个元素

heap.top();
// 返回栈顶元素

heap.size();
// 返回栈中元素的个数

a.empty();
// 判断栈是否为空

---

$set$ & $multiset$ 有序集合 & 有序多重集合

• 基于平衡二叉树(红黑树)实现
  可动态维护有序序列，因此不支持随机寻址

• set 中不会出现重复元素，重复插入的元素会被忽略。

• multiset 允许重复元素的存在。

操作函数

$O(1)$

a.size();
// 返回集合元素个数

a.empty();
// 判断集合是否为空

a.clear();
// 清空集合

$O(log_2n)$

a.insert(x);
// 向集合中插入元素 x，返回 pair：{插入位置迭代器, 是否成功}

a.find(x);
// 在集合中查找元素 x，如果不存在则返回 a.end() 迭代器

a.count(x);
// 返回集合中元素 x 的数量

a.erase(x);
// 输入变量 - 删除所有 x
// 输入迭代器 - 删除迭代器所指向的 x

a.lower_bound(x);
// 返回大于等于 x 的最小元素的迭代器

a.upper_bound(x);
// 返回大于 x 的最小元素的迭代器

// 以上两个函数如果不存在这样的元素，则返回 a.end() 迭代器，如解引用迭代器可能会导致 RE

$map$ & $multimap$ 映射

包含在 < map > 头文件中

• 基于平衡二叉树 (红黑树) 实现
  动态维护有序序列

定义

map<string, int> a;
// string 代表键 key, 不可重复
// int 代表值 val

a["wangk"] = 1;

操作函数

$O(1)$

a.size();
// 返回集合元素个数

a.empty();
// 判断集合是否为空

a.clear();
// 清空集合

$O(log_2n)$

a.insert();
// 向映射中插入一个 pair

a.erase();
// 在映射中删除一个 pair，输入 pair 和迭代器均可

a.find();
// 查找映射

a.lower_bound(x);
// 返回大于等于 x 的最小元素的迭代器

a.upper_bound(x);
// 返回大于 x 的最小元素的迭代器

// 以上两个函数如果不存在这样的元素，则返回 a.end() 迭代器

访问与遍历

使用 a[x] 访问时，如果无法找到，则新建一个 $key$ 为 $x$ 的 $map$，$val$ 指向 $0$

for (auto x : a)
    cout << x.first << " " << x.second << endl;

注意：在遍历中无法修改 $key$，只能修改 $value$

特殊使用

cout << a["wangk"] << endl;

输出 1，时间复杂度为 $O(log_2n)$

$unordered_set$ & $unordered_map$ 无序集合 / 映射

$unordered_multiset$ & $unordered_multimap$ 多重无序集合 / 映射

总体操作和 set map 等类似，操作的时间复杂度为 O(1)，不支持 lower_bound()和upper_bound() 以及 map 的特殊使用方法

注意：在初始化时会开 4 倍空间，警钟敲烂

---

bitset 压位

定义

bitset<10000> s;
// 定义长度为 10000 的 bitset

操作

• ~ & | ^ >> << == !=
• 取某一位 s[]

s.count();
// 返回 1 的个数

s.any();
// 是否至少有一个 1

s.none();
// 是否全部为 0

s.set();
// 将所有位置初始化成 1

s.reset();
// 将所有位置初始化为 0

s.set(k, v);
// 将第 k 位赋为 v

s.flip();
// 将所有位置取反

s.flip(k);
// 将第 k 位取反

STL 函数

需引入 <alrorithm> 头文件

• 规定下文中 begin 和 end 均为迭代器

min(x, y);

max(x, y);

swap(x, y);

find(begin, end, x);

count(begin, end, x);

revise(begin, end);

random_shuffle(begin, end);

unique(begin, end);

nth_element(bengin, begin + k, end, compare);
// 找出序列中第 n 大的元素，使其左边均为小于它的数，右边均为大于它的数。

lower_bound(begin, end, x);
upper_bound(begin, end, x);

next_permutation(begin, end);
prev_permutation(begin, end);
// 返回数列按字典序的上 / 下一个位置，可用于枚举全排列

值得注意的是，random_shuffle 自 C++14 起被弃用，C++17 起被移除。我们可以使用 shuffle 函数代替原来的 random_shuffle。使用方法为:

shuffle(v.begin(), v.end(), rng);

（最后一个参数传入的是使用的随机数生成器，一般情况使用以真随机数生成器 random_device 播种的梅森旋转伪随机数生成器 mt19937）。