Chapter 2 数据结构

知识

模板

1. 链表

int head; // 头指针: 指向一个node (init 时指向 NaN, -1)
int idx;  // 全局变量: 从 点集 中取点, 当前取到哪一个了

// 单链表
e[idx] = x; // 序号为idx的node, 值是x
ne[idx] = idx_nxt; // 序号为idx的node, 指向 序号为idx_nxt的node

// 双链表
e[idx] = x;
l[idx] = idx_left;
r[idx] = idx_right;

• 单链表
  • 初始化: init()
  • 头节点插入: add2head(x). "head_node" 指向 "值为x的node"
  • 中间节点插入: add(k, x). "序号为k的node" 后面加一个 "值为x的node"
  • 中间节点删除: remove(k). 删除 "序号为k的node" 的 "后继node"
  • 遍历输出: for (int i=head; i!=-1; i=ne[i]) cout << e[i] << " ";
• 双向链表
  • 初始化: init()
  • 中间节点插入: add(k, x). "序号为k的node" 后面加一个 "值为x的node"
  • 中间节点删除: remove(k). 删除 "序号为k的node" 的 "后继node"
  • 遍历输出: for (int i=head; i!=-1; i=ne[i]) cout << e[i] << " ";

(1) 单链表模板:

#include <iostream>

using namespace std;

const int N = 100010;

// head 表示头结点的下标
// e[i] 表示节点i的值
// ne[i] 表示节点i的next指针是多少
// idx 存储当前已经用到了哪个点
int head, e[N], ne[N], idx;

// 初始化
void init() {
    head = -1; // head -> NaN
    idx = 0;   // 当前还没开始取点
}

// 将x插到头结点
void add_to_head(int x) {
    e[idx] = x; // 给node赋值
    ne[idx] = head;
    head = idx;
    idx++; // 当前点已使用, 点用量++
}

// 将x插到下标是k的点后面
void add(int k, int x) {
    e[idx] = x; // 给node赋值
    ne[idx] = ne[k];
    ne[k] = idx;
    idx++; // 当前点已使用, 点用量++
}

// 将下标是k的点后面的点删掉
void remove(int k) {
    ne[k] = ne[ne[k]];
    // idx不变, 因为“点池”里node数量没增加
}

int main()
{
    int m;
    cin >> m;

    init();

    while (m -- ) {
        int k, x;
        char op;

        cin >> op;
        if (op == 'H') {
            cin >> x;
            add_to_head(x);
        }
        else if (op == 'D') {
            cin >> k;
            if (!k) head = ne[head];
            else remove(k - 1);
        }
        else {
            cin >> k >> x;
            add(k - 1, x);
        }
    }

    for (int i = head; i != -1; i = ne[i]) cout << e[i] << ' ';
    cout << endl;

    return 0;
}

(2) 双向链表模板:

#include <iostream>

using namespace std;

const int N = 100010;

int m;
int e[N], l[N], r[N], idx;

// 初始化
void init() {
    // 0: 左端点 1: 右端点
    r[0] = 1;
    l[1] = 0;
    // 初始化. 就已经消耗了2个node作为 LEFT and RIGHT
    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];
}

int main()
{
    cin >> m;

    init();

    while (m -- )
    {
        string op;
        cin >> op;
        int k, x;
        if (op == "L") {
            cin >> x;
            insert(0, x);
        }
        else if (op == "R") {
            cin >> x;
            insert(l[1], x);
        }
        else if (op == "D") {
            cin >> k;
            remove(k + 1);
        }
        else if (op == "IL") {
            cin >> k >> x;
            insert(l[k + 1], x);
        }
        else {
            cin >> k >> x;
            insert(k + 1, x);
        }
    }

    for (int i = r[0]; i != 1; i = r[i]) cout << e[i] << ' ';
    cout << endl;

    return 0;
}

2. 栈 && 队列

个人习惯是基于STL直接调用

(1) stack:

#include<stack>

stack<int> st;

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

// 入栈 && 弹出栈顶元素
st.push(1);
st.pop();

// 判空 && 当前栈内元素个数
st.empty();
st.size();

(2) queue:

#include<queue>

queue<int> q;

// 队首元素 && 队尾元素
q.front()
q.back()

