### 第一部分：算法竞赛常用容器

#### 1. `vector`（动态数组）

*   **头文件**：`#include <vector>`
*   **特点**：连续内存存储，支持随机访问。适合需要像普通数组一样用下标快速读写，但大小不固定的场景。

*   **常用方法**：
    *   `v[i]`（中括号访问）：获取或修改下标为 `i` 的元素。
        *   **参数**：`i`（无符号整数，表示下标，从 0 开始）
        *   **返回值**：下标为 `i` 的元素的引用（可读、可写）
        *   **时间复杂度**：$O(1)$
    *   `v.front()`：获取数组的第一个元素。
        *   **参数**：无
        *   **返回值**：首元素的引用
        *   **时间复杂度**：$O(1)$
    *   `v.back()`：获取数组的最后一个元素。
        *   **参数**：无
        *   **返回值**：尾元素的引用
        *   **时间复杂度**：$O(1)$
    *   `push_back(val)`：在数组末尾添加一个元素。
        *   **参数**：`val`（要添加的元素）
        *   **返回值**：无（`void`）
        *   **时间复杂度**：均摊 $O(1)$
    *   `pop_back()`：删除数组最后一个元素。
        *   **参数**：无
        *   **返回值**：无（`void`）
        *   **时间复杂度**：$O(1)$
    *   `size()`：返回数组中元素的个数。
        *   **参数**：无
        *   **返回值**：`size_t`（无符号整数）
        *   **时间复杂度**：$O(1)$
    *   `empty()`：判断数组是否为空。
        *   **参数**：无
        *   **返回值**：`bool`
        *   **时间复杂度**：$O(1)$
    *   `clear()`：清空数组中的所有元素。
        *   **参数**：无
        *   **返回值**：无（`void`）
        *   **时间复杂度**：$O(N)$

*   **代码演示**：

```cpp
#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {10, 20, 30};
    
    // 1. 使用下标访问和修改
    cout << "Index 1: " << v[1] << endl;   // 输出 20
    v[1] = 99;                             // 修改
    cout << "New Index 1: " << v[1] << endl; // 输出 99
    
    // 2. 首尾访问
    cout << "First: " << v.front() << endl; // 输出 10
    cout << "Last: " << v.back() << endl;   // 输出 30
    
    // 3. 尾部增删
    v.push_back(40);
    v.pop_back();
    
    return 0;
}
```

---

#### 2. `deque`（双端队列）

*   **头文件**：`#include <deque>`
*   **特点**：分段连续内存存储。支持在头部和尾部进行高效的插入和删除，且支持用下标直接取任意位置的元素。

*   **常用方法**：
    *   `dq[i]`（中括号访问）：获取或修改队列中下标为 `i` 的元素。
        *   **参数**：`i`（无符号整数，表示下标，从 0 开始）
        *   **返回值**：下标为 `i` 的元素的引用（可读、可写）
        *   **时间复杂度**：$O(1)$
    *   `dq.front()`：获取队头的第一个元素。
        *   **参数**：无
        *   **返回值**：队头元素的引用
        *   **时间复杂度**：$O(1)$
    *   `dq.back()`：获取队尾的最后一个元素。
        *   **参数**：无
        *   **返回值**：队尾元素的引用
        *   **时间复杂度**：$O(1)$
    *   `push_back(val)`：在队尾添加一个元素。
        *   **参数**：`val`
        *   **返回值**：无（`void`）
        *   **时间复杂度**：$O(1)$
    *   `pop_back()`：删除队尾最后一个元素。
        *   **参数**：无
        *   **返回值**：无（`void`）
        *   **时间复杂度**：$O(1)$
    *   `push_front(val)`：在队头添加一个元素。
        *   **参数**：`val`
        *   **返回值**：无（`void`）
        *   **时间复杂度**：$O(1)$
    *   `pop_front()`：删除队头第一个元素。
        *   **参数**：无
        *   **返回值**：无（`void`）
        *   **时间复杂度**：$O(1)$
    *   `size()`：返回队列中元素的个数。
        *   **参数**：无
        *   **返回值**：`size_t`
        *   **时间复杂度**：$O(1)$
    *   `empty()`：判断队列是否为空。
        *   **参数**：无
        *   **返回值**：`bool`
        *   **时间复杂度**：$O(1)$
    *   `clear()`：清空队列。
        *   **参数**：无
        *   **返回值**：无（`void`）
        *   **时间复杂度**：$O(N)$

*   **代码演示**：

```cpp
#include <iostream>
#include <deque>
using namespace std;

int main() {
    deque<int> dq;
    dq.push_back(20);  // {20}
    dq.push_front(10); // {10, 20}
    dq.push_back(30);  // {10, 20, 30}
    
    // 1. 使用下标访问和修改
    cout << "Index 1: " << dq[1] << endl;   // 输出 20
    dq[1] = 50;
    cout << "New Index 1: " << dq[1] << endl; // 输出 50
    
    // 2. 首尾访问
    cout << "Front: " << dq.front() << endl; // 输出 10
    cout << "Back: " << dq.back() << endl;   // 输出 30
    
    return 0;
}
```

