📦数据结构

备注：基于 Acwing 的 irai 个人笔记记录

一、单链表

模板题：826. 单链表
示例代码：

c++

// 使用数组来实现静态的单链表
#include <iostream>

using namespace std;

const int N = 1e5 + 10;

// head 头节点, e[] 数据域, ne[] 指针域, idx 将要操作的下标 
int head, e[N], ne[N], idx;

// 初始化
void init(){
    head = -1;  // 一开始头节点指向 -1 (NULL)
    idx = 0;    // 将要操作的下标为 0
}

// 向链表头插入一个数
void insert_to_head(int x){
    // 给新节点赋值 x
    e[idx] = x;
    // 新节点指向头节点指向的位置
    ne[idx] = head;
    // 头节点指向新节点
    head = idx;
    // 更新将要操作的下标
    idx ++;
}

// 删除第 k 个插入的数后面的一个数
void remove_behind_k(int k){
    // 第一个插入的数下标为 0
    // 第 k 个插入的数下标为 k - 1 
    ne[k - 1] = ne[ne[k - 1]]; // 指向后面的节点指向的节点就实现删除后一个
}

// 在第 k 个插入的数后插入一个数
void insert_behind_k(int k, int x){
    // 第一个插入的数下标为 0
    // 第 k 个插入的数下标为 k - 1
    e[idx] = x;
    // 新节点指向第 k 个插入的节点指向的节点
    ne[idx]  = ne[k - 1];
    // 第 k 个插入的节点指向新节点
    ne[k - 1] = idx ++;
}

// 打印链表
void print(int head){
    for(int i = head; i != -1; i = ne[i]){
        cout << e[i] << ' ';
    }
    cout << endl;
}

int main()
{
    // 操作次数 m 
    int m;
    cin >> m;
    
    // 初始化
    init();
    
    while( m -- ){
        // m 行操作
        char op[2];
        int x, k;
        cin >> op;
        if(op[0] == 'H'){
            // 向链表头插入一个数 x
            cin >> x;
            insert_to_head(x);
            
        }else if(op[0] == 'D'){
            // 删除第 k 个插入的数后面的一个数
            cin >> k;
            // 删除首元节点
            if(k == 0){
                head = ne[head];
                continue;
            }
            remove_behind_k(k);
            
        }else if(op[0] == 'I'){
            // 在第 k 个插入的数后面插入一个数 x
            cin >> k >> x;
            insert_behind_k(k,x);
        }
    }
    
    // 打印链表
    print(head);
    
    return 0;
}

二、双链表

三、栈

四、队列

五、单调栈

场景：找到某一个数左边或者右边离它最近的数且满足某个属性（如比它大或小...）的数
模板题：830. 单调栈
示例代码：

c++

#include <iostream>
#include <vector>

using namespace std;

const int N = 1e5 + 10;
int n,stk[N],tt;

int main()
{
    // 目的: 输出每个数左边第一个比它小的数
    // 思路: 维护一个单调栈，使得单调递增
    // 原因: 如果存在逆序对，即位置在前面但是值反而更大
    // 那么前面这个值更大的只要有右边这个小数的存在，就永远轮不到它
    // 做法: 依次进栈，while当前元素小于等于栈顶，那么pop栈顶,
    // 比栈顶大，那么输出栈顶(左边第一个比它小的数)
    cin >> n;
    while( n -- ){
        int x;
        cin >> x;
        while(tt && stk[tt] >= x) tt --;
        // 如果栈不空的话：现在是单调递增的，且栈顶就是第一个比x小的数
        if(tt) cout << stk[tt] << ' ';
        else cout << -1 << ' ';
        // 记得元素要进栈
        stk[ ++ tt ] = x;
    }
    
    return 0;
}

六、单调队列

场景：输出滑动窗口的最大值或最小值
模板题：154. 滑动窗口
示例代码：

c++

#include <iostream>

using namespace std;

const int N = 1e6 + 10;
int n, k, a[N], q[N], hh, tt;

