C++ STL 标准模板库复习：算法与容器详解

二、nth_element

• 作用：部分排序，用于重新排列元素，使得第 n 个位置的元素处于其排序后的正确位置，但不保证其他元素的完全有序。
• 模板：nth_element(Iterator begin, Iterator nth, Iterator end, function comp)
• 复杂度：O(n)
• Function Comp：自定义比较器
• 预定义函数对象：最常用 greater<>()，用于实现降序排序
• 代码案例：

#include <bits/stdc++.h>
using namespace std;
int main() {
    vector<int> v1 = {5, 2, 8, 1, 9, 3, 6, 4, 7, 0};
    vector<int> v2 = {5, 2, 8, 1, 9, 3, 6, 4, 7, 0};
    vector<int> v3 = {5, 2, 8, 1, 9, 3, 6, 4, 7, 0};
    vector<int> v4 = {5, 2, 8, 1, 9, 3, 6, 4, 7, 0};
    // 1. 查询第五小的元素
    nth_element(v1.begin(), v1.begin() + 4, v1.end());
    cout << "第 5 小的元素是：" << v1[4] << endl;
    // 2. 查找前 k 个最小元素
    nth_element(v2.begin(), v2.begin() + 3, v2.end());
    cout << "前 3 小的元素：";
    for (int i = 0; i < 3; i++) { cout << v2[i] << " "; }
    cout << endl;
    // 3. 使用自定义预定义函数对象
    nth_element(v3.begin(), v3.begin() + 2, v3.end(), greater<int>());
    cout << "第 3 大的元素是：" << v3[2] << endl;
    // 4. 寻找中位数
    int nums = v4.size();
    if(nums % 2 != 0){
        nth_element(v4.begin(), v4.begin() + nums/2, v4.end());
    }else{
        nth_element(v4.begin(), v4.begin() + nums/2, v4.end());
        int right_mid = v4[nums/2];
        nth_element(v4.begin(), v4.begin() + nums/2 - 1, v4.begin() + nums/2);
        int left_mid = v4[nums/2 - 1];
        double median = (left_mid + right_mid) / 2.0;
        cout << "中位数：" << median << endl;
    }
}

三、lower_bound & upper_bound

• 模板：lower_bound(Iterator begin, Iterator end, Type v, Function comp) / upper_bound(Iterator begin, Iterator end, Type v, Function comp)
• 作用：用于在已排序的序列中查找元素
• 复杂度：O(log n)
• Type v：目标值
• Function Comp：自定义比较器
• 预定义函数对象：最常用 greater<>()，用于实现降序排序
• 代码案例：

#include <bits/stdc++.h>
using namespace std;
int main() {
    vector<int> v = {1, 2, 2, 2, 3, 4, 4, 5, 7, 9};
    // 1. lower_bound: 查找第一个 >= target 的元素位置
    int target1 = 3;
    auto lb1 = lower_bound(v.begin(), v.end(), target1);
    cout << " 第一个 >= 3 的元素位置：索引 " << (lb1 - v.begin()) << endl;
    cout << " 对应元素值：" << *lb1 << endl << endl;
    // 2. upper_bound: 查找第一个 > target 的元素位置
    int target2 = 3;
    auto ub2 = upper_bound(v.begin(), v.end(), target2);
    cout << " 第一个 > 3 的元素位置：索引 " << (ub2 - v.begin()) << endl;
    cout << " 对应元素值：" << *ub2 << endl << endl;
    // 3. 查找重复元素的范围
    int target3 = 2;
    auto lb3 = lower_bound(v.begin(), v.end(), target3);
    auto ub3 = upper_bound(v.begin(), v.end(), target3);
    cout << " 元素 2 的范围：[" << (lb3 - v.begin()) << ", " << (ub3 - v.begin()) << ")" << endl;
    cout << " 元素 2 的个数：" << (ub3 - lb3) << endl << endl;
    // 4. 在降序数组中查找
    vector<int> v_desc = {9, 7, 5, 5, 5, 3, 1};
    int target5 = 5;
    auto lb5 = lower_bound(v_desc.begin(), v_desc.end(), target5, greater<int>());
    auto ub5 = upper_bound(v_desc.begin(), v_desc.end(), target5, greater<int>());
    cout << " lower_bound(5) 位置：索引 " << (lb5 - v_desc.begin()) << endl;
    cout << " upper_bound(5) 位置：索引 " << (ub5 - v_desc.begin()) << endl;
    cout << " 元素 5 的个数：" << (ub5 - lb5) << endl << endl;
    // 5. 检查元素是否存在
    int target6 = 4;
    cout << "5. 检查元素 4 是否存在:" << endl;
    auto it = lower_bound(v.begin(), v.end(), target6);
    if (it != v.end() && *it == target6) {
        cout << " 元素 4 存在，位置：索引 " << (it - v.begin()) << endl;
    } else {
        cout << " 元素 4 不存在" << endl;
    }
    cout << endl;
    // 6. 查找插入位置保持有序
    int new_element = 6;
    auto insert_pos = lower_bound(v.begin(), v.end(), new_element);
    cout << "插入元素 " << new_element << " 保持有序:" << endl;
    cout << " 应该插入在索引：" << (insert_pos - v.begin()) << endl;
    v.insert(insert_pos, new_element);
    cout << " 插入后数组：";
    for (auto& x : v) { cout << x << " "; }
    cout << endl;
    return 0;
}