// 入队 && 队首元素弹出
q.push()
q.pop()

// // 判空 && 当前queue内元素个数
q.empty()
q.size()

(3) vector:

比起用 queue / deque, 我更喜欢用vector来模拟

#include<vector>

/*
以 vector<int> v1 = {1,2,3,4,5,6,7,8,9,10}; 为例
*/

// (1) 初始化 1D | 2D 数组

vector<int> vec;
vector<vector<int> > vec_2d;

// (2) 插入

// push_back: 尾插
v1.push_back(1);
// insert(ptr, value): 任意位置插值
// v1.begin() 返回一个指向字符串第一个元素的迭代器
v1.insert(v1.begin() + 3, 30); // 在 v1[2] ~ v1[3] 之间加上30. now: {1, 2, 3, 30, 4, 5, 6, 7, 8, 9, 10}

// (3) 访问

cout << v1[0] << endl;
cout << v1[1] << endl;
cout << v1.front() << endl; // 获取第一个元素
cout << v1.back() << endl;  // 获取最后一个元素

// (4) 删除

// pop_back: 尾删
v1.pop_back();
// erase(ptr): 任意位置删除
v1.erase(v1.begin() + 3); // 删除 v1[3] (上例, 4). now: {1, 2, 3, 5, 6, 7, 8, 9, 10}
v.erase(v1.begin() + 1, v1.begin() + 3); // 删除 [ v1[1] ~ v1[3] ). now: {1,4,5,6,7,8,9,10}

// (5) 特殊
v1.empty() // 判空
v1.clear() // 清空 vector 中的所有元素

// (6) 遍历

for (int i = 0; i < v1.size(); i++) // 下标访问式
{
    cout << v1[i] << ' ';
}

for (vector<int>::iterator i = v1.begin(); i !=v1.end(); i++) // 纯迭代器式
{
    cout << *i << ' ';
}

for (auto e : v1) // 迭代器式 (auto)
{
    cout << e << ' ';
}

3. 单调栈 && 单调队列

算不上是数据结构，只是基于 stack && queue 进行了一系列维护单调性的操作

1. 单调栈
   • 单调递增栈：在保持栈内元素单调递增的前提下（如果栈顶元素大于要入栈的元素，将将其弹出），将新元素入栈
   • 单调递减栈：在保持栈内元素单调递减的前提下（如果栈顶元素小于要入栈的元素，则将其弹出），将新元素入栈
   • 
   • 
2. 单调队列
   • 操作需要: vector

(1) 单调栈: 给定一个长度为 N 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 −1

// 可以使用 单调stack 的原因:
// 当 i < j 时, if a[i] > a[j], 则 a[i] 肯定不是答案

#include<iostream>
#include<stack>

using namespace std;
const int N=100010;

int n;
int a[N];
stack<int>stk;

int main() 
{   
    cin >> n;

    for (int i = 0; i < n; ++i) {
        int s; 
        cin >> s;

        while (!stk.empty() && s <= stk.top()) stk.pop();
        a[i] = stk.empty() ? -1 : stk.top();

        stk.push(s);
    }

    for (int i=0; i<n; i++) cout << a[i] << " ";
    cout << endl;
    return 0;
}

(2) 单调队列: 确定滑动窗口位于每个位置时，窗口中的"最大值"和"最小值" (滑动窗口问题)

/*
分析:

这道题目, 我们就维护两个队列, 一个是最小值, 一个是最大值. 这里唯一的重点就是, 每一次入队的时候, 不需要管是不是比队头小, 因为也许他现在小, 但是在队头出队列后, 他还在, 而且是最小的值.

seeking for MIN:

发现一个性质:

如果队列中存在两个元素, 满足 a[i] >= a[j] 且 i < j, 那么无论在什么时候我们都不会取 a[i] 作为最小值了, 所以可以直接将 a[i] 删掉
*/
#include <iostream>
#include <vector>

using namespace std;

const int N = 1000010;

int a[N];

