最新资讯

概述

C++ 标准模板库（Standard Template Library，STL）是一套功能强大的 C++ 模板类和函数的集合，它提供了一系列通用的、可复用的算法和数据结构。

本文将讲解C++11中最常用的STL及其用法，附带例题。

算法部分

一、sort

• 作用：对指定范围内的元素进行排序，默认按升序排列，也可通过自定义比较器指定排序规则

• 模板：sort(iterator begin,interator end,function comp)

• 复杂度： $O(n\log n)$

• Function Comp：自定义比较器

• 预定义函数对象：最常用greater< >()，用于实现降序排序

• 代码案例：

#include "bits/stdc++.h"
using namespace std;
int main() {
  vector  v1 = {9, 5, 1, 2, 4, 6, 8, 3, 0, 7};
  vector  v2 = {9, 5, 1, 2, 4, 6, 8, 3, 0, 7};
  vector  v3 = {9, 5, 1, 2, 4, 6, 8, 3, 0, 7};
  // 1.默认从小到大的升序排序
  sort(v1.begin(), v1.end());
  for (auto& x : v1){
    cout << x <<" ";
  }
  cout << endl;

  // 2.使用预定义函数对象实现降序排序
  sort(v2.begin(), v2.end(), greater ());
  //等价于sort(v2.begin(), v2.end(), [](int x, int y){return x > y;});
  for (auto& x : v2){
    cout << x <<" ";
  }
  cout << endl;

  // 3.使用自定义函数实现任意排序
  sort(v3.begin(), v3.end(), [](int a, int b) {
        // 比较奇偶性是否相同
        if ((a % 2) != (b % 2)) {
            // 奇偶性不同，奇数优先
            return (a % 2) > (b % 2);
        }
        // 奇偶性相同，按数值排序
        return a < b;
    });
    for (auto& x : v3){
    cout << x <<" ";
  }
  cout << endl;
}

二、nth_element

• 作用：部分排序，用于重新排列元素，使得第 n 个位置的元素处于其排序后的正确位置，但不保证其他元素的完全有序。

• 模板：nth_element(Iterator begin, Iterator nth, Iterator end, fuction comp)

• 复杂度：$O(n)$

• Function Comp：自定义比较器

• 预定义函数对象：最常用greater< >()，用于实现降序排序

• 代码案例：