四、next_permutation & prev_permutation

• 作用：用于生成序列的下一个/上一个排列，如果已经是最后一个排列，则修改为最小或最大的排列后，返回 false。bool 是 next_permutation 和 prev_permutation 函数的返回值类型，用来表示是否成功生成了下一个/上一个排列。
• 模板： next_permutation(Iterator begin, Iterator end) prev_permutation(Iterator begin, Iterator end)
• 复杂度：O(n)
• 代码案例：

#include <bits/stdc++.h>
using namespace std;
int main() {
    vector<int> v1 = {1, 2, 3};
    vector<int> v2 = {1, 2, 3};
    vector<int> v3 = {1, 2, 3};
    // 1. 使用 next_permutation 生成所有排列
    cout << "1. 使用 next_permutation 生成所有排列:" << endl;
    int count1 = 1;
    do {
        cout << "第" << count1 << "个排列：";
        for (auto& x : v1) { cout << x << " "; }
        cout << endl;
        count1++;
    } while (next_permutation(v1.begin(), v1.end()));
    cout << endl;
    // 2. 使用 prev_permutation 生成所有排列
    sort(v2.begin(), v2.end(), greater<int>());
    cout << "2. 使用 prev_permutation 生成所有排列:" << endl;
    cout << " (先降序排序：";
    for (auto& x : v2) cout << x << " ";
    cout << ")" << endl;
    int count2 = 1;
    do {
        cout << " 第" << count2 << "个排列：";
        for (auto& x : v2) { cout << x << " "; }
        cout << endl;
        count2++;
    } while (prev_permutation(v2.begin(), v2.end()));
    cout << endl;
    // 3. 只生成下一个排列
    cout << "3. 只生成下一个排列:" << endl;
    cout << "当前排列：";
    for (auto& x : v3) { cout << x << " "; }
    cout << endl;
    bool has_next = next_permutation(v3.begin(), v3.end());
    cout << " 下一个排列：";
    for (auto& x : v3) { cout << x << " "; }
    cout << endl;
    has_next = next_permutation(v3.begin(), v3.end());
    cout << " 下一个排列：";
    for (auto& x : v3) { cout << x << " "; }
    cout << endl;
    cout << endl;
    // 4. 处理有重复元素的数组
    vector<int> v4 = {1, 2, 2};
    cout << "4. 有重复元素 {1, 2, 2} 的排列:" << endl;
    sort(v4.begin(), v4.end());
    int count3 = 0;
    do {
        cout << " 排列" << ++count3 << ": ";
        for (auto& x : v4) { cout << x << " "; }
        cout << endl;
    } while (next_permutation(v4.begin(), v4.end()));
    cout << endl;
}

五、unique

• 作用：去除相邻重复元素的算法。它不真正删除元素，而是将不重复的元素移动到容器前面，并返回新的逻辑末尾。
• 模板：unique(iterator begin, iterator end, function matcher)
• 复杂度：O(n)
• function matcher：自定义比较函数
• 代码案例：

#include <bits/stdc++.h>
using namespace std;
int main() {
    vector<int> v1 = {1, 1, 2, 2, 2, 3, 3, 4, 4, 4, 5};
    vector<int> v2 = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
    vector<int> v3 = {1, 3, 2, 4, 6, 5, 7, 9, 8};
    vector<int> v4 = {12, 15, 18, 23, 25, 34, 37, 45, 48};
    // 1. 默认用法：去除相邻重复元素
    cout << "1. 默认用法（去除相邻重复元素）:" << endl;
    vector<int> temp1 = v1;
    auto new_end1 = unique(temp1.begin(), temp1.end());
    cout << " 去重后：";
    for (auto it = temp1.begin(); it != new_end1; it++) { cout << *it << " "; }
    cout << endl;
    // 2. 配合 sort 去除所有重复元素
    cout << "2. 配合 sort 去除所有重复元素:" << endl;
    vector<int> temp2 = v2;
    sort(temp2.begin(), temp2.end());
    auto new_end2 = unique(temp2.begin(), temp2.end());
    temp2.erase(new_end2, temp2.end());
    cout << " 去重后：";
    for (auto& x : temp2) cout << x << " ";
    cout << endl;
    // 3. 使用自定义比较函数
    cout << "3. 使用自定义比较函数（按十位数分组）:" << endl;
    sort(v4.begin(), v4.end(), [](int a, int b) { return a < b; });
    auto new_end4 = unique(v4.begin(), v4.end(), [](int a, int b) { return (a / 10) == (b / 10); });
    cout << " 去重后（每个十位数组保留第一个）：";
    for (auto it = v4.begin(); it != new_end4; it++) { cout << *it << " "; }
    cout << endl;
}