int main()
{
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> a[i];

    // (1) 使用 vector 求解滑动窗口最小值
    vector<int> q; // q: 装的是下标

    for (int i = 0; i < n; i++)
    {
        // 1. 队头检查: 如果队头元素的下标超出了窗口范围，则从队头出队
        if (!q.empty() && i - k + 1 > q.front()) {
            q.erase(q.begin());
        }

        // 2. 队尾维护单调性: 从队尾开始，移除所有比 a[i] 大的元素
        while (!q.empty() && a[q.back()] >= a[i]) {
            q.pop_back();
        }

        // 3. 入队: 将当前元素的下标加入队尾
        q.push_back(i);

        // 4. 取答案: 当窗口形成后，队头即为当前窗口的最小值
        if (i >= k - 1) {
            cout << a[q.front()] << " ";
        }
    }
    cout << endl;

    // (2) 使用 vector 求解滑动窗口最大值
    q.clear(); // 清空 vector，为求最大值做准备

    for (int i = 0; i < n; i++)
    {
        // 1. 队头检查
        if (!q.empty() && i - k + 1 > q.front()) {
            q.erase(q.begin());
        }

        // 2. 队尾维护单调性: 逻辑与求最小值时相反
        while (!q.empty() && a[q.back()] <= a[i]) {
            q.pop_back();
        }

        // 3. 入队
        q.push_back(i);

        // 4. 取答案
        if (i >= k - 1) {
            cout << a[q.front()] << " ";
        }
    }
    cout << endl;

    return 0;
}

4. KMP

直接放弃了，考到就背模板吧，大概率认栽...

给定一个字符串 S，以及一个模式串 P，所有字符串中只包含大小写英文字母以及阿拉伯数字。 模式串 P 在字符串 S 中多次作为子串出现。求出模式串 P 在字符串 S 中所有出现的位置的起始下标。

1. s[ ]是模式串，即比较长的字符串
2. p[ ]是模板串，即比较短的字符串
3. next[ ]是“部分匹配值表”，即next数组，它存储的是每一个下标对应的“部分匹配值”

核心思想： 在每次失配时，不是把p串往后移一位，而是把p串往后移动至下一次可以和前面部分匹配的位置，这样就可以跳过大多数的失配步骤。而每次p串移动的步数就是通过查找next[ ]数组确定的。

#include <iostream>

using namespace std;

const int N = 100010, M = 1000010;

int n, m;
int ne[N];
char s[M], p[N];

int main()
{
    cin >> n >> p + 1 >> m >> s + 1;

    for (int i = 2, j = 0; i <= n; 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 <= m; i ++ )
    {
        while (j && s[i] != p[j + 1]) j = ne[j];
        if (s[i] == p[j + 1]) j ++ ;
        if (j == n)
        {
            printf("%d ", i - n);
            j = ne[j];
        }
    }

    return 0;
}

5. Trie 树 (Trie数组)

快速 存储 / 查找 字符串集合

1. 只有找到以 * 结尾的, 才算一个真正的“字符串匹配”, find 才能 ++.
2. son[x][num] = y: nodeX 的一个 值为num的子节点 为 nodeY.
   1. init: son[N][26].
   2. (num=0: a) | (num=1: b) | ... | (num=25: z).
   3. eg. son[1][0]=2: 表示 1结点 的一个值为a的子结点为 结点2.
   4. son[1][0] = 0: 意味着没有值为a子结点
3. cnt[x]: 以 x 结尾的单词数量
4. idx: 全局变量, 相当于一个 node 分配计数器

题面:

维护一个字符串集合，支持两种操作:

1. I x 向集合中插入一个字符串 x
2. Q x 询问一个字符串在集合中出现了多少次

共有 N 个操作，所有输入的字符串总长度不超过 105，字符串仅包含小写英文字母。

代码:

#include <iostream>
#include <string>

using namespace std;

const int N = 100010;

int son[N][26], cnt[N], idx;
string input, str;

void insert(string str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        // 将当前字符转换成数字 (a->0, b->1,...)
        int u = str[i] - 'a';

        // 如果数中不能走到当前字符 (!son[p][u])
        // 为当前字符创建新的节点，保存该字符
        if (!son[p][u]) son[p][u] = ++ idx; // 建立 父子节点 连接

        p = son[p][u]; // 指针下移, 类似 nxt[]
    }
    // p 等于字符串 s 的尾字符所对应的 idx
    // cnt[p] 保存的是字符串 s 出现的次数
    cnt[p] ++ ; // 以p结尾的string个数++
}