int main()
{
    // 数组长度和滑动窗口长度
    cin >> n >> k;
    //接收输入
    for(int i = 0; i <  n; i ++ ) scanf("%d", &a[i]);

    // 找最小值
    // 初始化队列
    hh = 0, tt = -1;
    // 滑动窗口遍历
    for(int i = 0; i < n; i ++ ){
        // 如果队列不空，并且队头超出(索引上体现小于)了窗口大小就出队
        if(hh <= tt && i - k + 1 > q[hh]) hh ++;
        //保证是单调队列: 保证队列不空的情况下是单调递增的
        // 单调递增的队列，那么队首就是要找的最小值
        // 也就是说，一旦队尾是大于等于将要进来的数的，那么 tt --
        // 更直观的说法：只要将进来的数存在，那么它一定是比当前队尾是作为最小值更好的选择
        while(hh <= tt && a[q[tt]] >= a[i]) tt --;
        // 保证单调性进入窗口
        q[ ++ tt ] = i;
        // 窗口大于队列长度再输出: 一开始有一段还不需要输出
        if(i - k + 1 >= 0) printf("%d ", a[q[hh]]);
    }
    cout << endl;

    // 找最大值
    hh = 0, tt = -1;
    // 滑动窗口遍历
    for(int i = 0; i < n; i ++ ){
        // 如果队列不空，并且队头超出(索引上体现小于)了窗口大小就出队
        if(hh <= tt && i - k + 1 > q[hh]) hh ++;
        //保证是单调队列: 保证队列不空的情况下是单调递减的
        // 单调递减的队列，也就是队首就是最大值
        // 也就是说，一旦队尾是小于等于将要进来的数的则 tt --
        // 更直观的说法: 只要将进来的数存在，那么它一定是比当前队尾作为最大值更好的选择
        while(hh <= tt && a[q[tt]] <= a[i]) tt --;
        // 保证单调性进入窗口
        q[ ++ tt ] = i;
        // 窗口大于队列长度再输出: 一开始有一段还不需要输出
        if(i - k + 1 >= 0) printf("%d ", a[q[hh]]);
    }
    return 0;
}

七、KMP

八、Trie

Trie 树（字典树 / 前缀树）：用于高效地存储和查找字符串集合的数据结构

8.1 Trie 字符串

模板题：835. Trie字符串统计
示例代码：

c++

#include <iostream>
using namespace std;
const int N = 1e5 + 10;

// son[][] : 第一维度表示所有可能的节点，第二个维度对应的是第一个维度26个可能的子节点
// cnt[] : 表示以这个节点为字符串结尾的字符串数量
// idx : 下一个要操作的节点位置
// son 里下标是 0 的点即是根节点也是空节点
int son[N][26], cnt[N], idx;       
char str[N];    // 读入的字符串

// 把 str 这个字符串插入到 Trie 树
void insert(char str[]){
    int p = 0;  // 从下标为 0 的根节点开始找
    for(int i = 0; str[i]; i ++ ){
        // 把一个 a ~ z 的字符映射到 0 ~ 25
        int u = str[i] - 'a';
        // 如果没有这条路，那么建一条路(因为是插入操作)
        if(!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];   // 走去下一个位置
    }
    // 走到最后，在结尾做一个标记，意思为这个位置结尾的字符串的数量
    cnt[p] ++;
}