六、minmax_element

• 作用：用于在容器中查找最小元素和最大元素的位置。
• 模板：minmax_element(iterator begin, iterator end, function comp)
• 复杂度：O(n)
• Function Comp：自定义比较器
• 代码案例：

#include <bits/stdc++.h>
using namespace std;
int main() {
    vector<int> v1 = {9, 5, 1, 2, 4, 6, 8, 3, 0, 7};
    vector<int> v2 = {9, 5, 1, 2, 4, 6, 8, 3, 0, 7};
    vector<int> v3 = {-9, 5, 1, 2, 4, 6, 8, 3, 0, 7};
    // 1. 查找最大元素
    auto max_it = max_element(v1.begin(), v1.end());
    cout << " 最大值：" << *max_it << endl;
    cout << " 最大值位置：索引 " << (max_it - v1.begin()) << endl;
    cout << endl;
    // 2. 查找最小元素
    auto min_it = min_element(v2.begin(), v2.end());
    cout << " 最小值：" << *min_it << endl;
    cout << " 最小值位置：索引 " << (min_it - v2.begin()) << endl;
    cout << endl;
    // 3. 使用自定义比较函数
    auto abs_max_it = max_element(v3.begin(), v3.end(), [](int a, int b) { return abs(a) < abs(b); });
    cout << " 绝对值最大的元素：" << *abs_max_it << endl;
    cout << " 绝对值：" << abs(*abs_max_it) << endl;
    cout << " 位置：索引 " << (abs_max_it - v3.begin()) << endl;
    cout << endl;
    // 4. 同时查找最小和最大值（C++11）
    auto [min_it2, max_it2] = minmax_element(v1.begin(), v1.end());
    cout << " 最小值：" << *min_it2 << " (索引：" << (min_it2 - v1.begin()) << ")" << endl;
    cout << " 最大值：" << *max_it2 << " (索引：" << (max_it2 - v1.begin()) << ")" << endl;
    cout << endl;
    // 5. 在子范围中查找
    auto sub_min = min_element(v1.begin() + 2, v1.begin() + 7);
    auto sub_max = max_element(v1.begin() + 2, v1.begin() + 7);
    cout << " 子数组：";
    for (int i = 2; i < 7; i++) { cout << v1[i] << " "; }
    cout << endl;
    cout << " 子数组最小值：" << *sub_min << " (相对索引：" << (sub_min - v1.begin()) << ")" << endl;
    cout << " 子数组最大值：" << *sub_max << " (相对索引：" << (sub_max - v1.begin()) << ")" << endl;
    return 0;
}

七、accumulate

• 作用：对范围内的数值进行累加，可以修改累加函数
• 模板：accumulate(iterator begin, iterator end, type init, function operator)
• 复杂度：O(n)
• Type Init：初始值
• Function Comp：自定义比较器，案例中使用了 multiplies<int>()
• 代码案例：

#include <bits/stdc++.h>
using namespace std;
int main() {
    vector<int> v1 = {1, 2, 3, 4, 5};
    vector<int> v2 = {1, 2, 3, 4, 5};
    vector<int> v3 = {1, 2, 3, 4, 5};
    // 1. 默认累加（求和）
    int sum = accumulate(v1.begin(), v1.end(), 0);
    cout << " 1+2+3+4+5 = " << sum << endl;
    cout << endl;
    // 2. 使用预定义函数对象（乘法累加）
    int product = accumulate(v2.begin(), v2.end(), 1, multiplies<int>());
    cout << " 1×2×3×4×5 = " << product << endl;
    cout << endl;
    // 3. 使用自定义函数（绝对值累加）
    vector<int> nums = {1, -2, 3, -4, 5};
    int abs_sum = accumulate(nums.begin(), nums.end(), 0, [](int total, int x) { return total + abs(x); });
    cout << " 数组：";
    for (auto& x : nums) cout << x << " ";
    cout << endl;
    cout << " |1| + |-2| + |3| + |-4| + |5| = " << abs_sum << endl;
    cout << endl;
    return 0;
}

八、其他算法（共 19 个）