---

#### 3. `stack`（栈）

*   **头文件**：`#include <stack>`
*   **特点**：后进先出。不支持随机访问（不能写 `s[i]`），只能访问栈顶。

*   **常用方法**：
    *   `s.top()`：获取并访问栈顶元素。
        *   **参数**：无
        *   **返回值**：栈顶元素的引用（可读、可写）
        *   **时间复杂度**：$O(1)$
        *   **注意**：调用前必须用 `empty()` 确认非空，否则会报错。
    *   `push(val)`：将元素压入栈顶。
        *   **参数**：`val`
        *   **返回值**：无
        *   **时间复杂度**：$O(1)$
    *   `pop()`：弹出栈顶元素。
        *   **参数**：无
        *   **返回值**：无（不返回元素值）
        *   **时间复杂度**：$O(1)$
    *   `size()`：返回栈中元素个数。
        *   **参数**：无
        *   **返回值**：`size_t`
        *   **时间复杂度**：$O(1)$
    *   `empty()`：判断栈是否为空。
        *   **参数**：无
        *   **返回值**：`bool`
        *   **时间复杂度**：$O(1)$

*   **代码演示**：

```cpp
#include <iostream>
#include <stack>
using namespace std;

int main() {
    stack<int> s;
    s.push(10);
    s.push(20);
    
    if (!s.empty()) {
        cout << "Stack Top: " << s.top() << endl; // 输出 20
        s.top() = 100;                            // 修改栈顶
        cout << "New Stack Top: " << s.top() << endl; // 输出 100
    }
    
    s.pop();
    return 0;
}
```

---

#### 4. `queue`（队列）

*   **头文件**：`#include <queue>`
*   **特点**：先进先出。不支持随机访问，只能访问队头和队尾。

*   **常用方法**：
    *   `q.front()`：获取队头元素。
        *   **参数**：无
        *   **返回值**：队头元素的引用（可读、可写）
        *   **时间复杂度**：$O(1)$
    *   `q.back()`：获取队尾元素。
        *   **参数**：无
        *   **返回值**：队尾元素的引用（可读、可写）
        *   **时间复杂度**：$O(1)$
    *   `push(val)`：将元素加入队尾。
        *   **参数**：`val`
        *   **返回值**：无
        *   **时间复杂度**：$O(1)$
    *   `pop()`：弹出队头第一个元素。
        *   **参数**：无
        *   **返回值**：无
        *   **时间复杂度**：$O(1)$
    *   `size()`：返回队列元素个数。
        *   **参数**：无
        *   **返回值**：`size_t`
        *   **时间复杂度**：$O(1)$
    *   `empty()`：判断队列是否为空。
        *   **参数**：无
        *   **返回值**：`bool`
        *   **时间复杂度**：$O(1)$

*   **代码演示**：

```cpp
#include <iostream>
#include <queue>
using namespace std;

int main() {
    queue<int> q;
    q.push(10);
    q.push(20);
    
    if (!q.empty()) {
        cout << "Front: " << q.front() << ", Back: " << q.back() << endl; // 输出 10, 20
        q.front() = 99; // 修改队头元素
        cout << "New Front: " << q.front() << endl;                       // 输出 99
    }
    return 0;
}
```

---

#### 5. `priority_queue`（优先队列 / 堆）

*   **头文件**：`#include <queue>`
*   **特点**：自动排序。不支持随机访问，只能访问堆顶（最大值或最小值）。

*   **常用方法**：
    *   `pq.top()`：获取堆顶元素（默认是最大值）。
        *   **参数**：无
        *   **返回值**：堆顶元素的只读常引用（不能修改，修改会破坏堆结构）
        *   **时间复杂度**：$O(1)$
    *   `push(val)`：将元素放入堆中并重新调堆。
        *   **参数**：`val`
        *   **返回值**：无
        *   **时间复杂度**：$O(\log N)$
    *   `pop()`：弹出堆顶元素。
        *   **参数**：无
        *   **返回值**：无
        *   **时间复杂度**：$O(\log N)$
    *   `size()`：返回堆中元素个数。
        *   **参数**：无
        *   **返回值**：`size_t`
        *   **时间复杂度**：$O(1)$
    *   `empty()`：判断堆是否为空。
        *   **参数**：无
        *   **返回值**：`bool`
        *   **时间复杂度**：$O(1)$

*   **代码演示**：