// return 字符串 str 在 Trie 树中出现的次数 
int query(char str[]){
    int p = 0;
    for(int i = 0; str[i]; i ++ ){
        int u = str[i] - 'a';
        // 在这里是查找操作，如果没这条路说明就没有这个字符串
        // 返回这个字符串的数量为 0 
        if(!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}

int main()
{
    int n;  // n 次操作
    cin >> n;
    char op[2]; // 操作指令
    while( n -- ){
        cin >> op >> str;
        if(op[0] == 'I') insert(str);
        else cout << query(str) << endl;
    }
    
    return 0;
}

8.2 最大异或对

模板题：143. 最大异或对
示例代码：

c++

#include <iostream>
using namespace std;

// 每一个整数都是小于 2^31, 那么也就说明每一个数都是一个 31 位的二进制数
const int N = 1e5 + 10, M = 31 * N;

int son[M][2], idx;
int a[N];

// 把 x 插入到 Trie 树 中
void insert(int x){
    int p = 0;
    for(int i = 30; i >= 0; i --){
        int u = x >> i & 1; // 取x二进制表示时第i位数是什么
        // 没有这个方向就建出来
        if(!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];  // 走去下一步
    }
}

// 返回目前 Trie 树中与 x 异或最大的数
int query(int x){
    int p = 0, res = 0;
    for(int i = 30; i >= 0; i -- ){
        int u = x >> i & 1; 
        if(son[p][!u]){
            // 尽量走不同数的方向，异或的结果才大
            p = son[p][!u];
            res = (res << 1) + !u;
        }else{
            // 将就唯有的方向
            p = son[p][u];
            res = (res << 1) + u;
        }
    }
    return res;     // res 就是 Trie 中与传入的 x 异或最大的数
}

int main()
{
    int n;
    scanf("%d", &n);
    // 存入 n 个整数
    for(int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    
    int res = 0;    // 初始化异或最大的结果
    // 边插入 Trie 树 边查找异或最大的结果
    for(int i = 0; i < n; i ++ ){
        // 先插入后查找可以不需要我们写当 Trie 树空的时候的边界情况
        insert(a[i]);
        int t = query(a[i]);    // 这个 t 就是当前 Trie 里面和 a[i] 异或最大的
        res = max(res, a[i] ^ t);   // 更新 res
    }
    printf("%d", res);
    
    return 0;
}

九、并查集

9.1 合并集合

模版题：836. 合并集合
示例代码：

c++

#include <iostream>
using namespace std;

const int N = 1e5 + 10; 
int n, m;
int p[N]; // 记录每个点的祖宗节点(从 1 开始)

// 返回节点 u 的祖宗节点 + 路径压缩
int find(int u){
    if(p[u] != u) p[u] = find(p[u]);
    return p[u];
}

int main()
{
    // 编号 1 ~ n 的 n 个数
    cin >> n >> m;
    
    // 初始化并查集(一开始都指向自己)
    for(int i = 1; i <= n; i ++ ) p[i] = i;
    
    while( m -- ){
        // m 行操作指令
        int a, b;
        char op[2];
        cin >> op;
        cin >> a >> b;
        if(*op == 'M'){
            if(find(a) != find(b)) p[find(a)] = find(b);
        }else{
            if(find(a) == find(b)) puts("Yes");
            else puts("No");
        }
    }
    
    return 0;
}

9.2 连通块点的数量

模板题：837. 连通块中点的数量
核心：在并查集的基础上多维护一下每个连通块的数量
示例代码：

c++

#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int n, m;
int p[N]; // 存储每个点的祖宗节点
int sz[N];  // 如果这个点是祖宗节点，那么sz是它这个连通块中点的数量

// 返回节点 u 的祖宗节点 + 路径压缩
int find(int u){
    if(p[u] != u) p[u] = find(p[u]);
    return p[u];
}

int main()
{
    cin >> n >> m;
    
    // 初始化并查集
    for(int i = 1; i <= n; i ++ ){
        // 都指向自己
        p[i] = i;
        // sz 都是 1
        sz[i] = 1;
    }
    
    while( m -- ){
        // m 行操作
        char op[5];
        int a, b;
        cin >> op;
        if(op[0] == 'C'){
            cin >> a >> b;
            if(find(a) == find(b)) continue;
            // 把 a 的祖宗接到 b 的祖宗上，所以是 b 的祖宗的 sz 增加
            sz[find(b)] += sz[find(a)];
            p[find(a)] = find(b);
        }else if(op[1] == '1'){
            cin >> a >> b;
            if(find(a) == find(b)) cout << "Yes" << endl;
            else cout << "No" << endl;
        }else{
            cin >> a;
            cout << sz[find(a)] << endl;
        }
    }
    
    return 0;
}

9.3 食物链

模板题：240. 食物链
核心：在并查集的基础上，多维护每个节点与根节点的距离
- 思路换为：如果动物有关系就合并到一个集合
- 因为是三种动物的关系，所有集合内的点就可以通过 距离 % 3 分为三大类
- 1). d % 3 == 0 ：与根节点是同类
- 2). d % 3 == 1 ：可以吃根节点
- 1. d % 3 == 2 ：可以被根节点吃
示例代码：

c++

#include <iostream>
using namespace std;

const int N = 50010;
int n, m;
int p[N];   // 存储每个点的祖宗节点是谁
int d[N];   // 存储每个点离父节点的距离,在经过路径压缩后就是离根节点的距离

// 返回节点 u 的祖宗节点 + 维护d[] + 路径压缩
int find(int u){
    if(p[u] != u){
        int t = find(p[u]); // 先记录下p[u]的祖宗节点
        d[u] += d[p[u]]; // u离根节点(新父节点)的距离 = u离旧父节点的距离 + 旧父节点离根节点的距离
        p[u] = t;   // u 的祖宗节点是 之前记录的 p[u] 的祖宗节点
    }
    return p[u];
}

int main()
{
    cin >> n >> m;
    
    // 初始化并查集
    for(int i = 1; i <= n; i ++ ) p[i] = i;
    // 初始化 d[] 都是离根节点的距离，一开始都是距离自己，那么距离是 0
    // 又因为 d[] 是在堆空间初始化的，所以默认值就是 0 ，不用操作
    
    int res = 0; // 记录假话的总数
    while( m -- ){
        int t, x, y;
        cin >> t >> x >> y;
        if(x > n || y > n) res ++;
        else{
            int px = find(x), py = find(y);
            if(t == 1){
                // x 和 y 在一个集合里面
                // t == 1 这句话说 x 和 y 同类
                // 若 在 (dx - dy) 在 % 3 的时候是取 0 的话就是同类 
                // 那么也就是 (dx - dy) % 3 不是 0 的时候是假话
                if(px == py && (d[x] - d[y]) % 3) res ++;
                else if(px != py){
                    // x 和 y 不在一个集合里面
                    // t == 1 这句话说 x 和 y 同类
                    // 那么我们把 px 接到 py上
                    // 若记 px --> py 距离为 ?
                    // 那么 (dx + ? - dy) 在 % 3 的时候为 0
                    // 即我们需要把 ? 设置为 dy - dx
                    p[px] = py;
                    d[px] = d[y] - d[x];
                }
            }else if(t == 2){
                // x 和 y 在一个集合里面
                // t == 1 这句话说 x 吃 y
                // 那么也就说明 (dx - dy - 1) % 3 == 0 的
                // 若 (dx - dy - 1) % 3 != 0 的话是假话
                if(px == py && (d[x] - d[y] - 1) % 3) res ++;
                else if(px != py){
                    // x 和 y 不在一个集合里面
                    // 那么我们把 px 接到 py上
                    // 若记 px --> py 距离为 ?
                    // 那么 (dx + ? - dy - 1) 在 % 3 的时候为 0
                    // 则我们需要设置 ? 为 dy - dx + 1
                    p[px] = py;
                    d[px] = d[y] - d[x] + 1;
                }
            }
        }
    }
    
    cout << res << endl;
    
    return 0;
}

十、堆

10.1 概述

📌 堆是什么？
- 逻辑结构：
  - 一颗【完全二叉树】 , 满足堆序性
  - 小根堆：父亲 <= 儿子；大根堆：父亲 >= 儿子
- 物理结构：
  - 使用定长或动态数组存储，这里使用定长数组存储，使用 下标 1 作为根
  - 对于下标 i ：（可以发现是因为我们根节点从 1 开始才满足下述）
    - 父亲：i / 2
    - 左儿子：2 * i
    - 右儿子：2 * i + 1
  - 完全二叉树保证除最后一层外全满，最后一层从左向右填，所以数组没有空洞。

堆的两个核心的原子操作（小根堆）：
- down() ：O(log n)
  把某个位置 i 的元素 x 不断与孩子比较，若孩子更小就把孩子提上来，
  x 沉下去，直到叶或两个孩子都比 x 大。
- up() ： O(log n)
  把末尾新元素 x 不断与父亲比较，若 x 更小就交换，直到根或父亲 ≤ x 。

实现五个操作：
- 1). 插入一个数：在最后插入一个数，然后 up 上去
- 2). 求集合当中的最小值：返回根节点 head[1]
- 3). 删除最小值：把最后一个数与根节点交换，size-- , 然后根节点位置 down 下去
- 4). 删除任意一个元素：把第 k 个数与最后一个数交换，size-- , 然后第 k 个数的位置 down;up
- 5). 修改任意一个元素：把第 k 个数修改成 x，down;up