1. count() 统计容器中等于指定值的元素个数。
2. find() 在容器中查找指定值第一次出现的位置，返回迭代器。
3. fill() 将容器中指定范围内的所有元素赋值为指定值。
4. swap() 交换两个变量的值。
5. reverse() 反转容器中指定范围的元素顺序。
6. shuffle() 随机重排容器中元素的顺序。
7. max()/ min() 返回两个值中的较大值/较小值。
8. abs() 计算绝对值。
9. exp() 计算自然指数 e^x。
10. log()/ log10()/ log2() 计算对数。
11. pow() 计算幂运算。
12. sqrt() 计算平方根。
13. sin()/ cos()/ tan() 三角函数。
14. asin()/ acos()/ atan() 反三角函数。
15. sinh()/ cosh()/ tanh() 双曲函数。
16. asinh()/ acosh()/ atanh() 反双曲函数。
17. ceil()/ floor() 向上/向下取整。
18. round() 四舍五入取整。
19. iota()(C++11) 用连续递增的值填充容器。

容器部分

一、vector

申明

• vector<类型名> 变量名

初始化

1. 指定大小初始化

vector<int> v0(5); // 创建包含 5 个元素的 vector

2. 指定大小和值初始化

vector<int> v1(5, 1); // 创建包含 5 个元素的 vector，每个元素为 1

3. 列表初始化

vector<int> v2{1, 2, 3}; // 用花括号初始化列表

4. 拷贝初始化

vector<int> v3(v1); // 用 v1 初始化 v3

5. 移动初始化

vector<int> v4(move(v1)); // 移动 v1 到 v4

6. 二维 vector 的初始化

vector<vector<int>> v4(2, vector<int>(8, 3)); // 创建 2×8 的二维 vector

7. 从数组初始化

int arr[] = {1, 2, 3, 4, 5};
vector<int> v7(arr, arr + 5); // 从数组范围初始化

8. 从另一个 vector 的部分初始化

vector<int> v8(v2.begin(), v2.begin() + 2); // 结果：1 2

输入/输出

• 输入：

for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    vi.push_back(x);
}

• 输出：

// 索引遍历
for (int i = 0; i < vi.size(); i++) {
    cout << vi[i] << endl;
}
// 使用范围 for 循环
for (auto& x : vi) {
    cout << x << endl;
}
// 迭代器
for (auto it = vi.begin(); it != vi.end(); it++) {
    cout << *it << endl;
}

常用成员函数

1.访问函数（Access）

1. at()：带边界检查的访问，如果索引越界会抛出异常
2. operator[]：快速访问元素，不检查边界
3. front()：访问第一个元素
4. back()：访问最后一个元素

2.迭代器函数（Iterators）

1. begin()：返回指向第一个元素的迭代器
2. end()：返回指向最后一个元素之后的迭代器

3.容量函数（Capacity）

1. empty()：检查 vector 是否为空
2. size()：返回当前元素个数
3. clear()：清空所有元素
4. reserve()：预留空间，避免频繁重新分配内存

4.修改函数（Modifiers）

1. insert()：在指定位置插入元素
2. erase()：删除指定位置或范围的元素
3. resize()：改变 vector 的大小
4. push_back()：在末尾添加元素
5. emplace_back()：在末尾直接构造元素，避免拷贝
6. pop_back()：移除末尾元素

比较运算

vector 支持以下比较运算符：==, !=, <, <=, >, >=。比较按照字典序进行。

注意事项

• insert 和 erase 的复杂度为 O(n)，非必要不使用
• push_back 时间复杂度可能会卡常，数据多不建议使用

二、queue

申明

• queue<类型名> 变量名

初始化

1. 默认构造（空队列）
2. 用其他容器初始化
3. 指定底层容器

输入/输出

• 输入：通常通过循环逐个元素输入
• 输出：只能从队首访问，要输出所有元素需要边出队边输出

常用成员函数

1.访问函数（Access）

1. front()：访问队首元素
2. back()：访问队尾元素

2.容量函数（Capacity）

1. empty()：检查队列是否为空
2. size()：返回队列中元素的个数

3.修改函数（Modifiers）

1. push()：在队尾插入元素
2. emplace()：在队尾直接构造元素
3. pop()：移除队首元素
4. swap()：交换两个队列的内容

注意事项

1. queue 不支持迭代器访问
2. queue 不支持随机访问
3. queue 是容器适配器，基于 deque、list 等容器实现
4. 先进先出 (FIFO)

三、stack

申明

• stack<类型名> 变量名

初始化

1. 默认构造（空栈）
2. 用其他容器初始化
3. 指定底层容器

输入/输出

• 输入：通常通过循环逐个元素输入
• 输出：只能从栈顶访问，要输出所有元素需要边出栈边输出

常用成员函数

1.访问函数（Access）