```cpp
#include <iostream>
#include <queue>
using namespace std;

int main() {
    priority_queue<int> pq; // 默认大根堆
    pq.push(10);
    pq.push(30);
    pq.push(20);
    
    if (!pq.empty()) {
        cout << "Heap Top (Max): " << pq.top() << endl; // 输出 30
    }
    return 0;
}
```

---

#### 6. `set` 与 `multiset`（有序集合）

*   **头文件**：`#include <set>`
*   **特点**：自动升序排序。不支持随机访问（没有 `s[i]`），元素是只读的。

*   **常用方法**：
    *   `*s.begin()` / `*s.rbegin()`（元素访问方法）：
        *   **作用**：获取集合中的最小值（首元素）或最大值（尾元素）。
        *   **时间复杂度**：$O(1)$
    *   `insert(val)`：插入元素。
        *   **参数**：`val`
        *   **返回值**：迭代器
        *   **时间复杂度**：$O(\log N)$
    *   `erase(x)`：删除元素。
        *   **参数**：可以是值 `val`，也可以是迭代器 `pos`。
        *   **注意**：在 `multiset` 中，如果传入具体值 `val` 会把所有重复的 `val` 全部删掉；如果只想删一个，请传入对应的迭代器，如 `ms.erase(ms.find(val))`。
    *   `find(val)`：查找元素。
        *   **参数**：`val`
        *   **返回值**：指向该元素的迭代器（找不到则返回 `end()`）
        *   **时间复杂度**：$O(\log N)$
    *   `count(val)`：统计元素出现次数。
        *   **参数**：`val`
        *   **返回值**：出现次数（在 `set` 中只能是 0 或 1）
        *   **时间复杂度**：$O(\log N)$
    *   `lower_bound(val)`：查找第一个 $\ge val$ 的元素位置。
        *   **参数**：`val`
        *   **返回值**：迭代器
        *   **时间复杂度**：$O(\log N)$
    *   `upper_bound(val)`：查找第一个 $> val$ 的元素位置。
        *   **参数**：`val`
        *   **返回值**：迭代器
        *   **时间复杂度**：$O(\log N)$
    *   `size()` / `empty()` / `clear()`：大小、判空与清空。

*   **代码演示**：

```cpp
#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s = {30, 10, 20}; // 排成: {10, 20, 30}
    
    // 1. 获取最值
    cout << "Min: " << *s.begin() << endl;  // 输出 10
    cout << "Max: " << *s.rbegin() << endl; // 输出 30
    
    // 2. 查找特定值
    auto it = s.find(20);
    if (it != s.end()) {
        cout << "Found: " << *it << endl; // 输出 20
    }
    return 0;
}
```

---

#### 7. `map` 与 `multimap`（有序映射）

*   **头文件**：`#include <map>`
*   **特点**：自动按键（Key）排序。支持通过键直接访问和读写值。

*   **常用方法**：
    *   `mp[key]`（中括号访问，**仅限 `map`**）：获取或修改键 `key` 对应的值。
        *   **参数**：键 `key`
        *   **返回值**：值（Value）的引用（可读、可写）
        *   **时间复杂度**：$O(\log N)$
        *   **注意**：如果键不存在，访问它会自动插入这个键，并将值初始化为默认值。
    *   `find(key)`：查找键是否存在。
        *   **参数**：`key`
        *   **返回值**：指向 `pair` 的迭代器（找不到返回 `end()`）
        *   **时间复杂度**：$O(\log N)$
    *   `erase(key)`：删除对应的键值对。
        *   **参数**：`key`
        *   **时间复杂度**：$O(\log N)$
    *   `size()` / `empty()` / `clear()`：大小、判空与清空。

*   **代码演示**：

```cpp
#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, int> mp;
    mp["apple"] = 5; // 插入键值对
    
    // 1. 使用中括号读写值
    cout << "Apple count: " << mp["apple"] << endl; // 读值，输出 5
    mp["apple"] = 10;                               // 修改值
    
    // 2. 查找是否存在
    if (mp.find("banana") == mp.end()) {
        cout << "Banana not found!" << endl;
    }
    return 0;
}
```

---

#### 8. `unordered_set` 与 `unordered_map`（无序哈希容器）

*   **头文件**：`#include <unordered_set>` 与 `#include <unordered_map>`
*   **特点**：不排序，内部元素是乱序的。查找、插入和删除的平均复杂度是 $O(1)$。
*   **元素访问方式**：
    *   `unordered_set`：无随机访问，通过 `find()` 查找后用迭代器取值（只读）。
    *   `unordered_map`：支持 `ump[key]` 读写对应值，操作方法与 `map` 相同。

---

### 第二部分：容器的迭代器（Iterators）

迭代器是指向容器内部元素的“指针”。

#### 1. 获取迭代器的方法
*   `c.begin()`：指向首个元素。
*   `c.end()`：指向末尾元素之后（虚空位置）。
*   `c.rbegin()`：指向最后一个元素（用于反向遍历）。
*   `c.rend()`：指向首个元素之前（用于反向遍历）。

