【算法基础课-算法模板2】数据结构

数据结构算法模板目录

• 链表
• • 单链表
  • 双链表
• 栈
• • 普通栈
  • 单调栈
• 队列
• • 普通队列
  • 循环队列
  • 单调队列
• KMP
• Trie树
• 并查集
• 堆
• 哈希
• • 一般哈希
  • 字符串哈希
• C++ STL简介
• • 序列式容器
  • • vector
    • deque
    • string
  • 容器适配器
  • • stack
    • queue
    • priority_queue
  • 关联式容器
  • • set / multiset
    • map / multimap
  • 无序容器
  • 轻量辅助类型
  • • pair
    • bitset

链表

单链表

【算法思想】：
单链表是一种基本的数据结构，它由一系列节点组成，每个节点包含数据部分和指向下一个节点的指针。
1.初始化链表
链表的初始化过程是为链表设置一个空的起始状态。在这个步骤中，通常会定义一个头指针head，用于指向链表的第一个元素。初始时，head指向-1，表示链表为空。同时，idx用于记录当前节点的索引，初始化为0。
2.向链表头插入元素
新节点的next指针指向原链表的头部，随后更新头指针为新节点。
3.删除第k个位置的元素
删除第k个位置的元素时，我们需要将第k-1个节点的next指针指向第k个节点的下一个节点，从而跳过要删除的节点。
4.在第k个位置后插入元素
在第k个位置后插入一个新元素时，首先将新元素存入当前节点。然后，新节点的next指针指向第 k 个节点的原next指针，接着修改第k个节点的next 指针，指向新节点。
【算法模板】：

const int N = 1e5 + 10; // 定义链表的最大长度int e[N], ne[N]; // e[] 存储链表的值，ne[] 存储链表节点的 nextint head, idx; // head 指向链表头部，idx 记录当前节点的索引// 初始化链表void init() { head = -1; // 初始时，链表为空，头指针为 -1 idx = 0; // 从索引 0 开始}// 向链表头插入一个元素 xvoid add_to_head(int x) { e[idx] = x; // 将值 x 存储在当前节点 ne[idx] = head; // 当前节点的 next 指向原链表头部 head = idx++; // 更新头部指针为当前节点，idx 自增}// 删除第 k 个位置的元素void del_k(int k) { ne[k - 1] = ne[ne[k - 1]]; // 修改第 k-1 个节点的 next 指针，跳过要删除的节点}// 在第 k 个位置后插入一个元素 xvoid add_k(int k, int x) { e[idx] = x;  // 将值 x 存储在当前节点 ne[idx] = ne[k - 1]; // 当前节点的 next 指向原来第 k 个节点的 next ne[k - 1] = idx; // 修改第 k-1 个节点的 next 指针，指向当前节点 idx++; // 更新索引}

双链表

【算法思想】：
双链表是一种扩展版的链表，每个节点不仅有指向下一个节点的指针next，还有指向前一个节点的指针prev。这种结构使得双链表能够更高效地在任意位置进行插入和删除操作，因为我们可以同时通过前向和后向指针访问节点，而无需从头开始遍历。
1.初始化双链表
双链表的初始化与单链表类似，首先需要定义一个大小为N的数组来存储每个节点的数据、左指针和右指针。idx用于记录当前可用节点的索引，初始值为0。
2.在节点a的右边插入一个新节点x
首先需要将x存入当前节点，并设置它的左指针指向a，右指针指向节点a的右邻节点。然后需要更新节点a的右邻节点的左指针和a的右指针，以确保新的节点被正确插入。
3.删除节点a
将节点a右邻节点的左指针指向节点a的左邻节点，同时将节点a左邻节点的右指针指向节点a的右邻节点。
【算法模板】：

const int N = 100010; // 最大节点数int m; // 操作次数int e[N], l[N], r[N], idx; // e[] 存储节点值，l[] 存储左指针，r[] 存储右指针，idx 记录当前可用节点的索引// 在节点a的右边插入一个数xvoid insert(int a, int x) { e[idx] = x; // 存储值 x 到当前节点 l[idx] = a; // 当前节点的左指针指向节点a r[idx] = r[a]; // 当前节点的右指针指向节点a的右指针 l[r[a]] = idx; // 将a的右指针指向当前节点 r[a] = idx++; // 更新a的右指针，指向当前节点，idx 自增}// 删除节点avoid remove(int a) { l[r[a]] = l[a]; // 修改a的右指针的左指针 r[l[a]] = r[a]; // 修改a的左指针的右指针}