1. top()：访问栈顶元素

2.容量函数（Capacity）

1. empty()：检查栈是否为空
2. size()：返回栈中元素的个数

3.修改函数（Modifiers）

1. push()：在栈顶插入元素
2. emplace()：在栈顶直接构造元素
3. pop()：移除栈顶元素
4. swap()：交换两个栈的内容

注意事项

1. stack 不支持迭代器访问
2. stack 不支持随机访问
3. stack 是容器适配器，基于 deque、vector、list 等容器实现
4. 后进先出 (LIFO)

四、deque

申明

• deque<类型名> 变量名

初始化

1. 默认构造（空 deque）
2. 指定大小初始化
3. 列表初始化
4. 拷贝初始化
5. 移动初始化
6. 从数组初始化

输入/输出

• 输入：支持从两端交替输入
• 输出：支持索引遍历、范围 for 循环、迭代器

常用成员函数

1.访问函数（Access）

1. at()：带边界检查的访问
2. operator[]：下标访问
3. front()：访问第一个元素
4. back()：访问最后一个元素

2.迭代器函数（Iterators）

1. begin() / end()
2. rbegin() / rend()：反向迭代器

3.容量函数（Capacity）

1. empty() / size() / clear()

4.修改函数（Modifiers）

1. insert() / erase() / resize()
2. push_front() / emplace_front() / pop_front()
3. push_back() / emplace_back() / pop_back()
4. swap()

比较运算

deque 支持比较运算符，比较规则与 vector 类似（字典序）。

注意事项

1. deque 支持随机访问
2. deque 支持两端操作
3. deque 内部实现是分段连续空间
4. 中间位置的插入删除效率较低

五、priority_queue

申明

• priority_queue<类型名> 变量名

初始化

1. 默认构造（空优先队列）
2. 从容器初始化
3. 自定义比较函数初始化
4. 指定底层容器

输入/输出

• 输入：通常通过循环逐个元素输入
• 输出：只能访问顶部元素，要输出所有元素需要边弹出边输出

常用成员函数

1.访问函数（Access）

1. top()：访问顶部（优先级最高）的元素

2.容量函数（Capacity）

1. empty() / size()

3.修改函数（Modifiers）

1. push()：插入元素
2. emplace()：直接构造元素
3. pop()：移除顶部元素
4. swap()：交换两个优先队列的内容

注意事项

1. priority_queue 不支持迭代器访问
2. priority_queue 不支持随机访问
3. priority_queue 是容器适配器，基于 vector、deque 等容器实现
4. 默认是大顶堆，顶部元素是最大的
5. 内部实现通常是二叉堆

六、set

申明

• set<类型名> 变量名

初始化

1. 默认构造（空集合）
2. 列表初始化
3. 拷贝初始化
4. 从数组初始化
5. 自定义比较函数初始化

输入/输出

• 输入：set 通过插入元素输入
• 输出：使用范围 for 循环、迭代器遍历、反向遍历

常用成员函数

1.容量函数（Capacity）

1. empty() / size()

2.修改函数（Modifiers）

1. insert() / emplace() / erase() / clear()

3.查找函数（Lookup）

1. find() / count() / lower_bound() / upper_bound() / equal_range()

4.迭代器函数（Iterators）

1. begin() / end() / rbegin() / rend()

比较运算

set 支持比较运算符，比较规则与 vector 类似（字典序）。

注意事项

1. 元素自动排序，默认升序
2. 元素唯一，不允许重复
3. 插入删除时间复杂度：O(log n)
4. 不支持随机访问
5. 基于红黑树实现

七、multiset

申明

• multiset<类型名> 变量名

初始化

与 set 类似，但允许重复元素。

常用成员函数

multiset 的成员函数与 set 基本相同，但有以下区别：

1. count() 可以返回大于 1 的值
2. erase(key) 会删除所有等于 key 的元素
3. equal_range() 在 multiset 中更有用

注意事项

1. 允许重复元素
2. 其他特性与 set 相同

八、unordered_set

申明

• unordered_set<类型名> 变量名

初始化

1. 默认构造
2. 列表初始化
3. 从范围初始化

输入/输出

与 set 类似，但输出顺序不确定。

常用成员函数

unordered_set 的成员函数与 set 类似，但缺少排序相关函数，增加哈希相关函数。

比较运算

unordered_set 只支持 == 和 !=，不支持 <、<=、>、>=。

注意事项

1. 元素无序，不保证任何顺序
2. 元素唯一，不允许重复
3. 平均时间复杂度：O(1)，最坏 O(n)
4. 基于哈希表实现
5. 不支持反向迭代器

九、map

申明

• map<键类型，值类型> 变量名

初始化