#### 2. 迭代器遍历与读写示例

##### ① 遍历 `vector`（读与写）

```cpp
#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {10, 20, 30};
    
    // 1. 遍历并修改值
    for (auto it = v.begin(); it != v.end(); ++it) {
        *it += 5; // *it 表示取值
    }
    
    // 2. 反向输出：35 25 15
    for (auto it = v.rbegin(); it != v.rend(); ++it) {
        cout << *it << " ";
    }
    return 0;
}
```

##### ② 遍历 `map`（获取键和值）

```cpp
#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, int> mp = {{"apple", 5}, {"banana", 3}};
    
    for (auto it = mp.begin(); it != mp.end(); ++it) {
        // it->first 代表键 (Key)，it->second 代表值 (Value)
        cout << it->first << " has " << it->second << endl;
    }
    return 0;
}
```

---

### 第三部分：算法竞赛常用库函数

调用这些算法前，请确保传入的区间是**左闭右开区间 `[begin, end)`**。

#### 1. `sort`（快速排序）
*   **头文件**：`#include <algorithm>`
*   **参数**：`sort(first_it, last_it, comp = less())`
*   **返回值**：无（`void`）
*   **时间复杂度**：$O(N \log N)$

```cpp
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {3, 1, 5, 2, 4};
    sort(v.begin(), v.end()); // 排序后：{1, 2, 3, 4, 5}
    return 0;
}
```

---

#### 2. `reverse`（区间反转）
*   **头文件**：`#include <algorithm>`
*   **参数**：`reverse(first_it, last_it)`
*   **返回值**：无（`void`）
*   **时间复杂度**：$O(N)$

```cpp
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int main() {
    string s = "abcdef";
    reverse(s.begin(), s.end()); // 全局反转为: "fedcba"
    
    reverse(s.begin() + 1, s.begin() + 4); // 局部反转部分区间
    return 0;
}
```

---

#### 3. `unique`（去重）
*   **头文件**：`#include <algorithm>`
*   **参数**：`unique(first_it, last_it)`
*   **返回值**：指向去重后**不重复序列末尾之后**的迭代器。
*   **注意**：**使用前必须先排序**。

```cpp
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {2, 1, 2, 3, 1};
    sort(v.begin(), v.end()); // 先排序：{1, 1, 2, 2, 3, 3}
    
    // 配合 erase 真正删去尾部重复项
    v.erase(unique(v.begin(), v.end()), v.end()); // 去重后：{1, 2, 3}
    return 0;
}
```

---

#### 4. `lower_bound` 与 `upper_bound`（二分查找）
*   **头文件**：`#include <algorithm>`
*   **前提条件**：操作区间必须是**已经升序排序**的。
*   **参数**：`lower_bound(first_it, last_it, val)`
*   **返回值**：一个迭代器。
    *   `lower_bound`：指向第一个 **$\ge val$** 的元素。
    *   `upper_bound`：指向第一个 **$> val$** 的元素。
*   **时间复杂度**：$O(\log N)$

```cpp
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {10, 20, 30, 30, 40};
    
    auto it1 = lower_bound(v.begin(), v.end(), 30); // 第一个 >= 30 
    auto it2 = upper_bound(v.begin(), v.end(), 30); // 第一个 > 30
    
    cout << "Index: " << (it1 - v.begin()) << endl; // 输出 2
    return 0;
}
```

---

#### 5. `binary_search`（二分判断存在性）
*   **头文件**：`#include <algorithm>`
*   **参数**：`binary_search(first_it, last_it, val)`
*   **返回值**：`bool`（存在返回 `true`，不存在返回 `false`）

```cpp
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {10, 20, 30, 40};
    bool exist = binary_search(v.begin(), v.end(), 30); // 返回 true
    return 0;
}
```

---

#### 6. `next_permutation`（下一个全排列）
*   **头文件**：`#include <algorithm>`
*   **参数**：`next_permutation(first_it, last_it)`
*   **返回值**：`bool`（存在下一个排序返回 `true`，否则返回 `false`）

```cpp
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {1, 2, 3};
    sort(v.begin(), v.end());
    
    do {
        for (int x : v) cout << x << " ";
        cout << endl;
    } while (next_permutation(v.begin(), v.end()));
    return 0;
}
```

---

#### 7. `max_element` 与 `min_element`（查找极值位置）
*   **头文件**：`#include <algorithm>`
*   **参数**：`max_element(first_it, last_it)`
*   **返回值**：指向区间极值元素的迭代器。
*   **时间复杂度**：$O(N)$

```cpp
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {3, 9, 1, 5};
    auto max_it = max_element(v.begin(), v.end());
    cout << "Max: " << *max_it << " at index " << (max_it - v.begin()) << endl; // 9, index 1
    return 0;
}
```