一个 O(n) 的建堆操作：
对于一个完全二叉树来说，i <= [ n / 2] 为分支节点，i > [ n / 2 ] 为叶子结点
那么可以发现 n / 2 就是最后一个分支节点，我们可以从它开始 down() , 它 down() 完
后它的子树就满足的堆序性，那么到它前一个节点 down() ，以此类推，一直 down()
到根节点为止，就可以完成建堆过程，并且时间复杂度是 O(n) 的。

c++

// 建堆(从最后一个非叶子节点 n/2 ,一直down 到 1 )
for(int i = n / 2; i >= 1; i -- ) down(i);

10.2 堆排序

模板题 : 838. 堆排序
示例代码：

c++

#include <iostream>

using namespace std;

const int N = 1e5 + 10;
// 长度为 n 的整数序列，从小到大输出前 m 小的数
int n, m, sz;
// 使用数组来存储堆
int h[N];

void down(int u){
    int t = u; // t 用来存储局部三个数的最小值
    // 如果有左儿子，并且左儿子比 t 小 
    if(u * 2 <= sz && h[u * 2] < h[t]) t = u * 2;
    // 如果有右儿子，并且右儿子比 t 小
    if(u * 2 + 1 <= sz && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    // 现在 t 就是局部里最小的值，如果 t 不是 u 的话说明发生了交换
    if(t != u){
        swap(h[t],h[u]);
        // 继续 down 下去
        down(t);
    }
}

int main()
{
    cin >> n >> m;
    sz = n;
    
    // 输入整数序列 (从 1 开始存储)
    for(int i = 1; i <= n; i ++ ) scanf("%d", &h[i]);
    
    // 建堆， 从最后一个非叶子节点 n / 2, 一直 down 到 1
    for(int i = n / 2; i >= 1; i -- ) down(i);
    
    while( m -- ){
        // 输出前 m 小的数
        cout << h[1] << ' ';
        
        // 删除堆顶
        h[1] = h[sz];
        sz --;
        down(1);
    }
    
    return 0;
}

10.3 模拟堆

在竞赛 / 面试里，经常会遇到这样的需求：
不是删除 “值等于 x” 的元素，而是删除 “第 k 个被插入的元素” （k 是插入顺序，从 1 开始），
或者把 “第 k 个插入的数” 改成新值。
这时就必须把「插入时间戳」和「堆数组下标」双向映射起来。
两个辅助数组 ph[] 和 hp[] 就是干这件事的，它们的名字来自《算法竞赛进阶指南》
- ph： pointer-to-heap，下标是 “第 k 次插入”，值是 “当前在 heap 中的下标” ；
- hp：heap-to-pointer，下标是 “heap 中的下标” ，值是 “第几次插入”。

有了这对互逆映射，我们就可以在 O(1) 拿到 “第 k 个插入” 的元素在堆里的真实位置

❓ 很多同学会有如下疑惑：那我需要找到第几个插入的数，不就 ph 就好了吗？为什么还要 hp 呢？
- 答：当我们需要交换两个数的时候，首先很容易想到的是，我们不仅要交换他们的值，而且
  为了确保我们能通过 ph 找到正确的下标，那么 ph 也要同步进行 swap 。但是仔细想想
  ph 的定义，是根据 第 k 次插入的值 来寻找在堆里的下标的，那么我们从何得知某个数
  是第几次插入的呢？？？那么这就是这个反向映射数组 hp 的作用了。那么在后面进行交换
  的时候我们就会用到下面这个看起来好像很难懂的代码，其实就是我们刚刚解释的：
c++
```
// hp[a] : 找到 a 这个值是第几次插入的
// ph[hp[a]] : 根据 a 是第几次插入的找到 a 在 heap 中的下标
// 那么下面这句代码就说明: 我们交换了a b的值，那么他们在heap 中的下标也交换
swap(ph[hp[a]],ph[hp[b]])
```
1
2
3
4
同时如果有这两个辅助数组，我们就要维护这两个数组，也就说明当我们进行 swap 的
时候就不能简单 swap 了，因为这改变了这个数在 heap 中的下标，同时映射回去是第
几次插入也要做相应 swap , 那么就得有一套全新的交换方式：

c++

// 交换 h[a] 与 b[b]
void heap_swap(int a, int b){   
    swap(ph[hp[a]], ph[hp[b]]);
    swap(hp[a],hp[b]);
    swap(h[a], h[b]);
}

模板题：839. 模拟堆
示例代码：

c++

#include <iostream>
#include <algorithm>
#include <string.h>

using namespace std;
const int N = 1e5 + 10;
// n 次操作，m 记录第几个插入的，sz 记录堆大小
int n, m, sz;
// ph : pointer-to-heap : 下标是 “第 k 次插入”，值是 “当前在 heap 中的下标”
// hp : heap-to-pointer : 下标是 “heap 中的下标” ，值是 “第几次插入”
int ph[N], hp[N];
int h[N];

// 交换 h[a] 与 b[b]
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 <= sz && h[u * 2] < h[t]) t = u * 2;
    if(u * 2 + 1 <= sz && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if(t != u){
        heap_swap(t, u);
        down(t);
    }
}