1. 默认构造（空映射）
2. 列表初始化
3. 拷贝初始化
4. 从数组初始化
5. 自定义比较函数初始化

输入/输出

• 输入：map 通过插入键值对输入
• 输出：使用范围 for 循环、迭代器遍历、反向遍历

常用成员函数

1.容量函数（Capacity）

1. empty() / size()

2.修改函数（Modifiers）

1. insert() / emplace() / erase() / clear()
2. operator[]：访问或插入元素
3. at()：带边界检查的访问

3.查找函数（Lookup）

1. find() / count() / lower_bound() / upper_bound() / equal_range()

4.迭代器函数（Iterators）

1. begin() / end() / rbegin() / rend()

比较运算

map 支持比较运算符，比较规则与 vector 类似（字典序，按键比较）。

注意事项

1. 按键自动排序，默认升序
2. 键唯一，不允许重复键
3. 插入删除时间复杂度：O(log n)
4. 基于红黑树实现
5. operator[] 会自动插入不存在的键

十、multimap

申明

• multimap<键类型，值类型> 变量名

初始化

与 map 类似，但允许重复键。

常用成员函数

multimap 的成员函数与 map 基本相同，但有重要区别：

1. 不支持 operator[] 和 at()
2. insert() 总是成功
3. count() 可以返回大于 1 的值
4. equal_range() 在 multimap 中更有用

注意事项

1. 允许重复键
2. 不支持 operator[] 和 at()
3. 其他特性与 map 相同

十一、unordered_map

申明

• unordered_map<键类型，值类型> 变量名

初始化

1. 默认构造
2. 列表初始化
3. 从范围初始化

输入/输出

与 map 类似，但输出顺序不确定。

常用成员函数

unordered_map 的成员函数与 map 类似，但缺少排序相关函数，增加哈希相关函数。

比较运算

unordered_map 只支持 == 和 !=，不支持 <、<=、>、>=。

注意事项

1. 元素无序，不保证任何顺序
2. 键唯一，不允许重复键
3. 平均时间复杂度：O(1)，最坏 O(n)
4. 基于哈希表实现
5. 不支持反向迭代器

例题部分

一、【模板】栈

原题链接：B3614 【模板】栈 - 洛谷 题解：

#include <bits/stdc++.h>
using namespace std;
int main() {
    int T;
    cin >> T;
    while (T--) {
        stack<unsigned long long> stk;
        int n;
        cin >> n;
        while (n--) {
            char op[6];
            unsigned long long x;
            scanf("%s", op);
            if (strcmp(op, "push") == 0) {
                scanf("%llu", &x);
                stk.push(x);
            } else if (strcmp(op, "pop") == 0) {
                if (stk.empty()) {
                    cout << "Empty" << endl;
                } else {
                    stk.pop();
                }
            } else if (strcmp(op, "query") == 0) {
                if (stk.empty()) {
                    cout << "Anguei!" << endl;
                } else {
                    cout << stk.top() << endl;
                }
            } else {
                cout << stk.size() << endl;
            }
        }
    }
}

二、【模板】队列

原题链接：B3616 【模板】队列 - 洛谷 题解：

#include <bits/stdc++.h>
using namespace std;
int main() {
    queue<int> que;
    int n;
    cin >> n;
    while (n--) {
        int op, x;
        cin >> op;
        if (op == 1) {
            cin >> x;
            que.push(x);
        } else if (op == 2) {
            if (que.empty()) {
                cout << "ERR_CANNOT_POP" << endl;
            } else {
                que.pop();
            }
        } else if (op == 3) {
            if (que.empty()) {
                cout << "ERR_CANNOT_QUERY" << endl;
            } else {
                cout << que.front() << endl;
            }
        } else {
            cout << que.size() << endl;
        }
    }
}

三、[语言月赛 202303] Coin Selection G

原题链接：B3723 [语言月赛 202303] Coin Selection G - 洛谷 题解：

#include <bits/stdc++.h>
using namespace std;
int main() {
    using u64 = unsigned long long;
    multiset<u64> coins;
    int n;
    cin >> n;
    while (n--) {
        u64 coin;
        cin >> coin;
        coins.insert(coin);
    }
    u64 p1 = 0, p2 = 0;
    auto select = [&](u64 &sum) {
        auto iter = coins.upper_bound(sum);
        if (iter != coins.begin()) iter--;
        sum += *iter;
        coins.erase(iter);
    };
    while (!coins.empty()) {
        select(p1);
        if (coins.empty()) break;
        select(p2);
    }
    cout << p1 << ' ' << p2 << endl;
}

四、[语言月赛 202304] 你的牌太多了