---

#### 8. `accumulate`（区间求和）
*   **头文件**：`#include <numeric>`
*   **参数**：`accumulate(first_it, last_it, init_val)`
*   **返回值**：求和结果，类型与初始值 `init_val` 一致。
*   **防爆 int 技巧**：大数求和时，第三个参数写 `0LL`，即可自动使用 `long long` 累加。
*   **时间复杂度**：$O(N)$

```cpp
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {1, 2, 3, 4, 5};
    long long sum = accumulate(v.begin(), v.end(), 0LL); // 结果为 15
    return 0;
}
```

第一部分：算法竞赛常用容器

1. `vector`（动态数组）

头文件：#include <vector>
特点：连续内存存储，支持随机访问。适合需要像普通数组一样用下标快速读写，但大小不固定的场景。
常用方法：
- v[i]（中括号访问）：获取或修改下标为 i 的元素。
  - 参数：i（无符号整数，表示下标，从 0 开始）
  - 返回值：下标为 i 的元素的引用（可读、可写）
  - 时间复杂度：$O(1)$
- v.front()：获取数组的第一个元素。
  - 参数：无
  - 返回值：首元素的引用
  - 时间复杂度：$O(1)$
- v.back()：获取数组的最后一个元素。
  - 参数：无
  - 返回值：尾元素的引用
  - 时间复杂度：$O(1)$
- push_back(val)：在数组末尾添加一个元素。
  - 参数：val（要添加的元素）
  - 返回值：无（void）
  - 时间复杂度：均摊 $O(1)$
- pop_back()：删除数组最后一个元素。
  - 参数：无
  - 返回值：无（void）
  - 时间复杂度：$O(1)$
- size()：返回数组中元素的个数。
  - 参数：无
  - 返回值：size_t（无符号整数）
  - 时间复杂度：$O(1)$
- empty()：判断数组是否为空。
  - 参数：无
  - 返回值：bool
  - 时间复杂度：$O(1)$
- clear()：清空数组中的所有元素。
  - 参数：无
  - 返回值：无（void）
  - 时间复杂度：$O(N)$
代码演示：

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {10, 20, 30};

    // 1. 使用下标访问和修改
    cout << "Index 1: " << v[1] << endl;   // 输出 20
    v[1] = 99;                             // 修改
    cout << "New Index 1: " << v[1] << endl; // 输出 99

    // 2. 首尾访问
    cout << "First: " << v.front() << endl; // 输出 10
    cout << "Last: " << v.back() << endl;   // 输出 30

    // 3. 尾部增删
    v.push_back(40);
    v.pop_back();

    return 0;
}

2. `deque`（双端队列）

头文件：#include <deque>
特点：分段连续内存存储。支持在头部和尾部进行高效的插入和删除，且支持用下标直接取任意位置的元素。
常用方法：
- dq[i]（中括号访问）：获取或修改队列中下标为 i 的元素。
  - 参数：i（无符号整数，表示下标，从 0 开始）
  - 返回值：下标为 i 的元素的引用（可读、可写）
  - 时间复杂度：$O(1)$
- dq.front()：获取队头的第一个元素。
  - 参数：无
  - 返回值：队头元素的引用
  - 时间复杂度：$O(1)$
- dq.back()：获取队尾的最后一个元素。
  - 参数：无
  - 返回值：队尾元素的引用
  - 时间复杂度：$O(1)$
- push_back(val)：在队尾添加一个元素。
  - 参数：val
  - 返回值：无（void）
  - 时间复杂度：$O(1)$
- pop_back()：删除队尾最后一个元素。
  - 参数：无
  - 返回值：无（void）
  - 时间复杂度：$O(1)$
- push_front(val)：在队头添加一个元素。
  - 参数：val
  - 返回值：无（void）
  - 时间复杂度：$O(1)$
- pop_front()：删除队头第一个元素。
  - 参数：无
  - 返回值：无（void）
  - 时间复杂度：$O(1)$
- size()：返回队列中元素的个数。
  - 参数：无
  - 返回值：size_t
  - 时间复杂度：$O(1)$
- empty()：判断队列是否为空。
  - 参数：无
  - 返回值：bool
  - 时间复杂度：$O(1)$
- clear()：清空队列。
  - 参数：无
  - 返回值：无（void）
  - 时间复杂度：$O(N)$
代码演示：

#include <iostream>
#include <deque>
using namespace std;

int main() {
    deque<int> dq;
    dq.push_back(20);  // {20}
    dq.push_front(10); // {10, 20}
    dq.push_back(30);  // {10, 20, 30}

    // 1. 使用下标访问和修改
    cout << "Index 1: " << dq[1] << endl;   // 输出 20
    dq[1] = 50;
    cout << "New Index 1: " << dq[1] << endl; // 输出 50

    // 2. 首尾访问
    cout << "Front: " << dq.front() << endl; // 输出 10
    cout << "Back: " << dq.back() << endl;   // 输出 30

    return 0;
}