栈

普通栈

【算法思想】：
栈是一种常见的数据结构，它遵循后进先出的原则。栈的基本操作包括压栈（push）和弹栈（pop）。栈在许多算法中都有广泛应用，特别是在需要进行回溯、递归调用、表达式求值等场景中。
1.初始化栈
stk[]用来存储栈中的元素，tt用来表示栈顶的位置，tt = 0表示栈是空的。
2.向栈顶插入一个元素（压栈）
将新元素x插入到栈顶，栈顶指针tt加1，然后将x存储在stk[tt]中。
3.从栈顶弹出一个元素（弹栈）
栈顶元素会被删除，栈顶指针tt减1。由于栈遵循“后进先出”原则，所以总是从栈顶弹出最后插入的元素。
4.获取栈顶元素
栈顶的值就是当前tt索引指向的元素。
5.判断栈是否为空
栈是否为空取决于栈顶指针tt的值。如果tt的值大于0，表示栈中还有元素，否则栈为空。
【算法模板】：

// tt表示栈顶int stk[N], tt = 0;// 向栈顶插入一个数stk[ ++ tt] = x;// 从栈顶弹出一个数tt -- ;// 栈顶的值stk[tt];// 判断栈是否为空，如果 tt > 0，则表示不为空if (tt > 0) {}

单调栈

【算法思想】：
单调栈是一种在栈的基础上进行扩展的技术，广泛应用于解决“每个数左边/右边离它最近的比它大/小的数”这类问题。它通过维护栈中的元素的单调性，能够高效地解决一系列查询最近比它大的或小的元素的问题。单调栈的优势在于，它通过栈的结构，能够在线性时间内解决问题，避免了使用嵌套循环的低效方法。

单调栈的核心思想是利用栈来保持元素的单调性（单调递增或单调递减）。通过这种单调性，在遍历数组时，可以有效地找到每个元素的左边或右边最近的比它大或小的元素。
【算法模板】：

常见模型：找出每个数左边离它最近的比它大/小的数int tt = 0;for (int i = 1; i <= n; i ++ ){ while (tt && check(stk[tt], i)) tt -- ; stk[ ++ tt] = i;}

队列

队列是一种常见的线性数据结构，遵循先进先出的原则。队列与栈的主要区别在于，栈遵循后进先出的原则，而队列则是先进入的元素先被处理。

普通队列

【算法思想】：
队列的核心思想是按照“先进先出”的顺序处理元素。当新元素进入队列时，它们会被插入到队列的尾部；而当元素被处理时，它们会从队列的头部移除。队列可以用数组或链表来实现，数组实现时通常需要两个指针来表示队列的头部和尾部。
1.初始化队列
队列通常通过数组或链表来实现，q[]是存储队列元素的数组，hh是队头指针，tt是队尾指针。初始化时，队头指针hh为0，队尾指针tt为-1，表示队列为空。
2.入队
向队列的尾部插入一个元素，操作是将元素放入队列尾部，并更新队尾指针tt。
3.出队
从队列的头部弹出一个元素，操作是将队头元素移除，并更新队头指针hh。
4.获取队头元素
队头元素即为q[hh]，它是队列中第一个被处理的元素。
5.判断队列是否为空
通过判断hh <= tt来确认队列是否为空。如果hh <= tt，则表示队列不为空；如果hh > tt，则表示队列为空。
【算法模板】：

// hh 表示队头，tt表示队尾int q[N], hh = 0, tt = -1;// 向队尾插入一个数q[ ++ tt] = x;// 从队头弹出一个数hh ++ ;// 队头的值q[hh];// 判断队列是否为空，如果 hh <= tt，则表示不为空if (hh <= tt) {}

循环队列

【算法思想】：
循环队列是队列的一种变种，主要用于解决普通队列在处理元素时可能出现的空间浪费问题。在普通队列中，当队列元素被出队时，如果队列数组有空余空间，队头的空位就无法再利用。而循环队列则通过将队列的尾部和头部连接起来，实现“首尾相接”的结构，使得当队列头部元素被移除后，空余空间可以被重新利用。
【算法模板】：