void up(int u){
    while(u / 2  && h[u] < h[u / 2]){
        // 父节点更大，那么孩子可以 up 上去
        heap_swap(u, u / 2);
        u /= 2;
    }
}

int main()
{
    scanf("%d", &n);
    int k, x;
    char op[10];
    while( n -- ){
        scanf("%s", op);
        if(!strcmp(op,"I")){
            // 插入一个数 x
            scanf("%d", &x);
            m ++;
            sz ++;
            ph[m] = sz;
            hp[sz] = m;
            // 插入到 sz，然后 up 上去
            h[sz] = x;
            up(sz);
            
        }else if(!strcmp(op, "PM")){
            // 输出当前集合中的最小值
            printf("%d\n", h[1]);
            
        }else if(!strcmp(op, "DM")){
            // 删除当前集合中的最小值
            heap_swap(1,sz);
            sz --;
            down(1);
            
        }else if(!strcmp(op, "D")){
            // 删除第 k 个插入
            scanf("%d", &k);
            k = ph[k];
            heap_swap(k, sz);
            sz --;
            down(k), up(k);
            
        }else if(!strcmp(op, "C")){
            // 修改第 k 个插入，将其变成 x
            scanf("%d %d", &k, &x);
            k = ph[k];
            h[k] = x;
            down(k), up(k);
        }
    }
    return 0;
}