原题链接：B3745 [语言月赛 202304] 你的牌太多了 - 洛谷 题解：

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m, r;
    cin >> n >> m >> r;
    vector<pair<int, int>> p1(n), p2(n);
    for (auto &[x, _] : p1) cin >> x;
    for (auto &[_, x] : p1) cin >> x;
    for (auto &[x, _] : p2) cin >> x;
    for (auto &[_, x] : p2) cin >> x;
    multiset<pair<int, int>> ms(p2.begin(), p2.end());
    while (n--) {
        int id;
        cin >> id;
        auto &card = p1[id - 1];
        auto iter = ms.upper_bound(card);
        if (iter != ms.end() && iter->first == card.first) {
            ms.erase(iter);
        }
    }
    cout << ms.size() << endl;
}

五、[语言月赛 202304] 洛谷评测机模拟器

原题链接：B3746 [语言月赛 202304] 洛谷评测机模拟器 - 洛谷 题解：

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> ans(n);
    using pli = pair<long long, int>;
    set<pli> s;
    for (int i = 0; i < n; i ++) {
        s.emplace(0, i);
    }
    for (int i = 1; i <= m; i ++) {
        int time;
        cin >> time;
        auto [total, id] = *s.begin();
        s.erase(s.begin());
        ans[id].push_back(i);
        s.emplace(total + time, id);
    }
    for (auto &line : ans) {
        if (line.size() == 0) {
            cout << "0" << endl;
            continue;
        }
        for (auto &x: line) {
            cout << x << ' ';
        }
        cout << endl;
    }
}

六、[语言月赛 202312] 铅球杯

原题链接：B3911 [语言月赛 202312] 铅球杯 - 洛谷 题解：

#include <bits/stdc++.h>
using namespace std;
int main() {
    unordered_map<string, int> mp;
    int n, k;
    cin >> n >> k;
    while (n--) {
        string key;
        int val;
        cin >> key >> val;
        mp.emplace(key, val);
    }
    string str;
    getline(cin, str);
    while (k --) {
        getline(cin, str);
        for (int i = 0; i < str.length(); i ++) {
            if (str[i] == '{') {
                int r = str.find('}', i + 1);
                string key = str.substr(i + 1, r - i - 1);
                int val = mp[key];
                str.replace(i, r - i + 1, to_string(val));
            }
        }
        cout << str << endl;
    }
}

七、A-B 数对

原题链接：P1102 A-B 数对 - 洛谷 题解：

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, c;
    cin >> n >> c;
    unordered_map<int, int> ump;
    long long ans = 0;
    while (n--) {
        int x;
        cin >> x;
        ans += ump[x + c];
        ans += ump[x - c];
        ump[x]++;
    }
    cout << ans << endl;
}

八、日志分析

原题链接：P1165 日志分析 - 洛谷 题解：

#include <bits/stdc++.h>
using namespace std;
int main() {
    multiset<int> values;
    stack<int> stk;
    int n;
    cin >> n;
    while (n--) {
        int op, val;
        cin >> op;
        if(op == 0) {
            cin >> val;
            stk.push(val);
            values.insert(val);
        } else if (op == 1){
            if (stk.empty()) continue;
            int top = stk.top();
            stk.pop();
            values.erase(top);
        } else {
            if (values.size() == 0) {
                cout << 0 << endl;
                continue;
            }
            cout << *values.rbegin() << endl;
        }
    }
}

九、瑞瑞的木板

原题链接：P1334 瑞瑞的木板 - 洛谷 题解：

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    using u64 = unsigned long long;
    priority_queue<u64, vector<u64>, greater<u64>> q;
    while (n--) {
        int x;
        cin >> x;
        q.push(x);
    }
    u64 ans = 0;
    while (q.size() > 1) {
        u64 top1 = q.top();
        q.pop();
        u64 top2 = q.top();
        q.pop();
        ans += top1 + top2;
        q.push(top1 + top2);
    }
    cout << ans << endl;
}

十、眼红的 Medusa

原题链接：P1571 眼红的 Medusa - 洛谷 题解：

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    vector<int> vec(n);
    unordered_set<int> s;
    for (auto &x : vec) cin >> x;
    while (m--) {
        int x;
        cin >> x;
        s.insert(x);
    }
    for (auto &x : vec) {
        if (s.count(x)) {
            cout << x << ' ';
        }
    }
    cout << endl;
}

十一、全排列问题

原题链接：P1706 全排列问题 - 洛谷 题解：

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) arr[i] = i + 1;
    do {
        for (int i = 0; i < n; i ++) {
            cout.width(5);
            cout << arr[i];
        }
        cout << endl;
    } while (next_permutation(arr.begin(), arr.end()));
}

十二、求第 k 小的数

原题链接：P1923 【深基 9.例 4】求第 k 小的数 - 洛谷 题解：

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, k;
    cin >> n >> k;
    vector<int> arr(n);
    for (auto &x : arr) scanf("%d", &x);
    nth_element(arr.begin(), arr.begin() + k, arr.end());
    cout << arr[k] << endl;
}