3. `stack`（栈）

头文件：#include <stack>
特点：后进先出。不支持随机访问（不能写 s[i]），只能访问栈顶。
常用方法：
- s.top()：获取并访问栈顶元素。
  - 参数：无
  - 返回值：栈顶元素的引用（可读、可写）
  - 时间复杂度：$O(1)$
  - 注意：调用前必须用 empty() 确认非空，否则会报错。
- push(val)：将元素压入栈顶。
  - 参数：val
  - 返回值：无
  - 时间复杂度：$O(1)$
- pop()：弹出栈顶元素。
  - 参数：无
  - 返回值：无（不返回元素值）
  - 时间复杂度：$O(1)$
- size()：返回栈中元素个数。
  - 参数：无
  - 返回值：size_t
  - 时间复杂度：$O(1)$
- empty()：判断栈是否为空。
  - 参数：无
  - 返回值：bool
  - 时间复杂度：$O(1)$
代码演示：

#include <iostream>
#include <stack>
using namespace std;

int main() {
    stack<int> s;
    s.push(10);
    s.push(20);

    if (!s.empty()) {
        cout << "Stack Top: " << s.top() << endl; // 输出 20
        s.top() = 100;                            // 修改栈顶
        cout << "New Stack Top: " << s.top() << endl; // 输出 100
    }

    s.pop();
    return 0;
}

4. `queue`（队列）

头文件：#include <queue>
特点：先进先出。不支持随机访问，只能访问队头和队尾。
常用方法：
- q.front()：获取队头元素。
  - 参数：无
  - 返回值：队头元素的引用（可读、可写）
  - 时间复杂度：$O(1)$
- q.back()：获取队尾元素。
  - 参数：无
  - 返回值：队尾元素的引用（可读、可写）
  - 时间复杂度：$O(1)$
- push(val)：将元素加入队尾。
  - 参数：val
  - 返回值：无
  - 时间复杂度：$O(1)$
- pop()：弹出队头第一个元素。
  - 参数：无
  - 返回值：无
  - 时间复杂度：$O(1)$
- size()：返回队列元素个数。
  - 参数：无
  - 返回值：size_t
  - 时间复杂度：$O(1)$
- empty()：判断队列是否为空。
  - 参数：无
  - 返回值：bool
  - 时间复杂度：$O(1)$
代码演示：

#include <iostream>
#include <queue>
using namespace std;

int main() {
    queue<int> q;
    q.push(10);
    q.push(20);

    if (!q.empty()) {
        cout << "Front: " << q.front() << ", Back: " << q.back() << endl; // 输出 10, 20
        q.front() = 99; // 修改队头元素
        cout << "New Front: " << q.front() << endl;                       // 输出 99
    }
    return 0;
}

5. `priority_queue`（优先队列 / 堆）

头文件：#include <queue>
特点：自动排序。不支持随机访问，只能访问堆顶（最大值或最小值）。
常用方法：
- pq.top()：获取堆顶元素（默认是最大值）。
  - 参数：无
  - 返回值：堆顶元素的只读常引用（不能修改，修改会破坏堆结构）
  - 时间复杂度：$O(1)$
- push(val)：将元素放入堆中并重新调堆。
  - 参数：val
  - 返回值：无
  - 时间复杂度：$O(\log N)$
- pop()：弹出堆顶元素。
  - 参数：无
  - 返回值：无
  - 时间复杂度：$O(\log N)$
- size()：返回堆中元素个数。
  - 参数：无
  - 返回值：size_t
  - 时间复杂度：$O(1)$
- empty()：判断堆是否为空。
  - 参数：无
  - 返回值：bool
  - 时间复杂度：$O(1)$
代码演示：

#include <iostream>
#include <queue>
using namespace std;

int main() {
    priority_queue<int> pq; // 默认大根堆
    pq.push(10);
    pq.push(30);
    pq.push(20);

    if (!pq.empty()) {
        cout << "Heap Top (Max): " << pq.top() << endl; // 输出 30
    }
    return 0;
}

6. `set` 与 `multiset`（有序集合）

头文件：#include <set>
特点：自动升序排序。不支持随机访问（没有 s[i]），元素是只读的。
常用方法：
- *s.begin() / *s.rbegin()（元素访问方法）：
  - 作用：获取集合中的最小值（首元素）或最大值（尾元素）。
  - 时间复杂度：$O(1)$
- insert(val)：插入元素。
  - 参数：val
  - 返回值：迭代器
  - 时间复杂度：$O(\log N)$