十一、哈希表

11.1 概述

（哈希表）主要作用：用来快速判断一个元素是否出现集合里。
要枚举的话时间复杂度是 O(n)，但如果使用哈希表的话，只需要 O(1) 就可以做到。
当我们想使用哈希法来解决问题的时候，我们一般会选择如下三种数据结构
- 数组
- set 集合
- map 映射

数组就没什么好说的，下面看看 C++ STL 对于 set 和 map 提供的数据结构：

集合	底层实现	是否有序	数值是否可以重复	能否更改数值	查询效率	增删效率
`std::set`	红黑树	有序	否	否	`O(log n)`	`O(log n)`
`std::multiset`	红黑树	有序	是	否	`O(log n)`	`O(log n)`
`std::unordered_set`	哈希表	无序	否	否	`O(1)`	`O(1)`

std::unordered_set底层实现为哈希表，std::set 和 std::multiset 的底层实现是红黑树，
红黑树是一种平衡二叉搜索树，所以 key 值是有序的，但 key 不可以修改，改动 key 值
会导致整棵树的错乱，所以只能删除和增加。

集合	底层实现	是否有序	数值是否可以重复	能否更改数值	查询效率	增删效率
`std::map`	红黑树	key 有序	key 否	key 否	`O(log n)`	`O(log n)`
`std::multimap`	红黑树	key 有序	key 是	key 否	`O(log n)`	`O(log n)`
`std::unordered_map`	哈希表	key 无序	key 否	key 否	`O(1)`	`O(1)`