int query(string 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]; // 指针下移, 类似 nxt[]
    }
    return cnt[p];
}

int main()
{
    int n;
    cin >> n;
    while (n -- ) {
        cin >> input >> str;
        /* 
        在这题里不对, 因为 <blankspace> 会将string分成两个:
        string str = "";
        int len = input.length();

        for (int i=2; i<=len-1; i++) str += input[i];
        */
        if (input[0] == 'I') insert(str);
        else cout << query(str) << endl;
    }

    return 0;
}

6. 并查集

1. 合并集合: p[ find(a) ] = find(b).
2. 询问两个元素是否在一个集合中: find(a) == find(b).
3. 查询一个集合中的元素个数: 开个 cnt数组, 为每个集合的root维护, 更新方式 cnt[find(a)].

/*
M a b: 将编号为 a 和 b 的两个数所在的集合合并, 如两个数已经在同一个集合中, 则忽略操作
Q a b: 询问编号为 a 和 b 的两个数是否在同一个集合中
*/
#include <iostream>
#include <string>

using namespace std;

const int N = 100010;

int p[N];

int find(int x) // 查找x的祖先节点 (root)
{
    // 并查集: 只有 root 节点的 p[x]==x
    if (p[x] != x) p[x] = find(p[x]); // 上行
    return p[x];
}

int main()
{
    int n, m;
    cin >> n >> m;

    // 并查集初始化 ("每个node都是root")
    for (int i = 1; i <= n; i ++ ) p[i] = i;

    while (m -- )
    {
        string op;
        int a, b;
        cin >> op >> a >> b; // <blankspace> 自动划分

        if (op == "M") p[find(a)] = find(b); // "集合合并"
        else
        {
            // "判断两个元素是否属于同一个集合"
            if (find(a) == find(b)) puts("Yes");
            else puts("No");
        }
    }

    return 0;
}

/* 
连通块中点的数量

C a b: 在点 a 和点 b 之间连一条边, a 和 b 可能相等
Q1 a b: 询问点 a 和点 b 是否在同一个连通块中, a 和 b 可能相等
Q2 a: 询问点 a 所在连通块中点的数量
*/
#include <iostream>

using namespace std;

const int N = 100010;

int n, m;
int p[N], cnt[N];

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    cin >> n >> m;

    // 并查集初始化 
    // 1. 每个node都是root
    // 2. 每个set里都只有自己这一个元素
    for (int i = 1; i <= n; i ++ ) {
        p[i] = i;
        cnt[i] = 1;
    }

    while (m -- ) {
        string op;
        int a, b;
        cin >> op;

        if (op == "C")
        {
            cin >> a >> b;
            a = find(a), b = find(b);
            if (a != b) { // "集合合并"
                p[a] = b;
                cnt[b] += cnt[a];
            }
        }
        else if (op == "Q1")
        {
            // 集合判等
            cin >> a >> b;
            if (find(a) == find(b)) puts("Yes");
            else puts("No");
        }
        else
        {
            // 输出集合内元素个数
            cin >> a;
            cout << cnt[find(a)] << endl;
        }
    }

    return 0;
}

7. 堆

应用题目我喜欢STL, 但是heap的模拟很重要, 后面平衡树之类的会用到

(1) 定义:

#include <queue> // 只需要这一个头文件就管够了

// 定义 大根堆 (default)
priority_queue<int> max_heap;

// 定义 小根堆
priority_queue<int, vector<int>, greater<int>> min_heap;

结构体的大根堆/小根堆:

// 结构体定义
struct node { 
    int ve; 
    int dist;
};

// ===========================
// 建立小根堆
// ===========================
struct node {
    int ve;   // 顶点
    int dist; // 距离出发点的min_dist

    bool operator>(const node& other) const {
        return dist > other.dist;
    }
};

priority_queue<node, vector<node>, greater<node>> min_heap;

// ===========================
// 建立大根堆
// ===========================
struct node {
    int ve; 
    int dist; 
    bool operator<(const node& other) const { 
        return this->dist < other.dist; 
    }
};

priority_queue<node> max_heap;

(2) 常用操作:

heap.top()   // 访问堆顶元素（此时优先队列不能为空）
heap.empty() // 询问容器是否为空
heap.size()  // 查询容器中的元素数量

heap.push(x) // 插入元素，并对底层容器排序
heap.pop()   // 删除堆顶元素（此时优先队列不能为空）

(3) 数组模拟heap:

1. ph[] && hp[] && idx

堆中的每次插入都是在堆尾，但是堆中经常有up和down操作。所以节点与节点的关系并不是用一个ne[idx][2]可以很好地维护的。但是好在堆是个完全二叉树。子父节点的关系可以通过下标来联系（左儿子2n，右儿子2n+1）

就数组模拟来说，知道数组的下标就知道结点在堆中的位置。所以核心就在于即使有down和up操作也能维护堆数组的下标（k）和结点（idx）的映射关系。 比如说：h[k] = x, h数组存的是节点的值，按理来说应该h[idx]来存，但是节点位置总是在变的，因此维护k和idx的映射关系就好啦

举例： 用ph数组来表示ph[idx] = k(idx到下标), 那么结点值为h[ph[idx]], 儿子为ph[idx] * 2和ph[idx] * 2 + 1, 这样值和儿子结点就可以通过idx联系在一起了!

2. 为什么还要 hp[]

h数组主要用于帮助从idx映射到下标k，似乎有了ph数组就可以完成所有操作了，但为什么还要有一个hp数组呢？

原因就在于在swap操作中我们输入是堆数组的下标，无法知道每个堆数组的k下标对应idx（第idx个插入），所以需要hp数组方便查找idx

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

const int N = 100010;

int h[N], ph[N], hp[N], cnt;