#include "bits/stdc++.h"
using namespace std;
int main() {
    vector v1 = {5, 2, 8, 1, 9, 3, 6, 4, 7, 0};
    vector v2 = {5, 2, 8, 1, 9, 3, 6, 4, 7, 0};
    vector v3 = {5, 2, 8, 1, 9, 3, 6, 4, 7, 0};
    vector 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] << " ";  // 输出: 0 1 2（不一定有序）
    }
    cout << endl;

    // 3.使用自定义预定义函数对象
    nth_element(v3.begin(), v3.begin() + 2, v3.end(), greater());
    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{ // 数组元素个数为偶
        // 先找到第n/2个元素，放在位置n/2
        nth_element(v4.begin(), v4.begin() + nums/2, v4.end());
        int right_mid = v4[nums/2];
        // 再在左边部分找到第n/2-1个元素，即左边部分的最大值
        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(logn)$

• Type v：目标值

• Function Comp：自定义比较器

• 预定义函数对象：最常用greater< >()，用于实现降序排序

• 代码案例：

#include "bits/stdc++.h"
using namespace std;

int main() {
    vector 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 v_desc = {9, 7, 5, 5, 5, 3, 1};
    int target5 = 5;
    auto lb5 = lower_bound(v_desc.begin(), v_desc.end(), target5, greater());
    auto ub5 = upper_bound(v_desc.begin(), v_desc.end(), target5, greater());
    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 v1 = {1, 2, 3};
    vector v2 = {1, 2, 3};
    vector 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 生成所有排列
    // 注意：使用 prev_permutation 前需要先降序排序
    sort(v2.begin(), v2.end(), greater());
    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 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)$

• fuction matcher：自定义比较函数

• 代码案例：

#include "bits/stdc++.h"
using namespace std;
int main() {
    // 注意：unique 只去除相邻的重复元素
    vector v1 = {1, 1, 2, 2, 2, 3, 3, 4, 4, 4, 5};
    vector v2 = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
    vector v3 = {1, 3, 2, 4, 6, 5, 7, 9, 8};
    vector v4 = {12, 15, 18, 23, 25, 34, 37, 45, 48};

    // 1. 默认用法：去除相邻重复元素
    cout << "1. 默认用法（去除相邻重复元素）:" << endl;
    vector 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 temp2 = v2;  // 复制一份
    // 第一步：排序
    sort(temp2.begin(), temp2.end());
    cout << "   排序后: ";
    for (auto& x : temp2) cout << x << " ";
    cout << endl;

    // 第二步：使用unique
    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, fuction comp)

• 复杂度：$O(n)$

• Function Comp：自定义比较器

• 代码案例：

#include "bits/stdc++.h"
using namespace std;
int main() {
    vector v1 = {9, 5, 1, 2, 4, 6, 8, 3, 0, 7};
    vector v2 = {9, 5, 1, 2, 4, 6, 8, 3, 0, 7};
    vector 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()

• 代码案例：

#include "bits/stdc++.h"
using namespace std;
int main() {
    vector v1 = {1, 2, 3, 4, 5};
    vector v2 = {1, 2, 3, 4, 5};
    vector 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());
    cout << "   1×2×3×4×5 = " << product << endl;
    cout << endl;

    // 3. 使用自定义函数（绝对值累加）
    vector 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()
   统计容器中等于指定值的元素个数。例如：count(v.begin(), v.end(), 5)统计值为5的元素个数。

2. find()
   在容器中查找指定值第一次出现的位置，返回迭代器。例如：find(v.begin(), v.end(), 5)查找第一个5的位置。

3. fill()
   将容器中指定范围内的所有元素赋值为指定值。例如：fill(v.begin(), v.end(), 0)将所有元素设为0。

4. swap()
   交换两个变量的值。例如：swap(a, b)交换a和b的值。

5. reverse()
   反转容器中指定范围的元素顺序。例如：reverse(v.begin(), v.end())将整个容器反转。

6. shuffle()
   随机重排容器中元素的顺序。例如：shuffle(v.begin(), v.end(), rng)使用随机数生成器重排。

7. max()/ min()
   返回两个值中的较大值/较小值。例如：max(a, b)返回a和b中的较大值。

8. abs()
   计算绝对值。例如：abs(-5)返回5。

9. exp()
   计算自然指数 e^x。例如：exp(1)返回e的1次方。

10. log()/ log10()/ log2()
    计算对数：

    • log()：自然对数（以e为底）
    • log10()：常用对数（以10为底）
    • log2()：二进制对数（以2为底）

11. pow()
    计算幂运算。例如：pow(2, 3)返回2的3次方（8）。

12. sqrt()
    计算平方根。例如：sqrt(16)返回4。

13. sin()/ cos()/ tan()
    三角函数：

    • sin()：正弦函数
    • cos()：余弦函数
    • tan()：正切函数

14. asin()/ acos()/ atan()
    反三角函数：

    • asin()：反正弦函数
    • acos()：反余弦函数
    • atan()：反正切函数

15. sinh()/ cosh()/ tanh()
    双曲函数：

    • sinh()：双曲正弦函数
    • cosh()：双曲余弦函数
    • tanh()：双曲正切函数

16. asinh()/ acosh()/ atanh()
    反双曲函数：

    • asinh()：反双曲正弦函数
    • acosh()：反双曲余弦函数
    • atanh()：反双曲正切函数

17. ceil()/ floor()
    向上/向下取整：

    • ceil()：向上取整（不小于原数的最小整数）
    • floor()：向下取整（不大于原数的最大整数）

18. round()
    四舍五入取整。例如：round(3.14)返回3，round(3.6)返回4。

19. iota()(C++11)
    用连续递增的值填充容器。例如：iota(v.begin(), v.end(), 1)用1, 2, 3…填充容器。

容器部分

一、vector

申明

• vector<类型名> 变量名

初始化

1. 指定大小初始化

vector v0(5);  // 创建包含5个元素的vector
// 结果: 0 0 0 0 0

2. 指定大小和值初始化

vector v1(5, 1);  // 创建包含5个元素的vector，每个元素为1
// 结果: 1 1 1 1 1

3. 列表初始化

vector v2{1, 2, 3};  // 用花括号初始化列表
// 等同于vector v2 = {1, 2, 3};
// 结果: 1 2 3

4. 拷贝初始化

vector v3(v1);  // 用v1初始化v3
// 结果: 1 1 1 1 1 （与v1相同）

5. 移动初始化

vector v4(move(v1));  // 移动v1到v4
// v1变为空，v4获得v1的所有元素

6. 二维vector的初始化

vector> v4(2, vector(8, 3));
// 创建2×8的二维vector，每个元素为3
// 结果: 
// 第0行: 3 3 3 3 3 3 3 3
// 第1行: 3 3 3 3 3 3 3 3

7. 从数组初始化

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

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

vector v8(v2.begin(), v2.begin() + 2);
// 结果: 1 2 （v2的前2个元素）

输入/输出

• 输入：

1. 基本输入

for (int i = 0; i < n; i++) {
    int x;                // 临时变量存储输入值
    cin >> x;             // 读取一个整数
    vi.push_back(x);      // 将整数添加到 vector 末尾
}

• 输出：

1. 索引遍历

for (int i = 0; i < vi.size(); i++) {
    cout << vi[i] << endl;  // 输出每个元素，每行一个
}

2. 使用范围 for 循环

for (auto& x : vi) {
    cout << x << endl;  // 输出每个元素，每行一个
}

3. 迭代器

for (auto it = vi.begin(); it != vi.end(); it++) {
    cout << *it << endl;
}

常用成员函数

1.访问函数（Access）

1. at()

• 功能：带边界检查的访问，如果索引越界会抛出异常
• 用法：vector.at(index)
• 示例：

vector v = {1, 2, 3, 4, 5};
cout << v.at(2) << endl;  // 输出: 3
// 若cout << v.at(10) << endl;  
// 会抛出 std::out_of_range 异常

2. operator[]（下标访问）

• 功能：快速访问元素，不检查边界
• 用法：vector[index]
• 示例：

vector v = {1, 2, 3, 4, 5};
cout << v[2] << endl;  // 输出: 3
// cout << v[10] << endl;  // 可能崩溃或返回错误值

3. front()

• 功能：访问第一个元素
• 用法：vector.front()
• 示例：

vector v = {1, 2, 3, 4, 5};
cout << v.front() << endl;  // 输出: 1

4. back()

• 功能：访问最后一个元素
• 用法：vector.back()
• 示例：

vector v = {1, 2, 3, 4, 5};
cout << v.back() << endl;  // 输出: 5

2.迭代器函数（Iterators）

1. begin()

• 功能：返回指向第一个元素的迭代器
• 用法：vector.begin()
• 示例：

vector v = {1, 2, 3, 4, 5};
auto it = v.begin();
cout << *it << endl;  // 输出: 1

2. end()

• 功能：返回指向最后一个元素之后的迭代器
• 用法：vector.end()
• 示例：

vector v = {1, 2, 3};
for (auto it = v.begin(); it != v.end(); it++) {
    cout << *it << " ";  // 输出: 1 2 3
}

3.容量函数（Capacity）

1. empty()

• 功能：检查vector是否为空
• 用法：vector.empty()
• 示例：

vector v1 = {1, 2, 3};
vector v2;
cout << v1.empty() << endl;  // 输出: 0 (false)
cout << v2.empty() << endl;  // 输出: 1 (true)

2. size()

• 功能：返回当前元素个数
• 用法：vector.size()
• 示例：

vector v = {1, 2, 3, 4, 5};
cout << v.size() << endl;  // 输出: 5

3. clear()

• 功能：清空所有元素
• 用法：vector.clear()
• 示例：

vector v = {1, 2, 3, 4, 5};
cout << "清空前大小: " << v.size() << endl;  // 输出: 5
v.clear();
cout << "清空后大小: " << v.size() << endl;  // 输出: 0

4. reserve()

• 功能：预留空间，避免频繁重新分配内存
• 用法：vector.reserve(n)
• 示例：

vector v;
cout << "初始容量: " << v.capacity() << endl;  // 可能为0
v.reserve(100);
cout << "预留后容量: " << v.capacity() << endl;  // 至少100

4.修改函数（Modifiers）

1. insert()

• 功能：在指定位置插入元素
• 用法：vector.insert(position, value)
• 示例：

vector v = {1, 3, 4, 5};
auto it = v.begin() + 1;  // 指向3的位置
v.insert(it, 2);  // 在3之前插入2
// 现在v = {1, 2, 3, 4, 5}

2. erase()

• 功能：删除指定位置或范围的元素
• 用法：vector.erase(position)或 vector.erase(first, last)
• 示例：

vector v = {1, 2, 3, 4, 5};
// 删除第三个元素(3)
v.erase(v.begin() + 2);
// 现在v = {1, 2, 4, 5}
// 删除前两个元素
v.erase(v.begin(), v.begin() + 2);
// 现在v = {4, 5}

3. resize()

• 功能：改变vector的大小
• 用法：vector.resize(new_size)或 vector.resize(new_size, value)
• 示例：

vector v = {1, 2, 3};
v.resize(5);  // 增大，新元素初始化为0
// 现在v = {1, 2, 3, 0, 0}

v.resize(2);  // 缩小
// 现在v = {1, 2}

4. push_back()

• 功能：在末尾添加元素
• 用法：vector.push_back(value)
• 示例：

vector v = {1, 2, 3};
v.push_back(4);
v.push_back(5);
// 现在v = {1, 2, 3, 4, 5}

5. emplace_back()

• 功能：在末尾直接构造元素，避免拷贝
• 用法：vector.emplace_back(args...)
• 示例：

vector> v;
v.emplace_back(1, "one");  // 直接在末尾构造pair
v.push_back(make_pair(2, "two"));  // 先构造再拷贝
// 现在v = {{1, "one"}, {2, "two"}}

6. pop_back()

• 功能：移除末尾元素
• 用法：vector.pop_back()
• 示例：

vector v = {1, 2, 3, 4, 5};
v.pop_back();  // 移除5
v.pop_back();  // 移除4
// 现在v = {1, 2, 3}

比较运算

1. 基本比较操作

vector v0{1, 2, 3};
vector v2{1, 2, 4};
bool result = v0 < v2;  // 比较 v0 是否小于 v2
// result = true，因为 3 < 4

2. 支持的比较运算符
   vector 支持以下比较运算符：

• ==：相等
• !=：不等
• <：小于
• <=：小于等于
• >：大于
• >=：大于等于

2. 比较规则
   比较按照字典序（lexicographical comparison）：

• 从左到右比较对应位置的元素
• 第一个不相同的元素决定比较结果
• 如果所有对应元素都相等，较短的 vector 较小

注意事项

• insert和erase的复杂度为$O(n)$，非必要不使用

• push_back时间复杂度可能会卡常，数据多不建议使用

二、queue

申明

• queue<类型名> 变量名

初始化

queue不支持直接列表初始化，通常通过以下方式初始化：

1. 默认构造（空队列）

queue q1;  // 创建空队列
// 结果: []

2. 用其他容器初始化

deque dq{1, 2, 3, 4, 5};
queue q2(dq);  // 用deque初始化queue
// 结果: 队首←1 2 3 4 5←队尾

3. 用list初始化

list lst{1, 2, 3};
queue> q3(lst);  // 指定list为底层容器
// 结果: 队首←1 2 3←队尾

4. 指定底层容器

// 默认底层容器是deque，但可以指定为list
queue> q4;  // 使用list作为底层容器
// 结果: []

输入/输出

• 输入：
  queue通常通过循环逐个元素输入

queue q;
int n, x;
cin >> n;  // 输入队列中元素个数
for (int i = 0; i < n; i++) {
    cin >> x;     // 读取一个整数
    q.push(x);    // 将整数入队
}

• 输出：
  queue只能从队首访问，要输出所有元素需要边出队边输出

// 方法1：输出并清空队列
while (!q.empty()) {
    cout << q.front() << " ";  // 输出队首元素
    q.pop();                    // 移除队首元素
}
cout << endl;

// 方法2：复制队列后输出（不破坏原队列）
queue q_copy = q;  // 复制队列
while (!q_copy.empty()) {
    cout << q_copy.front() << " ";
    q_copy.pop();
}
cout << endl;

常用成员函数

1. 访问函数（Access）

1. front()
   • 功能：访问队首元素
   • 用法：queue.front()
   • 示例：

queue q;
q.push(1);
q.push(2);
q.push(3);
cout << q.front() << endl;  // 输出: 1

2. back()
   • 功能：访问队尾元素
   • 用法：queue.back()
   • 示例：

queue q;
q.push(1);
q.push(2);
q.push(3);
cout << q.back() << endl;  // 输出: 3

2. 容量函数（Capacity）

1. empty()
   • 功能：检查队列是否为空
   • 用法：queue.empty()
   • 示例：

queue q1;
queue q2;
q2.push(1);
cout << q1.empty() << endl;  // 输出: 1 (true)
cout << q2.empty() << endl;  // 输出: 0 (false)

2. size()
   • 功能：返回队列中元素的个数
   • 用法：queue.size()
   • 示例：

queue q;
q.push(1);
q.push(2);
q.push(3);
cout << q.size() << endl;  // 输出: 3

3. 修改函数（Modifiers）

1. push()
   • 功能：在队尾插入元素
   • 用法：queue.push(value)
   • 示例：

queue q;
q.push(1);  // 队列: 1
q.push(2);  // 队列: 1 2
q.push(3);  // 队列: 1 2 3

2. emplace()
   • 功能：在队尾直接构造元素，避免拷贝
   • 用法：queue.emplace(args...)
   • 示例：

queue> q;
q.emplace(1, "one");     // 直接在队尾构造pair
q.push(make_pair(2, "two"));  // 先构造再拷贝
// 队列包含: {1, "one"} {2, "two"}

3. pop()
   • 功能：移除队首元素
   • 用法：queue.pop()
   • 示例：

queue q;
q.push(1);
q.push(2);
q.push(3);
q.pop();  // 移除1
cout << q.front() << endl;  // 输出: 2

4. swap()
   • 功能：交换两个队列的内容
   • 用法：queue1.swap(queue2)
   • 示例：

queue q1, q2;
q1.push(1);
q1.push(2);
q2.push(3);
q1.swap(q2);
// 现在q1包含: 3
// q2包含: 1 2

注意事项

1. queue不支持迭代器访问，不能使用begin()、end()等函数

2. queue不支持随机访问，不能通过下标访问元素

3. queue是容器适配器，基于deque、list等容器实现

4. 先进先出(FIFO)：元素总是从队尾插入，从队首删除

三、stack

申明

• stack<类型名> 变量名

初始化

stack不支持直接列表初始化，通常通过以下方式初始化：

1. 默认构造（空栈）

stack s1;  // 创建空栈
// 结果: [] (栈顶在右)

2. 用其他容器初始化

deque dq{1, 2, 3, 4, 5};
stack s2(dq);  // 用deque初始化stack
// 结果: 栈底←1 2 3 4 5←栈顶

3. 用vector初始化

vector vec{1, 2, 3};
stack> s3(vec);  // 指定vector为底层容器
// 结果: 栈底←1 2 3←栈顶

4. 用list初始化

list lst{1, 2, 3};
stack> s4(lst);  // 指定list为底层容器
// 结果: 栈底←1 2 3←栈顶

5. 指定底层容器

// 默认底层容器是deque，但可以指定为vector或list
stack> s5;  // 使用vector作为底层容器
// 结果: []

输入/输出

• 输入：
  stack通常通过循环逐个元素输入

stack s;
int n, x;
cin >> n;  // 输入栈中元素个数
for (int i = 0; i < n; i++) {
    cin >> x;     // 读取一个整数
    s.push(x);    // 将整数压栈
}

• 输出：
  stack只能从栈顶访问，要输出所有元素需要边出栈边输出

// 方法1：输出并清空栈（元素会逆序输出）
while (!s.empty()) {
    cout << s.top() << " ";  // 输出栈顶元素
    s.pop();                 // 移除栈顶元素
}
cout << endl;

// 方法2：复制栈后输出（不破坏原栈）
stack s_copy = s;  // 复制栈
while (!s_copy.empty()) {
    cout << s_copy.top() << " ";
    s_copy.pop();
}
cout << endl;

// 方法3：保持原栈顺序输出（需要使用辅助栈）
stack temp;
while (!s.empty()) {
    cout << s.top() << " ";  // 从栈顶到栈底输出
    temp.push(s.top());      // 保存元素
    s.pop();
}
cout << endl;
// 恢复原栈
while (!temp.empty()) {
    s.push(temp.top());
    temp.pop();
}

常用成员函数

1. 访问函数（Access）

1. top()
   • 功能：访问栈顶元素
   • 用法：stack.top()
   • 示例：

stack s;
s.push(1);
s.push(2);
s.push(3);
cout << s.top() << endl;  // 输出: 3

2. 容量函数（Capacity）

1. empty()
   • 功能：检查栈是否为空
   • 用法：stack.empty()
   • 示例：

stack s1;
stack s2;
s2.push(1);
cout << s1.empty() << endl;  // 输出: 1 (true)
cout << s2.empty() << endl;  // 输出: 0 (false)

2. size()
   • 功能：返回栈中元素的个数
   • 用法：stack.size()
   • 示例：

stack s;
s.push(1);
s.push(2);
s.push(3);
cout << s.size() << endl;  // 输出: 3

3. 修改函数（Modifiers）

1. push()
   • 功能：在栈顶插入元素
   • 用法：stack.push(value)
   • 示例：

stack s;
s.push(1);  // 栈: 1 (栈底) ← 栈顶
s.push(2);  // 栈: 1 2
s.push(3);  // 栈: 1 2 3

2. emplace()
   • 功能：在栈顶直接构造元素，避免拷贝
   • 用法：stack.emplace(args...)
   • 示例：

stack> s;
s.emplace(1, "one");     // 直接在栈顶构造pair
s.push(make_pair(2, "two"));  // 先构造再拷贝
// 栈包含: {1, "one"} {2, "two"} (从栈底到栈顶)

3. pop()
   • 功能：移除栈顶元素
   • 用法：stack.pop()
   • 示例：

stack s;
s.push(1);
s.push(2);
s.push(3);
s.pop();  // 移除3
cout << s.top() << endl;  // 输出: 2

4. swap()(C++11)
   • 功能：交换两个栈的内容
   • 用法：stack1.swap(stack2)
   • 示例：

stack s1, s2;
s1.push(1);
s1.push(2);
s2.push(3);
s1.swap(s2);
// 现在s1包含: 3
// s2包含: 1 2

注意事项

1. stack不支持迭代器访问，不能使用begin()、end()等函数

2. stack不支持随机访问，不能通过下标访问元素

3. stack是容器适配器，基于deque、vector、list等容器实现

4. 后进先出(LIFO)：元素总是从栈顶插入和删除

5. 只能访问栈顶元素，不能直接访问中间或栈底元素

四、deque

申明

• deque<类型名> 变量名

初始化

1. 默认构造（空deque）

deque dq0;  // 创建空deque
// 结果: []

2. 指定大小初始化

deque dq1(5);  // 创建包含5个元素的deque
// 结果: 0 0 0 0 0

3. 指定大小和值初始化

deque dq2(5, 1);  // 创建包含5个元素的deque，每个元素为1
// 结果: 1 1 1 1 1

4. 列表初始化

deque dq3{1, 2, 3};  // 用花括号初始化列表
// 等同于deque dq3 = {1, 2, 3};
// 结果: 1 2 3

5. 拷贝初始化

deque dq4(dq2);  // 用dq2初始化dq4
// 结果: 1 1 1 1 1 （与dq2相同）

6. 移动初始化

deque dq5(move(dq2));  // 移动dq2到dq5
// dq2变为空，dq5获得dq2的所有元素

7. 从数组初始化

int arr[] = {1, 2, 3, 4, 5};
deque dq6(arr, arr + 5);  // 从数组范围初始化
// 结果: 1 2 3 4 5

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

deque dq7(dq3.begin(), dq3.begin() + 2);
// 结果: 1 2 （dq3的前2个元素）

输入/输出

• 输入：

1. 基本输入

deque dq;
int n, x;
cin >> n;  // 输入deque中元素个数
for (int i = 0; i < n; i++) {
    cin >> x;     // 读取一个整数
    dq.push_back(x);  // 从尾部添加元素
}

2. 从两端交替输入

deque dq;
int n, x;
cin >> n;
for (int i = 0; i < n; i++) {
    cin >> x;
    if (i % 2 == 0) {
        dq.push_back(x);  // 偶数索引从尾部添加
    } else {
        dq.push_front(x); // 奇数索引从头部添加
    }
}

• 输出：

1. 索引遍历

for (int i = 0; i < dq.size(); i++) {
    cout << dq[i] << " ";  // 输出每个元素
}
cout << endl;

2. 使用范围for循环

for (auto& x : dq) {
    cout << x << " ";  // 输出每个元素
}
cout << endl;

3. 迭代器

for (auto it = dq.begin(); it != dq.end(); it++) {
    cout << *it << " ";  // 输出每个元素
}
cout << endl;

4. 从头部开始输出

// 从头部开始输出
deque dq_copy = dq;
while (!dq_copy.empty()) {
    cout << dq_copy.front() << " ";
    dq_copy.pop_front();
}
cout << endl;

常用成员函数

1.访问函数（Access）

1. at()
   • 功能：带边界检查的访问，如果索引越界会抛出异常
   • 用法：deque.at(index)
   • 示例：

deque dq = {1, 2, 3, 4, 5};
cout << dq.at(2) << endl;  // 输出: 3
// 若cout << dq.at(10) << endl;  
// 会抛出 std::out_of_range 异常

2. operator[]（下标访问）
   • 功能：快速访问元素，不检查边界
   • 用法：deque[index]
   • 示例：

deque dq = {1, 2, 3, 4, 5};
cout << dq[2] << endl;  // 输出: 3
// cout << dq[10] << endl;  // 可能崩溃或返回错误值

3. front()
   • 功能：访问第一个元素
   • 用法：deque.front()
   • 示例：

deque dq = {1, 2, 3, 4, 5};
cout << dq.front() << endl;  // 输出: 1

4. back()
   • 功能：访问最后一个元素
   • 用法：deque.back()
   • 示例：

deque dq = {1, 2, 3, 4, 5};
cout << dq.back() << endl;  // 输出: 5

2.迭代器函数（Iterators）

1. begin()
   • 功能：返回指向第一个元素的迭代器
   • 用法：deque.begin()
   • 示例：

deque dq = {1, 2, 3, 4, 5};
auto it = dq.begin();
cout << *it << endl;  // 输出: 1

2. end()
   • 功能：返回指向最后一个元素之后的迭代器
   • 用法：deque.end()
   • 示例：

deque dq = {1, 2, 3};
for (auto it = dq.begin(); it != dq.end(); it++) {
    cout << *it << " ";  // 输出: 1 2 3
}

3. rbegin()和 rend()
   • 功能：返回反向迭代器
   • 用法：
   • rbegin()：指向最后一个元素
   • rend()：指向第一个元素之前
   • 示例：

deque dq = {1, 2, 3};
for (auto it = dq.rbegin(); it != dq.rend(); it++) {
    cout << *it << " ";  // 输出: 3 2 1 （逆序输出）
}

3.容量函数（Capacity）

1. empty()
   • 功能：检查deque是否为空
   • 用法：deque.empty()
   • 示例：

deque dq1 = {1, 2, 3};
deque dq2;
cout << dq1.empty() << endl;  // 输出: 0 (false)
cout << dq2.empty() << endl;  // 输出: 1 (true)

2. size()
   • 功能：返回当前元素个数
   • 用法：deque.size()
   • 示例：

deque dq = {1, 2, 3, 4, 5};
cout << dq.size() << endl;  // 输出: 5

3. clear()
   • 功能：清空所有元素
   • 用法：deque.clear()
   • 示例：

deque dq = {1, 2, 3, 4, 5};
cout << "清空前大小: " << dq.size() << endl;  // 输出: 5
dq.clear();
cout << "清空后大小: " << dq.size() << endl;  // 输出: 0

4.修改函数（Modifiers）

1. insert()
   • 功能：在指定位置插入元素
   • 用法：
   • deque.insert(position, value)：在指定位置插入一个元素
   • deque.insert(position, n, value)：在指定位置插入n个value
   • deque.insert(position, first, last)：在指定位置插入范围元素
   • 示例：

deque dq = {1, 3, 4, 5};
// 在3之前插入2
auto it = dq.begin() + 1;
dq.insert(it, 2);
// 现在dq = {1, 2, 3, 4, 5}

// 在开头插入3个0
dq.insert(dq.begin(), 3, 0);
// 现在dq = {0, 0, 0, 1, 2, 3, 4, 5}

2. erase()
   • 功能：删除指定位置或范围的元素
   • 用法：
   • deque.erase(position)：删除指定位置元素
   • deque.erase(first, last)：删除范围元素
   • 示例：

deque dq = {1, 2, 3, 4, 5};
// 删除第三个元素(3)
dq.erase(dq.begin() + 2);
// 现在dq = {1, 2, 4, 5}

// 删除前两个元素
dq.erase(dq.begin(), dq.begin() + 2);
// 现在dq = {4, 5}

3. resize()
   • 功能：改变deque的大小
   • 用法：
   • deque.resize(new_size)：改变大小，新元素默认构造
   • deque.resize(new_size, value)：改变大小，新元素为value
   • 示例：

deque dq = {1, 2, 3};
dq.resize(5);  // 增大，新元素初始化为0
// 现在dq = {1, 2, 3, 0, 0}

dq.resize(2);  // 缩小
// 现在dq = {1, 2}

4. push_front()
   • 功能：在头部添加元素
   • 用法：deque.push_front(value)
   • 示例：

deque dq = {2, 3};
dq.push_front(1);  // 在头部添加1
// 现在dq = {1, 2, 3}

5. emplace_front()
   • 功能：在头部直接构造元素，避免拷贝
   • 用法：deque.emplace_front(args...)
   • 示例：

deque> dq;
dq.emplace_front(1, "one");  // 在头部直接构造pair
// 现在dq = {{1, "one"}}

6. push_back()
   • 功能：在尾部添加元素
   • 用法：deque.push_back(value)
   • 示例：

deque dq = {1, 2};
dq.push_back(3);  // 在尾部添加3
// 现在dq = {1, 2, 3}

7. emplace_back()
   • 功能：在尾部直接构造元素，避免拷贝
   • 用法：deque.emplace_back(args...)
   • 示例：

deque> dq;
dq.emplace_back(1, "one");  // 在尾部直接构造pair
// 现在dq = {{1, "one"}}

8. pop_front()
   • 功能：移除头部元素
   • 用法：deque.pop_front()
   • 示例：

deque dq = {1, 2, 3, 4, 5};
dq.pop_front();  // 移除1
// 现在dq = {2, 3, 4, 5}

9. pop_back()
   • 功能：移除尾部元素
   • 用法：deque.pop_back()
   • 示例：

deque dq = {1, 2, 3, 4, 5};
dq.pop_back();  // 移除5
// 现在dq = {1, 2, 3, 4}

10. swap()
    • 功能：交换两个deque的内容
    • 用法：deque1.swap(deque2)
    • 示例：

deque dq1 = {1, 2, 3};
deque dq2 = {4, 5};
dq1.swap(dq2);
// 现在dq1 = {4, 5}, dq2 = {1, 2, 3}

比较运算

1. 基本比较操作

deque dq1{1, 2, 3};
deque dq2{1, 2, 4};
bool result = dq1 < dq2;  // 比较dq1是否小于dq2
// result = true，因为3 < 4

2. 支持的比较运算符
   deque支持以下比较运算符：
   • ==：相等
   • !=：不等
   • <：小于
   • <=：小于等于
   • >：大于
   • >=：大于等于
3. 比较规则
   比较按照字典序（lexicographical comparison）：
   • 从左到右比较对应位置的元素
   • 第一个不相同的元素决定比较结果
   • 如果所有对应元素都相等，较短的deque较小

注意事项

1. deque支持随机访问，可以通过下标[]或at()访问任意位置

2. deque支持两端操作，可以在头部和尾部高效插入删除

3. deque内部实现是分段连续空间，比vector在头部插入更高效

4. 中间位置的插入删除：时间复杂度为O(n)，效率较低

5. 内存不连续：deque的内存是分段连续的，不是完全连续

五、priority_queue

申明

• priority_queue<类型名> 变量名

初始化

1. 默认构造（空优先队列）

priority_queue pq1;  // 创建空的大顶堆
// 结果: []

2. 从容器初始化

vector vec{3, 1, 4, 1, 5, 9};
priority_queue pq2(vec.begin(), vec.end());  // 用vector初始化
// 结果: 9 5 4 3 1 1 (内部存储顺序，顶部是9)

3. 自定义比较函数初始化

// 小顶堆
priority_queue, greater> pq3;  // 小顶堆
// 结果: [] (顶部是最小元素)

// 使用自定义比较函数
struct Compare {
    bool operator()(int a, int b) {
        return a > b;  // 小顶堆
    }
};
priority_queue, Compare> pq4;

4. 指定底层容器

// 默认底层容器是vector
priority_queue> pq5;  // 明确指定vector
priority_queue> pq6;  // 指定deque作为底层容器

5. 用数组初始化

int arr[] = {3, 1, 4, 1, 5, 9};
priority_queue pq7(arr, arr + 6);  // 用数组范围初始化
// 结果: 顶部是9

6. 用其他priority_queue初始化

priority_queue pq8(pq2);  // 拷贝初始化
// 结果: 与pq2相同

输入/输出

• 输入：
  priority_queue通常通过循环逐个元素输入

priority_queue pq;
int n, x;
cin >> n;  // 输入元素个数
for (int i = 0; i < n; i++) {
    cin >> x;     // 读取一个整数
    pq.push(x);   // 将整数插入优先队列
}

• 输出：
  priority_queue只能访问顶部元素，要输出所有元素需要边弹出边输出

// 方法1：输出并清空优先队列（会破坏原队列）
while (!pq.empty()) {
    cout << pq.top() << " ";  // 输出顶部元素
    pq.pop();                 // 移除顶部元素
}
cout << endl;

// 方法2：复制后输出（不破坏原优先队列）
priority_queue pq_copy = pq;  // 复制优先队列
while (!pq_copy.empty()) {
    cout << pq_copy.top() << " ";
    pq_copy.pop();
}
cout << endl;

// 方法3：保持原样输出（需要使用辅助数据结构）
vector temp;
while (!pq.empty()) {
    cout << pq.top() << " ";  // 从大到小输出
    temp.push_back(pq.top());  // 保存元素
    pq.pop();
}
cout << endl;
// 恢复原优先队列
for (int x : temp) {
    pq.push(x);
}

常用成员函数

1. 访问函数（Access）

1. top()
   • 功能：访问顶部（优先级最高）的元素
   • 用法：priority_queue.top()
   • 示例：

priority_queue pq;
pq.push(3);
pq.push(1);
pq.push(5);
cout << pq.top() << endl;  // 输出: 5 (最大元素)

2. 容量函数（Capacity）

1. empty()
   • 功能：检查优先队列是否为空
   • 用法：priority_queue.empty()
   • 示例：

priority_queue pq1;
priority_queue pq2;
pq2.push(1);
cout << pq1.empty() << endl;  // 输出: 1 (true)
cout << pq2.empty() << endl;  // 输出: 0 (false)

2. size()
   • 功能：返回优先队列中元素的个数
   • 用法：priority_queue.size()
   • 示例：

priority_queue pq;
pq.push(1);
pq.push(2);
pq.push(3);
cout << pq.size() << endl;  // 输出: 3

3. 修改函数（Modifiers）

1. push()
   • 功能：插入元素
   • 用法：priority_queue.push(value)
   • 示例：

priority_queue pq;
pq.push(3);  // 插入3
pq.push(1);  // 插入1
pq.push(5);  // 插入5
// 现在顶部是5

2. emplace()
   • 功能：直接构造元素，避免拷贝
   • 用法：priority_queue.emplace(args...)
   • 示例：

priority_queue> pq;
pq.emplace(3, "three");  // 直接构造pair
pq.push(make_pair(1, "one"));  // 先构造再拷贝
// 现在顶部是{3, "three"}

3. pop()
   • 功能：移除顶部元素
   • 用法：priority_queue.pop()
   • 示例：

priority_queue pq;
pq.push(3);
pq.push(1);
pq.push(5);
pq.pop();  // 移除5
cout << pq.top() << endl;  // 输出: 3

4. swap()
   • 功能：交换两个优先队列的内容
   • 用法：priority_queue1.swap(priority_queue2)
   • 示例：

priority_queue pq1, pq2;
pq1.push(1);
pq1.push(2);
pq2.push(3);
pq1.swap(pq2);
// 现在pq1包含: 3
// pq2包含: 2 1 (顶部是2)

注意事项

1. priority_queue不支持迭代器访问，不能使用begin()、end()等函数

2. priority_queue不支持随机访问，不能通过下标访问元素

3. priority_queue是容器适配器，基于vector、deque等容器实现

4. 默认是大顶堆，顶部元素是最大的

5. 内部实现通常是二叉堆，插入删除的时间复杂度为O(log n)

6. 只能访问顶部元素，不能直接访问其他元素

7. 相同优先级的元素顺序不确定

六、set

申明

• set<类型名> 变量名

初始化

1. 默认构造（空集合）

set s0;  // 创建空集合
// 结果: {}

2. 列表初始化

set s1{1, 2, 3};  // 用花括号初始化列表
// 等同于set s1 = {1, 2, 3};
// 结果: 1 2 3 (自动排序)

3. 拷贝初始化

set s2(s1);  // 用s1初始化s2
// 结果: 1 2 3 (与s1相同)

4. 从数组初始化

int arr[] = {3, 1, 4, 1, 5, 9};
set s3(arr, arr + 6);  // 从数组范围初始化
// 结果: 1 3 4 5 9 (自动去重和排序)

5. 从另一个容器的部分初始化

vector vec{3, 1, 4, 1, 5, 9};
set s4(vec.begin(), vec.begin() + 3);  // 用vector前3个元素初始化
// 结果: 1 3 4

6. 自定义比较函数初始化

// 降序集合
set> s5;  // 使用greater作为比较函数
s5.insert({1, 2, 3});
// 结果: 3 2 1

输入/输出

• 输入：
  set通过插入元素输入

set s;
int n, x;
cin >> n;  // 输入元素个数
for (int i = 0; i < n; i++) {
    cin >> x;     // 读取一个整数
    s.insert(x);  // 插入集合，自动去重排序
}

• 输出：

1. 使用范围for循环

for (auto& x : s) {
    cout << x << " ";  // 按顺序输出每个元素
}
cout << endl;

2. 迭代器遍历

for (auto it = s.begin(); it != s.end(); it++) {
    cout << *it << " ";
}
cout << endl;

3. 反向遍历

for (auto it = s.rbegin(); it != s.rend(); it++) {
    cout << *it << " ";  // 逆序输出
}
cout << endl;

常用成员函数

1. 容量函数（Capacity）

1. empty()
   • 功能：检查set是否为空
   • 用法：set.empty()
   • 示例：

set s1{1, 2, 3};
set s2;
cout << s1.empty() << endl;  // 输出: 0 (false)
cout << s2.empty() << endl;  // 输出: 1 (true)

2. size()
   • 功能：返回set中元素个数
   • 用法：set.size()
   • 示例：

set s{1, 2, 3, 4, 5};
cout << s.size() << endl;  // 输出: 5

2. 修改函数（Modifiers）

1. insert()
   • 功能：插入元素
   • 用法：
   • set.insert(value)：插入单个元素
   • set.insert(first, last)：插入范围元素
   • 示例：

set s;
s.insert(3);  // 插入3
s.insert(1);  // 插入1
s.insert(5);  // 插入5
// 结果: 1 3 5

vector vec{2, 4};
s.insert(vec.begin(), vec.end());  // 插入范围
// 结果: 1 2 3 4 5

2. emplace()
   • 功能：直接构造元素，避免拷贝
   • 用法：set.emplace(args...)
   • 示例：

set> s;
s.emplace(1, "one");  // 直接构造pair
// 现在s = {{1, "one"}}

3. erase()
   • 功能：删除元素
   • 用法：
   • set.erase(key)：删除键值为key的元素
   • set.erase(position)：删除指定位置元素
   • set.erase(first, last)：删除范围元素
   • 示例：

set s{1, 2, 3, 4, 5};
s.erase(3);  // 删除元素3
// 结果: 1 2 4 5

auto it = s.find(2);
if (it != s.end()) {
    s.erase(it);  // 删除迭代器指向的元素
}
// 结果: 1 4 5

4. clear()
   • 功能：清空所有元素
   • 用法：set.clear()
   • 示例：

set s{1, 2, 3, 4, 5};
s.clear();
cout << s.size() << endl;  // 输出: 0

3. 查找函数（Lookup）

1. find()
   • 功能：查找元素，返回迭代器
   • 用法：set.find(key)
   • 示例：

set s{1, 2, 3, 4, 5};
auto it = s.find(3);
if (it != s.end()) {
    cout << "找到: " << *it << endl;  // 输出: 找到: 3
} else {
    cout << "未找到" << endl;
}

2. count()
   • 功能：统计元素出现次数（对set总是0或1）
   • 用法：set.count(key)
   • 示例：

set s{1, 2, 3, 4, 5};
cout << s.count(3) << endl;  // 输出: 1
cout << s.count(6) << endl;  // 输出: 0

3. lower_bound()
   • 功能：返回第一个不小于key的元素的迭代器
   • 用法：set.lower_bound(key)
   • 示例：

set s{1, 2, 4, 5};
auto it = s.lower_bound(3);
if (it != s.end()) {
    cout << *it << endl;  // 输出: 4
}

4. upper_bound()
   • 功能：返回第一个大于key的元素的迭代器
   • 用法：set.upper_bound(key)
   • 示例：

set s{1, 2, 4, 5};
auto it = s.upper_bound(2);
if (it != s.end()) {
    cout << *it << endl;  // 输出: 4
}

5. equal_range()
   • 功能：返回一个pair，表示等于key的元素范围
   • 用法：set.equal_range(key)
   • 示例：

set s{1, 2, 3, 4, 5};
auto p = s.equal_range(3);
if (p.first != p.second) {
    cout << "找到: " << *p.first << endl;  // 输出: 找到: 3
}

4. 迭代器函数（Iterators）

1. begin()和 end()
   • 功能：返回指向第一个元素和最后一个元素之后的迭代器
   • 示例：

set s{1, 2, 3};
for (auto it = s.begin(); it != s.end(); it++) {
    cout << *it << " ";  // 输出: 1 2 3
}

2. rbegin()和 rend()
   • 功能：返回反向迭代器
   • 示例：

set s{1, 2, 3};
for (auto it = s.rbegin(); it != s.rend(); it++) {
    cout << *it << " ";  // 输出: 3 2 1
}

比较运算

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

• ==：相等
• !=：不等
• <：小于
• <=：小于等于
• >：大于
• >=：大于等于

注意事项

1. 元素自动排序，默认升序

2. 元素唯一，不允许重复

3. 插入删除时间复杂度：O(log n)

4. 不支持随机访问，不能通过下标访问

5. 基于红黑树实现，保持平衡

七、multiset

申明

• multiset<类型名> 变量名

multiset ms;  // 创建一个int类型的多重集合

初始化

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

multiset ms1{1, 2, 2, 3, 3, 3};  // 列表初始化
// 结果: 1 2 2 3 3 3 (允许重复)

常用成员函数

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

1. count()可以返回大于1的值

multiset ms{1, 2, 2, 3, 3, 3};
cout << ms.count(2) << endl;  // 输出: 2
cout << ms.count(3) << endl;  // 输出: 3

2. erase(key)会删除所有等于key的元素

multiset ms{1, 2, 2, 3, 3, 3};
ms.erase(2);  // 删除所有2
// 结果: 1 3 3 3

3. equal_range()在multiset中更有用

multiset ms{1, 2, 2, 3, 3, 3};
auto p = ms.equal_range(2);
for (auto it = p.first; it != p.second; it++) {
    cout << *it << " ";  // 输出: 2 2
}

注意事项

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

八、unordered_set

申明

• unordered_set<类型名> 变量名

初始化

1. 默认构造

unordered_set us0;  // 创建空无序集合

2. 列表初始化

unordered_set us1{1, 2, 3, 4, 5};
// 结果: 元素无序，但保证唯一

3. 从范围初始化

vector vec{1, 2, 3, 4, 5};
unordered_set us2(vec.begin(), vec.end());

输入/输出

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

unordered_set us{3, 1, 4, 1, 5, 9};
for (auto& x : us) {
    cout << x << " ";  // 输出顺序不确定
}
// 可能的输出: 9 5 1 3 4

常用成员函数

unordered_set的成员函数与set类似，但缺少排序相关函数：

1. 哈希相关函数

unordered_set us{1, 2, 3, 4, 5};
cout << us.bucket_count() << endl;  // 桶的数量
cout << us.load_factor() << endl;   // 负载因子
us.rehash(20);  // 重新哈希

2. 不支持反向迭代器

unordered_set us{1, 2, 3};
// 没有rbegin(), rend()函数

比较运算

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

注意事项

1. 元素无序，不保证任何顺序

2. 元素唯一，不允许重复

3. 平均时间复杂度：O(1)，最坏O(n)

4. 基于哈希表实现

5. 不支持反向迭代器

九、map

申明

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

map mp;           // 创建一个int到string的映射
map mp2;         // 创建一个string到int的映射

初始化

1. 默认构造（空映射）

map mp0;  // 创建空映射
// 结果: {}

2. 列表初始化

map mp1{
    {1, "one"},
    {2, "two"},
    {3, "three"}
};  // 用花括号初始化列表
// 等同于 map mp1 = {{1, "one"}, {2, "two"}, {3, "three"}};
// 结果: 1:"one", 2:"two", 3:"three" (按键排序)

3. 拷贝初始化

map mp2(mp1);  // 用mp1初始化mp2
// 结果: 与mp1相同

4. 从数组初始化

pair arr[] = {{1, "one"}, {2, "two"}, {3, "three"}};
map mp3(arr, arr + 3);  // 从数组范围初始化
// 结果: 1:"one", 2:"two", 3:"three"

5. 从另一个容器的部分初始化

vector> vec{{1, "one"}, {2, "two"}, {3, "three"}};
map mp4(vec.begin(), vec.begin() + 2);  // 用vector前2个元素初始化
// 结果: 1:"one", 2:"two"

6. 自定义比较函数初始化

// 降序映射
map> mp5;  // 使用greater作为比较函数
mp5.insert({{1, "one"}, {2, "two"}, {3, "three"}});
// 结果: 3:"three", 2:"two", 1:"one"

输入/输出

• 输入：
  map通过插入键值对输入

map mp;
int n, value;
string key;
cin >> n;  // 输入键值对个数
for (int i = 0; i < n; i++) {
    cin >> key >> value;  // 读取键和值
    mp[key] = value;     // 插入键值对
}

• 输出：

1. 使用范围for循环

for (auto& [key, value] : mp) {  // C++17结构化绑定
    cout << key << ": " << value << endl;
}
// 或者
for (auto& p : mp) {
    cout << p.first << ": " << p.second << endl;
}

2. 迭代器遍历

for (auto it = mp.begin(); it != mp.end(); it++) {
    cout << it->first << ": " << it->second << endl;
}

3. 反向遍历

for (auto it = mp.rbegin(); it != mp.rend(); it++) {
    cout << it->first << ": " << it->second << endl;  // 逆序输出
}

常用成员函数

1. 容量函数（Capacity）

1. empty()
   • 功能：检查map是否为空
   • 用法：map.empty()
   • 示例：

map mp1{{1, "one"}, {2, "two"}};
map mp2;
cout << mp1.empty() << endl;  // 输出: 0 (false)
cout << mp2.empty() << endl;  // 输出: 1 (true)

2. size()
   • 功能：返回map中键值对个数
   • 用法：map.size()
   • 示例：

map mp{{1, "one"}, {2, "two"}, {3, "three"}};
cout << mp.size() << endl;  // 输出: 3

2. 修改函数（Modifiers）

1. insert()
   • 功能：插入键值对
   • 用法：
   • map.insert(pair)：插入单个键值对
   • map.insert({key, value})：插入单个键值对(C++11)
   • map.insert(first, last)：插入范围键值对
   • 示例：

map mp;
mp.insert(make_pair(1, "one"));  // 方法1
mp.insert({2, "two"});           // 方法2
mp.insert(pair(3, "three"));  // 方法3

vector> vec{{4, "four"}, {5, "five"}};
mp.insert(vec.begin(), vec.end());  // 插入范围
// 结果: 1:"one", 2:"two", 3:"three", 4:"four", 5:"five"

2. emplace()
   • 功能：直接构造键值对，避免拷贝
   • 用法：map.emplace(args...)
   • 示例：

map mp;
mp.emplace(1, "one");  // 直接构造pair
// 现在mp = {1:"one"}

3. erase()
   • 功能：删除元素
   • 用法：
   • map.erase(key)：删除键为key的元素
   • map.erase(position)：删除指定位置元素
   • map.erase(first, last)：删除范围元素
   • 示例：

map mp{{1, "one"}, {2, "two"}, {3, "three"}, {4, "four"}};
mp.erase(2);  // 删除键为2的元素
// 结果: 1:"one", 3:"three", 4:"four"

auto it = mp.find(3);
if (it != mp.end()) {
    mp.erase(it);  // 删除迭代器指向的元素
}
// 结果: 1:"one", 4:"four"

4. clear()
   • 功能：清空所有元素
   • 用法：map.clear()
   • 示例：

map mp{{1, "one"}, {2, "two"}, {3, "three"}};
mp.clear();
cout << mp.size() << endl;  // 输出: 0

5. operator[]
   • 功能：访问或插入元素
   • 用法：map[key]
   • 示例：

map mp;
mp["apple"] = 5;  // 插入或修改
mp["banana"] = 3;
cout << mp["apple"] << endl;  // 输出: 5
cout << mp["orange"] << endl;  // 输出: 0 (自动插入默认值)

6. at()
   • 功能：带边界检查的访问
   • 用法：map.at(key)
   • 示例：

map mp{{"apple", 5}, {"banana", 3}};
cout << mp.at("apple") << endl;  // 输出: 5
// cout << mp.at("orange") << endl;  // 抛出 std::out_of_range 异常

3. 查找函数（Lookup）

1. find()
   • 功能：查找键，返回迭代器
   • 用法：map.find(key)
   • 示例：

map mp{{1, "one"}, {2, "two"}, {3, "three"}};
auto it = mp.find(2);
if (it != mp.end()) {
    cout << "找到: " << it->first << " -> " << it->second << endl;
    // 输出: 找到: 2 -> two
} else {
    cout << "未找到" << endl;
}

2. count()
   • 功能：统计键出现次数（总是0或1，因为键唯一）
   • 用法：map.count(key)
   • 示例：

map mp{{1, "one"}, {2, "two"}, {3, "three"}};
cout << mp.count(2) << endl;  // 输出: 1
cout << mp.count(4) << endl;  // 输出: 0

3. lower_bound()
   • 功能：返回第一个不小于key的元素的迭代器
   • 用法：map.lower_bound(key)
   • 示例：

map mp{{1, "one"}, {3, "three"}, {5, "five"}};
auto it = mp.lower_bound(2);
if (it != mp.end()) {
    cout << it->first << ": " << it->second << endl;  // 输出: 3: three
}

4. upper_bound()
   • 功能：返回第一个大于key的元素的迭代器
   • 用法：map.upper_bound(key)
   • 示例：

map mp{{1, "one"}, {3, "three"}, {5, "five"}};
auto it = mp.upper_bound(2);
if (it != mp.end()) {
    cout << it->first << ": " << it->second << endl;  // 输出: 3: three
}

5. equal_range()
   • 功能：返回一个pair，表示等于key的元素范围
   • 用法：map.equal_range(key)
   • 示例：

map mp{{1, "one"}, {2, "two"}, {3, "three"}};
auto p = mp.equal_range(2);
if (p.first != p.second) {
    cout << "找到: " << p.first->first << " -> " << p.first->second << endl;
    // 输出: 找到: 2 -> two
}

4. 迭代器函数（Iterators）

1. begin()和 end()
   • 功能：返回指向第一个元素和最后一个元素之后的迭代器
   • 示例：

map mp{{1, "one"}, {2, "two"}, {3, "three"}};
for (auto it = mp.begin(); it != mp.end(); it++) {
    cout << it->first << ": " << it->second << " ";  // 输出: 1:one 2:two 3:three
}

2. rbegin()和 rend()
   • 功能：返回反向迭代器
   • 示例：

map mp{{1, "one"}, {2, "two"}, {3, "three"}};
for (auto it = mp.rbegin(); it != mp.rend(); it++) {
    cout << it->first << ": " << it->second << " ";  // 输出: 3:three 2:two 1:one
}

比较运算

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

• ==：相等
• !=：不等
• <：小于
• <=：小于等于
• >：大于
• >=：大于等于
  比较示例：

map mp1{{1, "one"}, {2, "two"}};
map mp2{{1, "one"}, {3, "three"}};
cout << (mp1 < mp2) << endl;  // 输出: 1 (true)，因为2 < 3

注意事项

1. 按键自动排序，默认升序

2. 键唯一，不允许重复键

3. 插入删除时间复杂度：O(log n)

4. 基于红黑树实现，保持平衡

5. operator[]会自动插入不存在的键，而at()会抛出异常

6. **可以使用结构化绑定(C++17)**简化遍历

十、multimap

申明

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

multimap mmp;  // 创建一个int到string的多重映射

初始化

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

multimap mmp1{
    {1, "one"},
    {2, "two"},
    {2, "another two"},  // 允许重复键
    {3, "three"}
};  // 列表初始化
// 结果: 1:"one", 2:"two", 2:"another two", 3:"three" (按键排序)

常用成员函数

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

1. 不支持operator[]和at()

multimap mmp;
// mmp[1] = "one";  // 错误，不支持operator[]
// mmp.at(1);       // 错误，不支持at()

2. insert()总是成功

multimap mmp;
mmp.insert({1, "one"});
mmp.insert({1, "another one"});  // 成功插入重复键

3. count()可以返回大于1的值

multimap mmp{{1, "one"}, {1, "another"}, {2, "two"}};
cout << mmp.count(1) << endl;  // 输出: 2

4. equal_range()在multimap中更有用

multimap mmp{{1, "one"}, {1, "another"}, {2, "two"}};
auto p = mmp.equal_range(1);
for (auto it = p.first; it != p.second; it++) {
    cout << it->first << ": " << it->second << " ";  // 输出: 1:one 1:another
}

注意事项

1. 允许重复键

2. 不支持operator[]和at()

3. 其他特性与map相同

十一、unordered_map

申明

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

初始化

1. 默认构造

unordered_map ump0;  // 创建空无序映射

2. 列表初始化

unordered_map ump1{
    {"apple", 5},
    {"banana", 3},
    {"orange", 2}
};
// 结果: 元素无序，但键唯一

3. 从范围初始化

vector> vec{{"apple", 5}, {"banana", 3}, {"orange", 2}};
unordered_map ump2(vec.begin(), vec.end());

输入/输出

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

unordered_map ump{{"apple", 5}, {"banana", 3}, {"orange", 2}};
for (auto& [key, value] : ump) {
    cout << key << ": " << value << " ";  // 输出顺序不确定
}
// 可能的输出: orange:2 banana:3 apple:5

常用成员函数

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

1. 支持operator[]和at()

unordered_map ump;
ump["apple"] = 5;
cout << ump.at("apple") << endl;  // 输出: 5

2. 哈希相关函数

unordered_map ump{{"apple", 5}, {"banana", 3}, {"orange", 2}};
cout << ump.bucket_count() << endl;  // 桶的数量
cout << ump.load_factor() << endl;   // 负载因子
ump.rehash(20);  // 重新哈希

3. 不支持反向迭代器

unordered_map ump{{"apple", 5}, {"banana", 3}, {"orange", 2}};
// 没有rbegin(), rend()函数

比较运算

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

注意事项

1. 元素无序，不保证任何顺序

2. 键唯一，不允许重复键

3. 平均时间复杂度：O(1)，最坏O(n)

4. 基于哈希表实现

5. 不支持反向迭代器

例题部分

一、【模板】栈

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

#include 
using namespace std;
int main() {
  int T;
  cin >> T;
  while (T--) {
    stack 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 
using namespace std;
int main() {
  queue 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 
using namespace std;
int main() {
  using u64 = unsigned long long;
  multiset 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 
using namespace std;
int main() {
  int n, m, r;
  cin >> n >> m >> r;
  vector> 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> 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 
using namespace std;
int main() {
  int n, m;
  cin >> n >> m;
  vector> ans(n);
  using pli = pair;
  set s;
  // priority_queue, greater> pq;
  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 
using namespace std;
int main() {
  // key -> value
  unordered_map 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 
using namespace std;
int main() {
  int n, c;
  cin >> n >> c;
  unordered_map 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 
using namespace std;
int main() {
  multiset values;
  stack 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 
using namespace std;
int main() {
  int n;
  cin >> n;
  using u64 = unsigned long long;
  priority_queue, greater> 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 
using namespace std;
int main() {
  int n, m;
  cin >> n >> m;
  vector vec(n);
  unordered_set 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 
using namespace std;
int main() {
  int n;
  cin >> n;
  vector 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 
using namespace std;
int main() {
  int n, k;
  cin >> n >> k;
  vector arr(n);
  for (auto &x : arr) scanf("%d", &x);
  nth_element(arr.begin(), arr.begin() + k, arr.end());
  cout << arr[k] << endl;
}

十三、约瑟夫问题

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

#include 
using namespace std;
int main() {
  queue 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 
using namespace std;
int main() {
  int n, m;
  cin >> n >> m;
  vector 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) {
      // found;
      cout << (iter - arr.begin() + 1) << ' ';
    } else {
      cout << -1 << ' ';
    }
  }
  cout << endl;
}

十五、【模板】堆

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

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

十六、寄包柜

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

#include 
using namespace std;
int main() {
  unordered_map, int, decltype([](const pair &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 
using namespace std;
int main() {
  unordered_map> 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 
using namespace std;
int main() {
  int T;
  cin >> T;
  while (T--) {
    set 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 
using namespace std;
int main() {
  int T;
  cin >> T;
  while (T--) {
    int n;
    cin >> n;
    vector pushed(n), poped(n);
    for (auto &x : pushed) cin >> x;
    for (auto &x : poped) cin >> x;
    stack 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 
using namespace std;
int main() {
  using pli = pair;
  using pq = priority_queue, greater>;
  int n, m;
  cin >> n >> m;
  vector> 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;
  }
}