- erase(x)：删除元素。
  - 参数：可以是值 val，也可以是迭代器 pos。
  - 注意：在 multiset 中，如果传入具体值 val 会把所有重复的 val 全部删掉；如果只想删一个，请传入对应的迭代器，如 ms.erase(ms.find(val))。
- find(val)：查找元素。
  - 参数：val
  - 返回值：指向该元素的迭代器（找不到则返回 end()）
  - 时间复杂度：$O(\log N)$
- count(val)：统计元素出现次数。
  - 参数：val
  - 返回值：出现次数（在 set 中只能是 0 或 1）
  - 时间复杂度：$O(\log N)$
- lower_bound(val)：查找第一个 $\ge val$ 的元素位置。
  - 参数：val
  - 返回值：迭代器
  - 时间复杂度：$O(\log N)$
- upper_bound(val)：查找第一个 $> val$ 的元素位置。
  - 参数：val
  - 返回值：迭代器
  - 时间复杂度：$O(\log N)$
- size() / empty() / clear()：大小、判空与清空。
代码演示：

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s = {30, 10, 20}; // 排成: {10, 20, 30}

    // 1. 获取最值
    cout << "Min: " << *s.begin() << endl;  // 输出 10
    cout << "Max: " << *s.rbegin() << endl; // 输出 30

    // 2. 查找特定值
    auto it = s.find(20);
    if (it != s.end()) {
        cout << "Found: " << *it << endl; // 输出 20
    }
    return 0;
}

7. `map` 与 `multimap`（有序映射）

头文件：#include <map>
特点：自动按键（Key）排序。支持通过键直接访问和读写值。
常用方法：
- mp[key]（中括号访问，仅限 map）：获取或修改键 key 对应的值。
  - 参数：键 key
  - 返回值：值（Value）的引用（可读、可写）
  - 时间复杂度：$O(\log N)$
  - 注意：如果键不存在，访问它会自动插入这个键，并将值初始化为默认值。
- find(key)：查找键是否存在。
  - 参数：key
  - 返回值：指向 pair 的迭代器（找不到返回 end()）
  - 时间复杂度：$O(\log N)$
- erase(key)：删除对应的键值对。
  - 参数：key
  - 时间复杂度：$O(\log N)$
- size() / empty() / clear()：大小、判空与清空。
代码演示：

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, int> mp;
    mp["apple"] = 5; // 插入键值对

    // 1. 使用中括号读写值
    cout << "Apple count: " << mp["apple"] << endl; // 读值，输出 5
    mp["apple"] = 10;                               // 修改值

    // 2. 查找是否存在
    if (mp.find("banana") == mp.end()) {
        cout << "Banana not found!" << endl;
    }
    return 0;
}

8. `unordered_set` 与 `unordered_map`（无序哈希容器）

头文件：#include <unordered_set> 与 #include <unordered_map>
特点：不排序，内部元素是乱序的。查找、插入和删除的平均复杂度是 $O(1)$。
元素访问方式：
- unordered_set：无随机访问，通过 find() 查找后用迭代器取值（只读）。
- unordered_map：支持 ump[key] 读写对应值，操作方法与 map 相同。

第二部分：容器的迭代器（Iterators）

迭代器是指向容器内部元素的“指针”。

1. 获取迭代器的方法

c.begin()：指向首个元素。
c.end()：指向末尾元素之后（虚空位置）。
c.rbegin()：指向最后一个元素（用于反向遍历）。
c.rend()：指向首个元素之前（用于反向遍历）。

2. 迭代器遍历与读写示例

① 遍历 `vector`（读与写）

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {10, 20, 30};

    // 1. 遍历并修改值
    for (auto it = v.begin(); it != v.end(); ++it) {
        *it += 5; // *it 表示取值
    }

    // 2. 反向输出：35 25 15
    for (auto it = v.rbegin(); it != v.rend(); ++it) {
        cout << *it << " ";
    }
    return 0;
}

② 遍历 `map`（获取键和值）

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, int> mp = {{"apple", 5}, {"banana", 3}};

    for (auto it = mp.begin(); it != mp.end(); ++it) {
        // it->first 代表键 (Key)，it->second 代表值 (Value)
        cout << it->first << " has " << it->second << endl;
    }
    return 0;
}

第三部分：算法竞赛常用库函数

调用这些算法前，请确保传入的区间是左闭右开区间 [begin, end)。

1. `sort`（快速排序）

头文件：#include <algorithm>
参数：sort(first_it, last_it, comp = less())
返回值：无（void）
时间复杂度：$O(N \log N)$

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {3, 1, 5, 2, 4};
    sort(v.begin(), v.end()); // 排序后：{1, 2, 3, 4, 5}
    return 0;
}

2. `reverse`（区间反转）

头文件：#include <algorithm>
参数：reverse(first_it, last_it)
返回值：无（void）
时间复杂度：$O(N)$

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int main() {
    string s = "abcdef";
    reverse(s.begin(), s.end()); // 全局反转为: "fedcba"

    reverse(s.begin() + 1, s.begin() + 4); // 局部反转部分区间
    return 0;
}