// hh 表示队头，tt表示队尾的后一个位置int q[N], hh = 0, tt = 0;// 向队尾插入一个数q[tt ++ ] = x;if (tt == N) tt = 0;// 从队头弹出一个数hh ++ ;if (hh == N) hh = 0;// 队头的值q[hh];// 判断队列是否为空，如果hh != tt，则表示不为空if (hh != tt) {}

单调队列

【算法思想】：
单调队列是一种高效的数据结构，广泛应用于解决“滑动窗口中的最大值/最小值”等问题。它通过维护队列的单调性（递增或递减）来高效地计算滑动窗口内的最值，避免了暴力算法中重复计算的问题。

单调队列的核心思想是通过使用队列维护一个单调递增或单调递减的序列。在滑动窗口中，队列中的元素始终保持一定的单调性，从而使得我们能够在常数时间内得到窗口内的最大值或最小值。
单调递增队列：队列中的元素按从小到大的顺序排列。队头元素是窗口内的最小值。
单调递减队列：队列中的元素按从大到小的顺序排列。队头元素是窗口内的最大值。
在每次滑动窗口时，我们通过弹出队列中不满足条件的元素，并将新的元素插入到队列中，同时保持队列的单调性。
【算法模板】：

常见模型：找出滑动窗口中的最大值/最小值int hh = 0, tt = -1;for (int i = 0; i < n; i ++ ) { while (hh <= tt && check_out(q[hh])) hh ++ ; // 判断队头是否滑出窗口 while (hh <= tt && check(q[tt], i)) tt -- ; q[ ++ tt] = i;}

KMP

【算法思想】：
KMP算法是一种高效的字符串匹配算法，用于在一个长文本s中查找模式串p。相比传统的暴力算法，KMP通过在模式串匹配失败时，利用已匹配的部分信息避免重复比较，减少了匹配的时间复杂度。

预处理模式串：在KMP算法中，首先对模式串p进行预处理，构建一个next数组，该数组表示每个位置的最长前缀和后缀相等的长度。利用这个数组，算法在匹配过程中可以根据已经匹配的字符跳过不必要的比较。
模式串与文本的匹配：在匹配过程中，当匹配失败时，不需要回溯到文本的前一个字符，而是根据next数组指示的跳转位置，继续查找下一个匹配的可能位置。这样有效地减少了不必要的字符比较，从而提高了匹配效率。
【算法模板】：

// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度// 求模式串的next数组：for (int i = 2, j = 0; i <= m; i ++ ) { while (j && p[i] != p[j + 1]) j = ne[j]; if (p[i] == p[j + 1]) j ++ ; ne[i] = j;}// 匹配for (int i = 1, j = 0; i <= n; i ++ ) { while (j && s[i] != p[j + 1]) j = ne[j]; if (s[i] == p[j + 1]) j ++ ; if (j == m) { j = ne[j]; // 匹配成功后的逻辑 }}

Trie树

【算法思想】：
Trie树是一种多叉树，用于存储字符串集合，特别适合用于快速查找、前缀匹配、字符串自动补全等应用。其主要优点是可以利用公共前缀减少存储空间和查找时间，尤其在处理大量字符串时，效率非常高。

Trie树的每个节点都包含以下信息：
字符：每个节点代表一个字符。
子节点：每个节点可以有多个子节点，表示不同的字符。
标记（可选）：某些节点可能会标记某个完整字符串的结尾，用于区分前缀和完整的字符串。
计数/标志（可选）：用于表示某个节点的某个字符在当前字符串集合中出现的频率或状态。
【算法模板】：

int son[N][26], cnt[N], idx;// 0号点既是根节点，又是空节点// son[][]存储树中每个节点的子节点// cnt[]存储以每个节点结尾的单词数量// 插入一个字符串void insert(char *str) { int p = 0; for (int i = 0; str[i]; i ++ ) { int u = str[i] - \'a\'; if (!son[p][u]) son[p][u] = ++ idx; p = son[p][u]; } cnt[p] ++ ;}// 查询字符串出现的次数int query(char *str) { int p = 0; for (int i = 0; str[i]; i ++ ) { int u = str[i] - \'a\'; if (!son[p][u]) return 0; p = son[p][u]; } return cnt[p];}

并查集

【算法思想】：
并查集是一种常用的数据结构，用于处理一些不交集的合并及查询问题。其核心思想是通过维护一个森林结构来处理集合的合并与查找操作，并通过一些优化方法来提高其效率。并查集广泛应用于图论、网络连通性、动态连通性等地方。

并查集的基本操作包括查找和合并，它支持快速地合并两个集合，并且可以在常数时间内查询一个元素属于哪个集合。
查找（Find）：查找某个元素所属的集合（即该元素的祖宗节点）。如果一个元素是一个集合的根节点，返回它自己，否则递归查找直到找到根节点。
合并（Union）：合并两个集合。合并时将其中一个集合的根节点作为另一个集合的子树，形成一个新的集合。

并查集的优化：
并查集的核心思想是通过维护每个元素的父节点来表示集合的结构，而进行查找时会不断地向上查找直至根节点。但原始的并查集会导致树形结构过深，从而影响查找效率。为了提高效率，常常对并查集做一些优化。
最常用的优化方法是路径压缩：
在查找过程中，我们通过递归地更新每个节点的父节点指向根节点，减小树的深度，从而加速后续的查找操作。
【算法模板】：

// 1.朴素并查集int p[N]; //存储每个点的祖宗节点// 返回x的祖宗节点int find(int x) { if (p[x] != x) p[x] = find(p[x]); return p[x];}// 初始化，假定节点编号是1~nfor (int i = 1; i <= n; i ++ ) p[i] = i;// 合并a和b所在的两个集合：p[find(a)] = find(b);

// 2.维护size的并查集int p[N], size[N];//p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量// 返回x的祖宗节点int find(int x) {if (p[x] != x) p[x] = find(p[x]);return p[x];}// 初始化，假定节点编号是1~nfor (int i = 1; i <= n; i ++ ) {p[i] = i;size[i] = 1;}// 合并a和b所在的两个集合：size[find(b)] += size[find(a)];p[find(a)] = find(b);

// 3.维护到祖宗节点距离的并查集int p[N], d[N];//p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离// 返回x的祖宗节点int find(int x) {if (p[x] != x) {int u = find(p[x]);d[x] += d[p[x]];p[x] = u;}return p[x];}// 初始化，假定节点编号是1~nfor (int i = 1; i <= n; i ++ ) {p[i] = i;d[i] = 0;}// 合并a和b所在的两个集合：p[find(a)] = find(b);d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量

堆

【算法思想】：
堆是一种特殊的完全二叉树结构，常用于实现优先队列。通过堆，我们可以在$O(logn)$时间内高效地完成插和删除堆顶元素等操作，并支持$O(n)$时间的一次性建堆。

堆的定义与性质：堆是一棵除了最底层可能不满外，且最底层从左向右填充的二叉树。
堆序性质：
小根堆：每个节点的值都不大于其子节点值。堆顶（根节点）保存全集合的最小值。
大根堆：每个节点的值都不小于其子节点值，堆顶为最大值。

数组存储：堆通常用数组h[1…n]存储，其中：
根节点位于下标1；
对于存储在下标u的节点，其左儿子是2u，右儿子是2u+1；
父节点下标为⌊u/2⌋。

插入映射：为了支持按插入顺序定位并删除任意元素的操作，常维护两组辅助数组：
ph[k]：第k个插入元素在堆数组中的位置；
hp[u]：堆数组位置 u存放的是第几个插入的元素。
每次交换堆中两个位置时，需要同步更新ph与hp，保证映射关系不变。
【算法模板】：

// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1// ph[k]存储第k个插入的点在堆中的位置// hp[k]存储堆中下标是k的点是第几个插入的int h[N], ph[N], hp[N], size;// 交换两个点，及其映射关系void heap_swap(int a, int b) { swap(ph[hp[a]],ph[hp[b]]); swap(hp[a], hp[b]); swap(h[a], h[b]);}void down(int u) { int t = u; if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2; if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1; if (u != t) { heap_swap(u, t); down(t); }}void up(int u) { while (u / 2 && h[u] < h[u / 2]) { heap_swap(u, u / 2); u >>= 1; }}// O(n)建堆for (int i = n / 2; i; i -- ) down(i);

哈希

【算法思想】：
哈希表是一种典型的用于快速查找的数据结构，其核心思想是将任意规模的“关键字”通过哈希函数映射到一个固定大小的数组上，从而将查找、插入和删除等操作的平均时间复杂度降到 $O(1)$。

1 哈希表核心概念
1.1 哈希函数
将关键字 $x$ 映射到数组下标 $k$ 上的函数：$k=H(x)modN$
其中$N$为哈希表大小。
理想的哈希函数应满足“均匀分布”和“确定性”两大原则：
均匀分布：不同输入应尽可能分散到各个下标，降低冲突概率；
确定性：相同输入每次映射结果一致。
1.2 冲突
由于输入域远大于哈希表大小，不可避免地会出现不同关键字映射到同一位置的情况，称为“冲突”。如何高效地解决冲突，是哈希表设计的核心。

2.冲突解决策略
2.1 拉链法
思想：在哈希数组的每个槽位维护一个动态链表，所有映射到同一槽位的元素都插入该链表中。
2.2 开放寻址法
思想：所有元素都保存在同一个哈希数组中，发生冲突时按一定探测序列（线性探测、二次探测、双哈希等）寻找下一个空槽。

一般哈希

【算法模板】：

// (1) 拉链法int h[N], e[N], ne[N], idx;// 向哈希表中插入一个数void insert(int x) {int k = (x % N + N) % N;e[idx] = x;ne[idx] = h[k];h[k] = idx ++ ;}// 在哈希表中查询某个数是否存在bool find(int x) {int k = (x % N + N) % N;for (int i = h[k]; i != -1; i = ne[i])if (e[i] == x)return true;return false;}

// (2) 开放寻址法int h[N];// 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置int find(int x) {int t = (x % N + N) % N;while (h[t] != null && h[t] != x) {t ++ ;if (t == N) t = 0;}return t;}

字符串哈希

【算法模板】：

// 核心思想：将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低// 小技巧：取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果typedef unsigned long long ULL;ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64// 初始化p[0] = 1;for (int i = 1; i <= n; i ++ ){ h[i] = h[i - 1] * P + str[i]; p[i] = p[i - 1] * P;}// 计算子串 str[l ~ r] 的哈希值ULL get(int l, int r){ return h[r] - h[l - 1] * p[r - l + 1];}

C++ STL简介

C++ 标准模板库（STL，Standard Template Library）提供了一组高效、通用的容器与算法，极大地简化了日常开发中的数据结构操作。

序列式容器

以线性顺序存储元素，支持根据位置的快速访问。

vector

概念：动态可变长数组，底层按倍增策略分配空间，扩容/收缩具备摊还线性复杂度。
场景：需要频繁随机访问或尾部插入/删除。
常用接口：

vector<int> v;v.size(); // 元素个数v.empty(); // 是否为空v.clear(); // 清空v.front(); // 第一个元素v.back(); // 最后一个元素v.push_back(x); // 尾部插入v.pop_back(); // 尾部弹出v.begin()/v.end(); // 迭代器v[i]; // 随机访问

deque

概念：双端队列，支持两端高效插入/删除。
场景：既需要随机访问，又可能在前端频繁插入/删除。
常用接口：

deque<int> dq; // 声明一个 int 类型的双端队列dq.push_back(1);  // 在尾部插入元素 1dq.push_front(2); // 在头部插入元素 2int df = dq.front(); // 访问头部元素int db = dq.back(); // 访问尾部元素dq.pop_back(); // 弹出尾部元素dq.pop_front(); // 弹出头部元素size_t dqs = dq.size(); // 获取大小bool dq_empty = dq.empty();// 检查是否为空dq.clear(); // 清空所有元素auto dqb = dq.begin(); // 获取首元素迭代器auto dqend = dq.end(); // 获取尾后迭代器int d0 = dq[0]; // 通过下标访问元素

string

概念：字符序列专用容器，兼具vector能力，并提供丰富字符串操作。
场景：文本处理与拼接。
常用接口：

string s = \"Hello, STL!\"; // 声明并初始化字符串size_t len = s.size(); // 获取字符长度size_t len2 = s.length(); // length() 等价于 size()bool str_empty = s.empty(); // 检查是否为空串s.clear();  // 清空字符串内容string sub = s.substr(0,5); // 获取从下标 0 开始、长度为 5 的子串const char* cstr = s.c_str(); // 获取 C 风格字符串指针

容器适配器

在底层容器基础上，封装出特殊的接口限制。

stack

概念：后进先出（LIFO）结构。
常用接口：

stack<int> st;  // 声明一个 int 类型的栈st.push(8);  // 将 8 压入栈顶int stt = st.top(); // 访问栈顶元素st.pop();  // 弹出栈顶元素size_t sts = st.size(); // 获取栈大小bool st_empty = st.empty(); // 检查是否为空

queue

概念：先进先出（FIFO）结构。
常用接口：

queue<int> q; // 声明一个 int 类型的队列q.push(5);  // 在队尾插入元素 5int qf = q.front(); // 访问队头元素int qb = q.back();  // 访问队尾元素q.pop();  // 弹出队头元素size_t qs = q.size(); // 获取队列大小bool q_empty = q.empty(); // 检查是否为空

priority_queue

概念：堆结构（默认大根堆）。
小根堆示例：priority_queue<int, vector, greater> minHeap;
常用接口：

priority_queue<int> pq; // 默认大根堆pq.push(3);// 插入元素 3int top1 = pq.top(); // 获取堆顶（最大值）pq.pop(); // 删除堆顶元素size_t pqs = pq.size(); // 获取大小bool pq_empty = pq.empty(); // 检查是否为空// 定义最小堆priority_queue<int, vector<int>, greater<int>> min_pq; // 指定 greater 作为比较器

关联式容器

基于平衡二叉树（红黑树）实现，维护有序元素集合，所有操作均为$O(logn)$。

set / multiset

概念：set 中元素唯一，multiset 可重复。
常用接口：

set<int> s1;  // 声明一个不重复的有序集合s1.insert(5);  // 插入元素 5auto it_s = s1.find(5); // 查找元素 5size_t cnt5 = s1.count(5); // 统计值为 5 的元素个数s1.erase(5);  // 删除所有值为 5 的元素auto lb = s1.lower_bound(3); // 第一个 ≥ 3 的位置auto ub = s1.upper_bound(3); // 第一个 > 3 的位置multiset<int> ms; // 声明一个可重复的有序集合ms.insert(5);  // 插入元素 5（可重复）ms.erase(ms.begin()); // 根据迭代器删除单个元素

map / multimap

概念：键-值对，有序映射。map键唯一，multimap可重复。
常用接口：

map<string,int> mp;  // 键为 string、值为 int 的映射mp[\"apple\"] = 3;// 下标插入或访问mp.insert({\"banana\",5});  // insert 插入键值对auto it_mp = mp.find(\"banana\"); // 查找键为 \"banana\"if (it_mp != mp.end()) { int v = it_mp->second; // 访问对应值}mp.erase(\"apple\");  // 删除键为 \"apple\"auto lbm = mp.lower_bound(\"apple\"); // 第一个键 ≥ \"apple\"auto ubm = mp.upper_bound(\"apple\"); // 第一个键 > \"apple\"multimap<string,int> mmp; // 可重复键的映射mmp.insert({\"key\",1}); // 插入一对键值

无序容器

基于哈希表实现，实现均摊$O(1)$的增删改查；不维护顺序。

unordered_set<T> / unordered_multiset<T>unordered_map<Key,T> / unordered_multimap<Key,T>

unordered_set<int> us; // 声明一个无序集合us.insert(10);  // 插入元素 10auto it_us = us.find(10); // 查找元素 10us.erase(10);  // 删除元素 10size_t usn = us.size(); // 获取大小bool us_empty = us.empty(); // 检查是否为空unordered_map<string,int> um; // 键值对无序映射um[\"k\"] = 100;  // 插入或访问auto it_um = um.find(\"k\"); // 查找键为 \"k\"

轻量辅助类型

pair

概念：存储两个元素的简单结构，支持字典序比较。
成员：first、second；可用于map或算法返回值。

pair<int,int> p{10,20}; // 声明并初始化一个 int 二元组int u = p.first; // 访问第一个元素int v = p.second; // 访问第二个元素pair<int,int> q = {10,20}; // 同样的列表初始化bool eq = (p == q); // 比较两个 pair 是否相等bool lt = (p < q);  // 按 first, 再按 second 字典序比较

bitset

概念：定长位集，高效位运算。

bitset<10000> bs; // 声明大小为 10000 的位集bs.set();  // 将所有位设为 1bs.reset();  // 将所有位重置为 0bs.flip();  // 对所有位取反bs.set(5, true); // 将第 5 位设为 1bs.flip(5);  // 对第 5 位取反bool any1 = bs.any(); // 是否存在至少一个 1bool none1 = bs.none(); // 是否所有位均为 0size_t cnt1 = bs.count(); // 统计 1 的个数bool b5 = bs[5]; // 访问第 5 位的值