【算法模版】数据结构模版

C++ STL简介

vector

• 变长数组，采用倍增的思想。
• size(): 返回元素个数。
• empty(): 返回是否为空。
• clear(): 清空容器。
• front()/back(): 返回第一个/最后一个元素。
• push_back()/pop_back(): 在尾部插入/删除一个元素。
• begin()/end(): 返回迭代器指向容器的起始/末尾位置。
• []: 支持下标访问，按照顺序访问元素。
• 支持比较运算，按照字典序排序。

pair

• 存储一对值，通常用于存储一对相关联的数据。
• first: 第一个元素。
• second: 第二个元素。
• 支持比较运算，以first为第一关键字，以second为第二关键字（按照字典序）。

string

• 字符串容器。
• size()/length(): 返回字符串长度。
• empty(): 返回是否为空。
• clear(): 清空字符串。
• substr(start, length): 返回子串。
• c_str(): 返回字符串所在字符数组的起始地址。

queue

• 队列容器。
• size(): 返回队列中元素个数。
• empty(): 返回是否为空。
• push(val): 向队尾插入一个元素。
• front(): 返回队头元素。
• back(): 返回队尾元素。
• pop(): 弹出队头元素。

priority_queue

• 优先队列容器，默认是大根堆。
• size(): 返回优先队列中元素个数。
• empty(): 返回是否为空。
• push(val): 插入一个元素。
• top(): 返回堆顶元素。
• pop(): 弹出堆顶元素。
• 可以定义成小根堆的方式：priority_queue<int, vector<int>, greater<int>> q;。

stack

• 栈容器。
• size(): 返回栈中元素个数。
• empty(): 返回是否为空。
• push(val): 向栈顶插入一个元素。
• top(): 返回栈顶元素。
• pop(): 弹出栈顶元素。

deque

• 双端队列容器。
• size(): 返回双端队列中元素个数。
• empty(): 返回是否为空。
• clear(): 清空双端队列。
• front()/back(): 返回第一个/最后一个元素。
• push_back()/pop_back(): 在尾部插入/删除一个元素。
• push_front()/pop_front(): 在头部插入/删除一个元素。
• begin()/end(): 返回迭代器指向容器的起始/末尾位置。
• []: 支持下标访问，按照顺序访问元素。

set, map, multiset, multimap

• 基于平衡二叉树（红黑树）的动态维护有序序列容器。
• size(): 返回容器中元素个数。
• empty(): 返回是否为空。
• clear(): 清空容器。
• begin()/end(): 返回迭代器指向容器的起始/末尾位置。
• ++, --: 返回前驱和后继，时间复杂度 O(logn)。
• insert(): 插入一个元素。
• find(): 查找一个元素。
• count(): 返回某个元素的个数。
• erase(): 删除元素，支持输入一个元素值或一个迭代器。
• lower_bound()/upper_bound(): 返回大于等于/大于某个值的最小元素的迭代器。

unordered_set, unordered_map, unordered_multiset, unordered_multimap

• 哈希表容器。
• 增删改查的时间复杂度是 O(1)。
• 不支持 lower_bound()/upper_bound()，迭代器的 ++, --。

bitset

• 位集合容器，用于处理位操作。
• bitset<10000> s;
• 支持位运算操作 ~, &, |, ^, >>, <<.
• 支持比较操作 ==, !=.
• 支持 [] 访问操作。
• count(): 返回有多少个1。
• any(): 判断是否至少有一个1。
• none(): 判断是否全为0。
• set(): 把所有位设置为1。
• set(k, v): 将第k位设置为v。
• reset(): 把所有位设置为0。
• flip(): 对所有位取反，等价于 ~。
• flip(k): 对第k位取反。

STL模拟实现模版

单链表 —— 模板

单链表是一种常见的链式数据结构，每个节点包含一个数据元素和一个指向下一个节点的指针。单链表的模板实现包括三个关键操作：初始化、在链表头插入元素和删除头结点。

• 初始化：设定头结点指针为 -1，表示链表为空；初始化节点数组的下标 idx 为 0，表示当前未使用任何节点。
• 在链表头插入元素：将新元素插入到节点数组的 idx 位置，更新 idx，然后将 head 指针指向新插入的节点，并将新节点的 next 指针指向原来的头结点。
• 删除头结点：将 head 指针指向头结点的下一个节点。

// head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点
int head, e[N], ne[N], idx;

// 初始化
void init()
{
    head = -1;
    idx = 0;
}

// 在链表头插入一个数a
void insert(int a)
{
    e[idx] = a, ne[idx] = head, head = idx++;
}

// 将头结点删除，需要保证头结点存在
void remove()
{
    head = ne[head];
}

双链表 —— 模板

双链表是链表的一种扩展，每个节点除了包含数据元素外，还包含指向前一个节点和后一个节点的指针。双链表的模板实现同样包括初始化、在指定位置插入元素和删除指定位置节点。

• 初始化：设定左端点 l[1] 和右端点 r[0]，并设置数组下标 idx 初始值为 2。
• 在指定位置插入元素：新元素插入到节点数组的 idx 位置，更新 idx，然后更新该节点的 left 和 right 指针，使其与前后节点相连接。
• 删除指定位置节点：更新被删除节点的前后节点的 left 和 right 指针，使其相连接。

// e[]表示节点的值，l[]表示节点的左指针，r[]表示节点的右指针，idx表示当前用到了哪个节点
int e[N], l[N], r[N], idx;

// 初始化
void init()
{
    //0是左端点，1是右端点
    r[0] = 1, l[1] = 0;
    idx = 2;
}

// 在节点a的右边插入一个数x
void insert(int a, int x)
{
    e[idx] = x;
    l[idx] = a, r[idx] = r[a];
    l[r[a]] = idx, r[a] = idx++;
}