std::unordered_map 底层实现为哈希表，std::map 和 std::multimap 的底层实现是红黑树。
同理，std::map 和 std::multimap 的 key 也是有序的

📌 结论：对于 set 我们就用 unordered_set 来做哈希表，对于 map 就用 unundered_map 来做哈希表
因为这两个根据它的底层实现，在映射和取值的时候效率是最高的，而且它可以帮助我们自动去重

11.1 有效字母异位词

本题用于练习使用数组实现模拟哈希表
PS ：数组就是简单的哈希表，但是数组的大小可不是无限开辟的
题目链接：242. 有效的字母异位词
示例代码：

c++

class Solution {
public:
    bool isAnagram(string s, string t) {
        // 因为这道题是只包含小写字母 a~z ,那么可以映射到下标 0~25
        int h[26];  // 使用数组来模拟哈希表
        for(int i = 0; i < s.size(); i ++ )
            h[s[i] - 'a'] ++;
        for(int i = 0; i < t.size(); i ++ )
            h[t[i] - 'a'] --;
        // 再遍历模拟哈希表，如果全是 0 就说明 s ＆ t 是有效字母异位词
        for(int i = 0; i < 26; i ++ )
            if(h[i] != 0) return false;
        
        return true;
    }
};

11.2 两个数组的交集

本题用于练习使用 unordered_set
PS : 如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费！
题目链接：349. 两个数组的交集
示例代码：

c++

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> res_set;   // 存放交集的结果，使用哈希表可以去重
        // 可以传入迭代器来初始化一个哈希表
        unordered_set<int> nums_set(nums1.begin(), nums1.end());
        for(int i = 0; i < nums2.size(); i ++ ){
            if(nums_set.find(nums2[i]) != nums_set.end()){
                // find() 如果返回 end() 的话说明就是没找到
                // 那么如果不是 end() 就说明是交集部分，可以放入res
                res_set.insert(nums2[i]);
            }
        }
        // 最后再把交集转回vector返回
        vector<int> res(res_set.begin(), res_set.end());
        return res;
    }
};

11.3 两数之和

本题用于练习使用 unordered_map
- 题目链接：1. 两数之和
示例代码：

c++

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> mp;     // {遍历过的值, 这个值对应的下标}
        for(int i = 0; i < nums.size(); i ++ ){
            int s = target - nums[i];   // s 是我们需要在哈希表中找的值
            auto it = mp.find(s);
            if(it != mp.end()){
                // 说明 s 在哈希表中出现过，那么可以返回
                return {it -> second, i};
            }
            // 如果没找到匹配对，就把访问过的元素和下标加入到map中
            mp.insert({nums[i], i});
        }
        return {};
    }
};

📦数据结构 ​

一、单链表 ​

二、双链表 ​

三、栈 ​

四、队列 ​

五、单调栈 ​

六、单调队列 ​

七、KMP ​

八、Trie ​

8.1 Trie 字符串 ​

8.2 最大异或对 ​

九、并查集 ​

9.1 合并集合 ​

9.2 连通块点的数量 ​

9.3 食物链 ​

十、堆 ​

10.1 概述 ​

10.2 堆排序 ​

10.3 模拟堆 ​

十一、哈希表 ​

11.1 概述 ​

11.1 有效字母异位词 ​

11.2 两个数组的交集 ​

11.3 两数之和 ​

📦数据结构

一、单链表

二、双链表

三、栈

四、队列

五、单调栈

六、单调队列

七、KMP

八、Trie

8.1 Trie 字符串

8.2 最大异或对

九、并查集

9.1 合并集合

9.2 连通块点的数量

9.3 食物链

十、堆

10.1 概述

10.2 堆排序

10.3 模拟堆

十一、哈希表

11.1 概述

11.1 有效字母异位词

11.2 两个数组的交集

11.3 两数之和