十三、约瑟夫问题

原题链接：P1996 约瑟夫问题 - 洛谷 题解：

#include <bits/stdc++.h>
using namespace std;
int main() {
    queue<int> que;
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) que.push(i);
    int cnt = 1;
    while (!que.empty()) {
        int id = que.front();
        que.pop();
        if (cnt == m) {
            cout << id << ' ';
            cnt = 1;
        } else {
            cnt ++;
            que.push(id);
        }
    }
}

十四、查找

原题链接：P2249 【深基 13.例 1】查找 - 洛谷 题解：

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    vector<int> arr(n);
    for (auto &x : arr) scanf("%d", &x);
    while (m--) {
        int x;
        scanf("%d", &x);
        auto iter = ranges::lower_bound(arr, x);
        if (iter != arr.end() && *iter == x) {
            cout << (iter - arr.begin() + 1) << ' ';
        } else {
            cout << -1 << ' ';
        }
    }
    cout << endl;
}

十五、【模板】堆

原题链接：P3378 【模板】堆 - 洛谷 题解：

#include <bits/stdc++.h>
using namespace std;
int main() {
    multiset<int> s;
    int n;
    cin >> n;
    while (n--) {
        int op, x;
        cin >> op;
        if (op == 1) {
            cin >> x;
            s.insert(x);
        } else if (op == 2) {
            cout << *s.begin() << endl;
        } else {
            s.erase(s.begin());
        }
    }
}

十六、寄包柜

原题链接：P3613 【深基 15.例 2】寄包柜 - 洛谷 题解：

#include <bits/stdc++.h>
using namespace std;
int main() {
    unordered_map<pair<int, int>, int, decltype([](const pair<int, int> &index) { return (size_t)index.first * 1e5 + index.second; })> mp;
    int n, q;
    cin >> n >> q;
    while (q--) {
        int op , i, j, k;
        cin >> op;
        if (op == 1) {
            cin >> i >> j >> k;
            mp[{i, j}] = k;
        } else {
            cin >> i >> j;
            cout << mp[{i, j}] << endl;
        }
    }
}

十七、[TJOI2010] 阅读理解

原题链接：P3879 [TJOI2010] 阅读理解 - 洛谷 题解：

#include <bits/stdc++.h>
using namespace std;
int main() {
    unordered_map<string, set<int>> mp;
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++) {
        int m;
        cin >> m;
        while (m--) {
            string str;
            cin >> str;
            mp[str].insert(i);
        }
    }
    int q;
    cin >> q;
    while (q--) {
        string str;
        cin >> str;
        for (auto &x : mp[str]) {
            cout << x << ' ';
        }
        cout << endl;
    }
}

十八、[JLOI2011] 不重复数字

原题链接：P4305 [JLOI2011] 不重复数字 - 洛谷 题解

#include <bits/stdc++.h>
using namespace std;
int main() {
    int T;
    cin >> T;
    while (T--) {
        set<int> us;
        int n;
        cin >> n;
        while (n--) {
            int x;
            scanf("%d", &x);
            if (!us.count(x)) {
                us.insert(x);
                printf("%d ", x);
            }
        }
        cout << endl;
    }
}

十九、验证栈序列

原题链接：P4387 【深基 15.习 9】验证栈序列 - 洛谷 解题思路： 题解：

#include <bits/stdc++.h>
using namespace std;
int main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<int> pushed(n), poped(n);
        for (auto &x : pushed) cin >> x;
        for (auto &x : poped) cin >> x;
        stack<int> stk;
        int index = 0;
        for (auto &x : pushed) {
            stk.push(x);
            while (!stk.empty() && poped[index] == stk.top()) {
                stk.pop();
                index ++;
            }
        }
        cout << (stk.empty() ? "Yes" : "No") << endl;
    }
}

二十、[蓝桥杯 2021 省 AB2] 负载均衡

原题链接：P8755 [蓝桥杯 2021 省 AB2] 负载均衡 - 洛谷 题解：

#include <bits/stdc++.h>
using namespace std;
int main() {
    using pli = pair<long long, int>;
    using pq = priority_queue<pli, vector<pli>, greater<pli>>;
    int n, m;
    cin >> n >> m;
    vector<pair<long long, pq>> computes(n);
    for (auto &[v, _] : computes) cin >> v;
    while (m--) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        auto &[v, q] = computes[b - 1];
        while (!q.empty() && q.top().first <= a) {
            v += q.top().second;
            q.pop();
        }
        if (d > v) {
            cout << -1 << endl;
            continue;
        }
        v -= d;
        q.emplace(a + c, d);
        cout << v << endl;
    }
}