// 删除节点a
void remove(int a)
{
    l[r[a]] = l[a];
    r[l[a]] = r[a];
}

栈 —— 模板

栈是一种先进后出（FILO）的数据结构，只允许在一端进行插入和删除操作。栈的模板实现包括向栈顶插入元素、从栈顶弹出元素和判断栈是否为空。

• 向栈顶插入元素：将新元素插入到栈顶，更新栈顶指针。
• 从栈顶弹出元素：将栈顶指针向下移动一个位置。
• 判断栈是否为空：通过栈顶指针的位置判断栈是否为空。

// tt表示栈顶
int stk[N], tt = 0;

// 向栈顶插入一个数
stk[++tt] = x;

// 从栈顶弹出一个数
tt--;

// 栈顶的值
stk[tt];

// 判断栈是否为空，如果 tt > 0，则表示不为空
if (tt > 0)
{
}

队列 —— 模板

队列是一种先进先出（FIFO）的数据结构，允许在队尾插入元素，在队头删除元素。队列的模板实现包括普通队列和循环队列。

• 普通队列：使用队头和队尾指针来维护队列，插入元素时更新队尾指针，删除元素时更新队头指针。
• 循环队列：使用队头和队尾指针以及数组的循环利用特性来维护队列，插入元素和删除元素时通过循环更新指针位置。

1. 普通队列：

// hh 表示队头，tt表示队尾
int q[N], hh = 0, tt = -1;

// 向队尾插入一个数
q[++tt] = x;

// 从队头弹出一个数
hh++;

// 队头的值
q[hh];

// 判断队列是否为空，如果 hh <= tt，则表示不为空
if (hh <= tt)
{
}

2. 循环队列：

// 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 tt = 0;
for (int i = 1; i <= n; i++)
{
    while (tt && check(stk[tt], i))
        tt--;
    stk[++tt] = i;
}

单调队列 —— 模板

单调队列是一种特殊的队列结构，用于解决一些滑动窗口中的最大值或最小值的问题。单调队列的模板实现包括维护一个单调递增或单调递减的队列和循环遍历数组的过程。

• 模板思路：遍历数组，维护一个单调递增或单调递减的队列，当队尾元素小于当前元素时，将队尾元素出队，直到队尾元素大于等于当前元素，然后当前元素入队；同时，判断队头元素是否滑出窗口范围，若是则将队头元素出队。

// 常见模型：找出滑动窗口中的最大值/最小值
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 算法用于在一个主串中查找一个模式串的出现位置，其核心是利用模式串内部的信息来跳过不必要的比较。KMP 算法的模板实现包括两个关键步骤：计算模式串的 Next 数组和匹配过程。

• 计算模式串的 Next 数组：Next 数组用于记录模式串中每个位置的最长相同前缀后缀的长度。通过遍历模式串，逐步计算 Next 数组。
• 匹配过程：利用 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 树的模板实现包括两个关键操作：插入和查询。

• 插入操作：从根节点开始，按照字符串的每个字符依次插入到 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];
}

并查集 —— 模板

并查集是一种用于处理集合合并与查询连通性的数据结构，通常用于解决图论中的动态连通性问题。并查集的模板实现包括三种常见形式：朴素并查集、维护集合大小的并查集和维护到祖宗节点距离的并查集。

• 朴素并查集：每个节点指向其所在集合的祖宗节点，通过路径压缩和按秩合并优化。
• 维护集合大小的并查集：在朴素并查集的基础上，额外维护每个祖宗节点所在集合的大小。
• 维护到祖宗节点距离的并查集：在朴素并查集的基础上，额外维护每个节点到其祖宗节点的距离。

1. 朴素并查集：

int p[N]; //存储每个点的祖宗节点

// 返回x的祖宗节点
int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

// 初始化，假定节点编号是1~n
for (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~n
for (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~n
for (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)的偏移量

堆 —— 模板

堆是一种特殊的树形数据结构，常用于实现优先队列。堆的模板实现包括两种基本操作：向上调整和向下调整。

• 向上调整：将一个新元素插入到堆中后，可能会破坏堆的性质，需要通过向上调整来修复堆，保持其性质不变。
• 向下调整：在删除堆顶元素或者修改堆顶元素值后，可能会破坏堆的性质，需要通过向下调整来修复堆，保持其性质不变。

// 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);

一般哈希 —— 模板

一般哈希是一种常见的哈希表实现方式，包括拉链法和开放寻址法两种方法。

• 拉链法：利用数组和链表结合实现哈希表，解决哈希冲突的方法是在数组的每个位置上维护一个链表，将哈希值相同的元素放入同一个链表中。
• 开放寻址法：利用数组实现哈希表，解决哈希冲突的方法是当发生冲突时，顺序地向后寻找下一个空位置，直到找到合适的位置。

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进制数，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];
}

详细练习AcWing题目：
单链表 —— 模板题 (AcWing 826. 单链表)
双链表 —— 模板题 (AcWing 827. 双链表)
栈 —— 模板题 (AcWing 828. 模拟栈)
队列 —— 模板题 (AcWing 829. 模拟队列)
单调栈 —— 模板题 (AcWing 830. 单调栈)
单调队列 —— 模板题 (AcWing 154. 滑动窗口)
KMP —— 模板题 (AcWing 831. KMP字符串)
Trie树 —— 模板题 (AcWing 835. Trie字符串统计)
并查集 —— 模板题 (AcWing 836. 合并集合, AcWing 837. 连通块中点的数量)
堆 —— 模板题 (AcWing 838. 堆排序, AcWing 839. 模拟堆)
一般哈希 —— 模板题 (AcWing 840. 模拟散列表)
字符串哈希 —— 模板题 (AcWing 841. 字符串哈希)