3. `unique`（去重）

头文件：#include <algorithm>
参数：unique(first_it, last_it)
返回值：指向去重后不重复序列末尾之后的迭代器。
注意：使用前必须先排序。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {2, 1, 2, 3, 1};
    sort(v.begin(), v.end()); // 先排序：{1, 1, 2, 2, 3, 3}

    // 配合 erase 真正删去尾部重复项
    v.erase(unique(v.begin(), v.end()), v.end()); // 去重后：{1, 2, 3}
    return 0;
}

4. `lower_bound` 与 `upper_bound`（二分查找）

头文件：#include <algorithm>
前提条件：操作区间必须是已经升序排序的。
参数：lower_bound(first_it, last_it, val)
返回值：一个迭代器。
- lower_bound：指向第一个 $\ge val$ 的元素。
- upper_bound：指向第一个 $> val$ 的元素。
时间复杂度：$O(\log N)$

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {10, 20, 30, 30, 40};

    auto it1 = lower_bound(v.begin(), v.end(), 30); // 第一个 >= 30 
    auto it2 = upper_bound(v.begin(), v.end(), 30); // 第一个 > 30

    cout << "Index: " << (it1 - v.begin()) << endl; // 输出 2
    return 0;
}

5. `binary_search`（二分判断存在性）

头文件：#include <algorithm>
参数：binary_search(first_it, last_it, val)
返回值：bool（存在返回 true，不存在返回 false）

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {10, 20, 30, 40};
    bool exist = binary_search(v.begin(), v.end(), 30); // 返回 true
    return 0;
}

6. `next_permutation`（下一个全排列）

头文件：#include <algorithm>
参数：next_permutation(first_it, last_it)
返回值：bool（存在下一个排序返回 true，否则返回 false）

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {1, 2, 3};
    sort(v.begin(), v.end());

    do {
        for (int x : v) cout << x << " ";
        cout << endl;
    } while (next_permutation(v.begin(), v.end()));
    return 0;
}

7. `max_element` 与 `min_element`（查找极值位置）

头文件：#include <algorithm>
参数：max_element(first_it, last_it)
返回值：指向区间极值元素的迭代器。
时间复杂度：$O(N)$

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {3, 9, 1, 5};
    auto max_it = max_element(v.begin(), v.end());
    cout << "Max: " << *max_it << " at index " << (max_it - v.begin()) << endl; // 9, index 1
    return 0;
}

8. `accumulate`（区间求和）

头文件：#include <numeric>
参数：accumulate(first_it, last_it, init_val)
返回值：求和结果，类型与初始值 init_val 一致。
防爆 int 技巧：大数求和时，第三个参数写 0LL，即可自动使用 long long 累加。
时间复杂度：$O(N)$

#include <iostream>
#include <numeric>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {1, 2, 3, 4, 5};
    long long sum = accumulate(v.begin(), v.end(), 0LL); // 结果为 15
    return 0;
}

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com

STL容器，迭代器，常用函数 分享

第一部分：算法竞赛常用容器

1. vector（动态数组）

2. deque（双端队列）

3. stack（栈）

4. queue（队列）

5. priority_queue（优先队列 / 堆）

6. set 与 multiset（有序集合）

7. map 与 multimap（有序映射）

8. unordered_set 与 unordered_map（无序哈希容器）

第二部分：容器的迭代器（Iterators）

1. 获取迭代器的方法

2. 迭代器遍历与读写示例

① 遍历 vector（读与写）

② 遍历 map（获取键和值）

第三部分：算法竞赛常用库函数

1. sort（快速排序）

2. reverse（区间反转）

3. unique（去重）

4. lower_bound 与 upper_bound（二分查找）

5. binary_search（二分判断存在性）

6. next_permutation（下一个全排列）

7. max_element 与 min_element（查找极值位置）

8. accumulate（区间求和）

STL容器，迭代器，常用函数

1. `vector`（动态数组）

2. `deque`（双端队列）

3. `stack`（栈）

4. `queue`（队列）

5. `priority_queue`（优先队列 / 堆）

6. `set` 与 `multiset`（有序集合）

7. `map` 与 `multimap`（有序映射）

8. `unordered_set` 与 `unordered_map`（无序哈希容器）

① 遍历 `vector`（读与写）

② 遍历 `map`（获取键和值）

1. `sort`（快速排序）

2. `reverse`（区间反转）

3. `unique`（去重）

4. `lower_bound` 与 `upper_bound`（二分查找）

5. `binary_search`（二分判断存在性）

6. `next_permutation`（下一个全排列）

7. `max_element` 与 `min_element`（查找极值位置）

8. `accumulate`（区间求和）