终于到了说再见的时候了，竞赛中常见的STL容器将在这一篇迎来尾声，相信跟着我的介绍，大家足以用现在学到的这些容器解决90%的问题了，接下来要介绍的三个容器将会帮助我们解决剩下的5%，至于最后的5%，就要靠大家除我的博客额外去学习更多容器及其适配器关联容器了，废话不多说，进入正题。

一、优先队列（priority_queue）

我们之前介绍过双端队列（deque）而队列（queue）就是双端队列去除栈（stack）操作的更加适配的版本，由于之前我未曾提及队列和栈，大家可以自行学习相应的数据结构，不过直接用双端队列永远不失为一个好的选择。

优先队列（priority_queue）是一种特殊的队列，主要体现在其能自动排序。

优先队列的操作和队列一样，下面给出其部分重要函数：

q.size();  //返回q里元素个数
q.empty();  //返回q是否为空，空则返回1，否则返回0
q.push(k);  //在q的末尾插入k
q.pop();  //删掉q的第一个元素
q.top();  //返回q的第一个元素

优先队列可以自动排序，那么是什么样的排序规则呢？这里用一句话告诉大家结论，队首元素始终是优先级最高（即最大或最小）的元素。

下面给出小顶堆以及大顶堆的构造方法代码：

priority_queue<int, vector<int>, greater<int>> p; // 小顶堆

priority_queue<int> q; // 大顶堆
q.push(-x);            // 取负后入队，取时再取反，变为小顶堆

那么我们不禁产生疑问，我明明可以自己用sort排序找最大值最小值，这个优先队列有什么用呢，其实特别适合需要快速访问最高或最低优先级元素的场景，因为优先队列对于插入还有删除元素的时间复杂度极低，都是O(log n)，性能十分优异。

经典例题：
P5412 [YNOI2019] 排队 – 洛谷
[JSOI2007]建筑抢修

二、unordered_map

unordered_map其实就是无序map的意思，大家如果之前看过我的map篇的话，其实对于这个无序的理解会更加深刻，那么和map相比，什么情况下我们选择unordered_map呢？

其实unordered_map和map的底层构造并不相同，因为unordered_map是基于哈希表，而map是基于红黑树，因此它们调用尤其是查询函数时，unordered_map的时间复杂度时O(1)，极端情况会退化为O(n)，而map的时间复杂度永远是O(log n)。因此当我们需要大量查询操作并且对于顺序并无要求时，unordered_map将会是个上佳选择。

其常见用法与map保持一致，这里不再赘述。

经典例题：
P1102 A-B 数对 – 洛谷

三、unordered_set

unordered_set就是无序集合，和unordered_map一样的底层逻辑，同样的我们在之前的set篇里提到的内置函数同样适用unordered_set，对于什么时候选择unordered_set和unordered_map相同。

经典例题：
P4305 [JLOI2011] 不重复数字 – 洛谷

四、bitset

四月补充，还真是学无止尽
bitset位集合是一个由位（bit）组成的数组，每个位可以是 0 或 1，提供了高效的方式来存储和操作二进制数据，特别适合需要位级操作的场景。

基础用法如下：

#include <bitset>

// 声明一个大小为N的bitset
std::bitset<N> b;

// 初始化bitset
b = std::bitset<N>(value);

// 访问位集合中的单个位
bool bit = b[i];

初始化 std::bitset：

• 默认初始化：所有位为 0。
• 从整数初始化：将整数转换为二进制。
• 从字符串初始化：将字符串解析为二进制。

如：

std::bitset<8> bits1;               // 默认初始化：00000000
std::bitset<8> bits2(42);           // 从整数初始化：00101010
std::bitset<8> bits3("10101010");   // 从字符串初始化：10101010

常见成员函数如下：

• operator[]：访问或修改某一位。
• set()：将某一位或所有位设置为 1。
• reset()：将某一位或所有位设置为 0。
• flip()：翻转某一位或所有位。

如：

std::bitset<8> bits("00001111");
bits[0] = 1;          // 修改第 0 位：00001111 -> 00001111
bits.set(4);          // 设置第 4 位：00001111 -> 00011111
bits.reset(1);        // 重置第 1 位：00011111 -> 00011101
bits.flip();          // 翻转所有位：00011101 -> 11100010

查询位信息：

• count()：返回 1 的个数。
• size()：返回位数。
• test(pos)：检查某一位是否为 1。
• all()：检查是否所有位都为 1。
• any()：检查是否有任何一位为 1。
• none()：检查是否所有位都为 0。

如：

std::bitset<8> bits("10101010");
std::cout << "Count of 1s: " << bits.count() << std::endl;  // 输出 4
std::cout << "Size: " << bits.size() << std::endl;          // 输出 8
std::cout << "Is bit 3 set? " << bits.test(3) << std::endl; // 输出 1 (true)
std::cout << "All bits set? " << bits.all() << std::endl;   // 输出 0 (false)

转换为其他类型:

• to_ulong()：将 std::bitset 转换为 unsigned long。
• to_ullong()：将 std::bitset 转换为 unsigned long long。
• to_string()：将 std::bitset 转换为字符串。

如：

std::bitset<8> bits("10101010");
unsigned long num = bits.to_ulong();  // 转换为整数：170
std::string str = bits.to_string();   // 转换为字符串："10101010"

std::bitset 支持常见的位操作，如按位与、按位或、按位异或和按位取反。

如：

std::bitset<8> bits1("10101010");
std::bitset<8> bits2("11110000");

std::bitset<8> result_and = bits1 & bits2;  // 按位与：10100000
std::bitset<8> result_or = bits1 | bits2;   // 按位或：11111010
std::bitset<8> result_xor = bits1 ^ bits2;  // 按位异或：01011010
std::bitset<8> result_not = ~bits1;         // 按位取反：01010101

经典例题：
L1-4 颠倒阴阳