void heap_swap(int a, int b)
{
    // 第a个插入的数 && 第b个插入的数
    swap(ph[hp[a]],ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

void down(int u)
{
    // NodeU 下移
    int t = u;
    if (u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if (u != t)
    {
        heap_swap(u, t);
        down(t);
    }
}

void up(int u)
{
    // NodeU 上移
    while (u / 2 && h[u] < h[u / 2])
    {
        heap_swap(u, u / 2);
        u >>= 1;
    }
}

int main()
{
    int n, m = 0;
    cin >> n;

    while (n -- ) {
        string op;
        int k, x;
        cin >> op;

        if (op == "I") {
            cin >> x;
            cnt ++ ;
            m ++ ;
            ph[m] = cnt, hp[cnt] = m; // 插入序号 <-> heap index
            h[cnt] = x;
            up(cnt);
        }
        else if (op == "PM") cout << h[1] << endl;
        else if (op == "DM") {
            heap_swap(1, cnt);
            cnt -- ;
            down(1);
        }
        else if (op == "D") {
            cin >> k; // 第k个插入的数
            k = ph[k];
            heap_swap(k, cnt);
            cnt -- ;
            up(k);
            down(k);
        }
        else {
            cin >> k >> x;
            k = ph[k];
            h[k] = x;
            up(k);
            down(k);
        }
    }

    return 0;
}

8. 哈希表

哈希表的作用：把庞大复杂的数据映射到较小的范围

1. 拉链法: 纯邻接表
2. 开放寻址法: 多开几倍, 一直向后看, 如果有坑就坐, 如果坑被占就继续向后看

题面:

维护一个集合，支持如下几种操作:

1. I x，插入一个整数 x
2. Q x，询问整数 x 是否在集合中出现过

现在要进行 N 次操作, 对于每个询问操作输出对应的结果

数据范围:

• \(1\) ≤ \(N\) ≤ \(10^5\)
• −\(10^9\) ≤ \(x\) ≤ \(10^9\)

(1) 拉链法

#include <cstring>
#include <string>
#include <iostream>

using namespace std;

// 选择一个大于数据范围N的素数 (玄学理论), 这里 1e5+3 即可
const int N = 100003; // 如何筛素数? 见后面数学的chapter

int h[N], e[N], ne[N], idx;

void insert(int x) {
    // 定位 h[]
    int k = (x % N + N) % N;
    // 像链表那样插入node即可
    e[idx] = x;
    ne[idx] = h[k];
    h[k] = idx ++ ;
}

bool find(int x) {
    // 定位 h[]
    int k = (x % N + N) % N;
    // 遍历链表进行查询
    for (int i = h[k]; i != -1; i = ne[i])
        if (e[i] == x)
            return true;

    return false;
}

int main()
{
    int n;
    cin >> n;

    // 初始化: 跟链表一样 (HEAD指向空指针)
    memset(h, -1, sizeof h); // 一整排 head[]

    while (n -- )
    {
        string op;
        int x;
        cin >> op >> x;

        if (op == "I") insert(x);
        else
        {
            if (find(x)) puts("Yes");
            else puts("No");
        }
    }

    return 0;
}

(2) 开放寻址法

#include <cstring>
#include <iostream>

using namespace std;

// 选择一个大于数据范围 2~3倍 的素数 (玄学理论), 这里 2e5+3 即可
const int N = 200003, null = 0x3f3f3f3f;

int h[N];

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;
}

int main()
{
    // 初始化: 确保在取值范围1e9以外即可
    memset(h, 0x3f, sizeof h);

    int n;
    scanf("%d", &n);

    while (n -- )
    {
        char op[2];
        int x;
        scanf("%s%d", op, &x);
        if (*op == 'I') h[find(x)] = x;
        else
        {
            if (h[find(x)] == null) puts("No");
            else puts("Yes");
        }
    }

    return 0;
}

9. C++ STL

除了上面的那些，我们还需要着重说一下这几个:

• set && unordered_set
• map && unordered_map
• string
• pair

(1) set && unordered_set

头文件: #include <set>

集合三要素	解释	set	multiset	unordered_set
确定性	一个元素要么在集合中，要么不在	✔	✔	✔
互异性	一个元素仅可以在集合中出现一次	✔	❌（任意次）	✔
无序性	集合中的元素是没有顺序的	❌（从小到大）	❌（从小到大）	✔

初始化定义:

// 默认从小到大
set<int> st1;               // 储存int的集合（从小到大）
set<int, greater<int>> st2; // 储存int的集合（从大到小）

遍历:

// method 1:
for (set<int>::iterator it = st.begin(); it != st.end(); ++it)
    cout << *it << endl;
// method 2:
for (auto &ele : st)
    cout << ele << endl;

其他:

作用	用法	示例
插入元素	.insert(元素)	st.insert(1);
删除元素	.erase(元素)	st.erase(2);
查找元素	.find(元素)	auto it = st.find(1);
判断元素是否存在	.count(元素)	st.count(3);
查看大小 / 清空 / 判空	略	st.clear();

使用场景:

• 元素去重：\([1,1,3,2,4,4]\to[1,2,3,4]\)
• 维护顺序：\([1,5,3,7,9]\to[1,3,5,7,9]\)
• 元素是否出现过：元素大小 \([-10^{18},10^{18}]\)，元素数量 \(10^6\)，vis 数组无法实现，通过 set 可以完成。
• count(x): 返回 set 内键为 x 的元素数量
• find(x): 在 set 内存在键为 x 的元素时会返回该元素的迭代器，否则返回 end()
• lower_bound(x): 返回指向首个不小于给定键的元素的迭代器。如果不存在这样的元素，返回 end()
• upper_bound(x): 返回指向首个大于给定键的元素的迭代器。如果不存在这样的元素，返回 end()
• empty(): 返回容器是否为空
• size(): 返回容器内元素个数

注意事项:

[1] 可使用迭代器进行遍历，它不存在下标这一概念

cout << st[0] << endl;

[2] set 的迭代器取到的元素是只读的（因为是 const 迭代器），不可修改其值。如果要改，需要先 erase 再 insert. 下面是错误用法：

cout << *st.begin() << endl; // 正确。可读。
*st.begin() = 1;             // 错误！不可写！

(2) map && unordered_map

头文件: #include <map>

性质	解释	map	multimap	unordered_map
互异性	一个键仅可以在映射中出现一次	✔	❌（任意次）	✔
无序性	键是没有顺序的	❌（从小到大）	❌（从小到大）	✔

初始化定义:

// map<key_type, value_type> map_instance;
// 默认key从小到大
map<int, int> mp1;               // int->int 的映射（键从小到大）
map<int, int, greater<int>> st2; // int->int 的映射（键从大到小）

遍历:

// 可使用迭代器进行遍历
for (map<int, int>::iterator it = mp.begin(); it != mp.end(); ++it)
    cout << it->first << ' ' << it->second << endl;
// 基于范围的循环（C++11）
for (auto &pr : mp)
    cout << pr.first << ' ' << pr.second << endl;
// 结构化绑定 + 基于范围的循环（C++17）
for (auto &[key, val] : mp)
    cout << key << ' ' << val << endl;

其他:

作用	用法	示例
增 / 改 / 查元素	中括号	mp[1] = 2;
查元素（返回迭代器）	.find(元素)	auto it = mp.find(1);
删除元素	.erase(元素)	mp.erase(2);
判断元素是否存在	.count(元素)	mp.count(3);
查看大小 / 清空 / 判空	略	mp.clear();
类似于insert()	.insert(PairType)	mp.insert({"Bob", 95});

插入与删除操作:

• 可以直接通过下标访问来进行查询或插入操作。例如 mp["Alan"]=100
• 通过向 map 中插入一个类型为 pair<Key, T> 的值可以达到插入元素的目的，例如 mp.insert(pair<string,int>("Alan",100));
• erase(key) 函数会删除键为 key 的 所有 元素。返回值为删除元素的数量
• erase(pos): 删除迭代器为 pos 的元素，要求迭代器必须合法
• erase(first,last): 删除迭代器在 [first, last) 范围内的所有元素
• clear() 函数会清空整个容器

查询操作:

• count(x): 返回容器内键为 x 的元素数量
• find(x): 若容器内存在键为 x 的元素，会返回该元素的迭代器；否则返回 end()
• lower_bound(x): 返回指向首个不小于给定键的元素的迭代器
• upper_bound(x): 返回指向首个大于给定键的元素的迭代器。若容器内所有元素均小于或等于给定键，返回 end()
• empty(): 返回容器是否为空
• size(): 返回容器内元素个数

注意事项:

[1] 如果使用中括号访问 map 时对应的键不存在，那么会新增这个键，并且值为默认值，因此中括号会影响键的存在性

map<char, int> mp;
cout << mp.count('a') << endl; // 0
mp['a'];                       // 即使什么都没做，此时mp['a']=0已经插入了
cout << mp.count('a') << endl; // 1
cout << mp['a'] << endl;       // 0

(3) string

头文件: #include <string>

常用操作:

// (0) 转 char 数组
s.c_str()

// (1) 获取长度
str.length();
str.size();

// (2) 寻找某字符（串）第一次出现的位置
// find(str,pos)
string s = "OI Wiki", t = "OI", u = "i";
int pos = 5;
printf("字符 I 在 s 的 %lu 位置第一次出现\n", s.find('I'));
printf("字符 a 在 s 的 %lu 位置第一次出现\n", s.find('a'));
printf("字符 a 在 s 的 %d 位置第一次出现\n", s.find('a'));
printf("字符串 t 在 s 的 %lu 位置第一次出现\n", s.find(t));
printf("在 s 中自 pos 位置起字符串 u 第一次出现在 %lu 位置", s.find(u, pos));
/*
字符 I 在 s 的 1 位置第一次出现
字符 a 在 s 的 18446744073709551615 位置第一次出现 // 即为 size_t(-1)，具体数值与平台有关。
字符 a 在 s 的 -1 位置第一次出现 // 强制转换为 int 类型则正常输出 -1
字符串 t 在 s 的 0 位置第一次出现
在 s 中自 pos 位置起字符串 u 第一次出现在 6 位置
*/

// (3) 截取子串
// substr(pos, len) 函数的参数返回从 pos位置 开始截取最多 len 个字符组成的字符串
// 不会忽略空格
string s = "OI Wiki", t = "OI";
cout << s.substr(3, 3).c_str() <<endl;
cout << t.substr(1, 3).c_str() <<endl;
cout << s.substr(1, 3).c_str() <<endl;
/*
Wik
I
I W
*/

冷门备份:

// 插入 / 删除字符（串)
string s = "OI Wiki", t = " Wiki";
char u = '!';
s.erase(2);
printf("从字符串 s 的第三位开始删去所有字符后得到的字符串是 %s\n", s.c_str());
s.insert(2, t);
printf("在字符串 s 的第三位处插入字符串 t 后得到的字符串是 %s\n", s.c_str());
s.insert(7, 3, u);
printf("在字符串 s 的第八位处连续插入 3 次字符串 u 后得到的字符串是 %s",
       s.c_str());
/*
从字符串 s 的第三位开始删去所有字符后得到的字符串是 OI
在字符串 s 的第三位处插入字符串 t 后得到的字符串是 OI Wiki
在字符串 s 的第八位处连续插入 3 次字符串 u 后得到的字符串是 OI Wiki!!!
*/

// 替换字符（串）
string s = "OI Wiki";
s.replace(2, 5, "");
printf("将字符串 s 的第 3~7 位替换为空串后得到的字符串是 %s\n", s.c_str());
s.replace(s.begin(), s.begin() + 2, "NOI");
printf("将字符串 s 的前两位替换为 NOI 后得到的字符串是 %s", s.c_str());
/*
将字符串 s 的第 3~7 位替换为空串后得到的字符串是 OI
将字符串 s 的前两位替换为 NOI 后得到的字符串是 NOI
*/

(4) pair

初始化:

// (1)
pair<int, double> p0(1, 2.0);

// (2)
pair<int, double> p1;
p1.first = 1;
p1.second = 2.0;

// (3)
pair<int, double> p2 = make_pair(1, 2.0);
auto p3 = make_pair(1, 2.0);

访问:

int i = p0.first;
double d = p0.second;

// 可以直接对其进行修改
p1.first++;

赋值与交换:

#include <iostream>
#include <utility> // pair 所在的头文件 (no need)
#include <string>

int main() 
{
    // 创建并初始化两个 pair
    std::pair<int, std::string> lockerA = {101, "苹果"};
    std::pair<int, std::string> lockerB = {202, "香蕉"};

    std::cout << "--- 赋值前 ---" << std::endl;
    std::cout << "A号柜: " << lockerA.first << ", " << lockerA.second << std::endl;
    std::cout << "B号柜: " << lockerB.first << ", " << lockerB.second << std::endl;

    // 执行赋值操作
    std::cout << "\n执行 lockerA = lockerB; \n" << std::endl;
    lockerA = lockerB;

    std::cout << "--- 赋值后 ---" << std::endl;
    std::cout << "A号柜: " << lockerA.first << ", " << lockerA.second << std::endl;
    std::cout << "B号柜: " << lockerB.first << ", " << lockerB.second << std::endl;

    return 0;
}

/*
--- 赋值前 ---
A号柜: 101, 苹果
B号柜: 202, 香蕉

执行 lockerA = lockerB; 

--- 赋值后 ---
A号柜: 202, 香蕉
B号柜: 202, 香蕉
*/

#include <iostream>
#include <utility>
#include <string>

int main() 
{
    // 创建并初始化两个 pair
    std::pair<int, std::string> lockerC = {303, "樱桃"};
    std::pair<int, std::string> lockerD = {404, "榴莲"};

    std::cout << "--- 交换前 ---" << std::endl;
    std::cout << "C号柜: " << lockerC.first << ", " << lockerC.second << std::endl;
    std::cout << "D号柜: " << lockerD.first << ", " << lockerD.second << std::endl;

    // 执行交换操作
    std::cout << "\n执行 swap(lockerC, lockerD); \n" << std::endl;
    swap(lockerC, lockerD);

    std::cout << "--- 交换后 ---" << std::endl;
    std::cout << "C号柜: " << lockerC.first << ", " << lockerC.second << std::endl;
    std::cout << "D号柜: " << lockerD.first << ", " << lockerD.second << std::endl;

    return 0;
}

/*
--- 交换前 ---
C号柜: 303, 樱桃
D号柜: 404, 榴莲

执行 swap(lockerC, lockerD); 

--- 交换后 ---
C号柜: 404, 榴莲
D号柜: 303, 樱桃
*/

pair 与 map:

// map 的是 C++ 中存储键值对的数据结构
// 很多情况下，map 中存储的键值对通过 pair 向外暴露
map<int, double> m;
m.insert(make_pair(1, 2.0));