浅谈STL
Kingdom_Tears
·
·
算法·理论
vector (动态数组)
在 C++ 标准模板库（STL）中，std::vector 是最常用的动态数组容器，它结合了数组的高效访问特性与动态扩容能力，是日常开发中频繁使用的数据结构之一。
一、std::vector的核心特性
迭代器：
提供随机访问迭代器 (Random Access Iterator) ，可像数组一样高效访问任意位置元素。
劣势：中间或头部插入 / 删除元素时，需移动后续元素，时间复杂度为 O(n) ；扩容时可能触发内存重新分配和元素拷贝，存在性能开销。
其中T为元素类型（如 int 、string 等），Allocator 为内存分配器（默认使用 std::allocator）。
二、std::vector的常用操作
1. 初始化与赋值
#include <vector>//头文件
using namespace std;
// 初始化方式
vector<int> v1; // 空vector，无元素
vector<int> v2(5); // 包含5个元素，默认初始化为0（基础类型）
vector<int> v3(3, 10); // 包含3个元素，均为10
vector<int> v4(v3); // 拷贝构造，复制v3的所有元素
vector<int> v5 = {1, 2, 3, 4}; // 初始化列表（C++11及以上）
vector<int> v6(v5.begin(), v5.end()); // 用v5的迭代器范围初始化
2. 元素访问
支持多种高效访问方式，体现随机访问优势：
vector<int> v = {10, 20, 30, 40};
// 1. 下标访问（[]）：不检查越界，速度快
int a = v[1]; // 20
// 2. at()方法：会检查越界，越界时抛出out_of_range异常
int b = v.at(2); // 30
// 3. 访问首尾元素（需确保vector非空）
int first = v.front(); // 10
int last = v.back(); // 40
// 4. 数据指针（data()）：返回指向底层数组的指针，可直接操作内存
int* ptr = v.data();
ptr[0] = 100; // 修改第一个元素为100，v变为{100, 20, 30, 40}
3. 插入与删除
- 尾部操作（高效）：
vector<int> v = {1, 2};
v.push_back(3); // 尾部插入3，v变为{1, 2, 3}
v.pop_back(); // 尾部删除，v变为{1, 2}
- 任意位置操作（中间 / 头部，效率较低）：
vector<int> v = {1, 3, 4};
auto it = v.begin() + 1; // 指向索引1的位置（元素3）
// 在it位置插入元素2，后续元素后移
v.insert(it, 2); // v变为{1, 2, 3, 4}
// 删除it位置的元素（此时it仍指向原位置，内容已变为3）
v.erase(it); // v变为{1, 2, 4}
// 清空所有元素（内存可能保留，size变为0，capacity不变）
v.clear();
##### 4. 容量与大小管理
$vector$ 有两个关键属性：
- $size$：当前元素个数 $v.size()$
- $capacity$：当前已分配内存可容纳的最大元素个数$v.capacity()$，$capacity >= size$
常用操作：
```cpp
vector<int> v;
v.reserve(100); // 预分配至少能容纳100个元素的内存，不改变size（仍为0）
v.resize(10, 0); // 调整size为10，新增元素初始化为0（capacity可能增加）
bool isEmpty = v.empty(); // 判断是否为空（size == 0）
v.shrink_to_fit(); // 释放多余内存，使capacity等于size（C++11及以上）
扩容机制：
当 push_back 等操作导致 size 超过 capacity 时，vector 会自动扩容（通常扩容为当前 capacity 的 1.5 倍或 2 倍，取决于编译器），过程为：
1.分配一块更大的新内存；
2.将原元素拷贝到新内存；
3.释放原内存
扩容时可能导致迭代器、指针、引用失效（指向原内存）
三、std::vector与std::list的对比
| 特性 |
std::vector |
std::list |
| 内存存储 |
连续内存（数组形式） |
非连续（双向链表节点） |
| 随机访问 |
支持 (O (1)) |
不支持 (O (n)) |
| 中间插入 / 删除 |
O(n)（需移动后续元素） |
O(1)（已知位置时） |
| 尾部插入 / 删除 |
O(1)（通常，可能触发扩容） |
O(1) |
| 迭代器稳定性 |
扩容或中间操作可能失效 |
插入 / 删除不影响其他迭代器 |
| 内存开销 |
较低（仅存数据） |
较高（需存储前后指针） |
四、适用场景
- 需要随机访问元素（如通过索引快速读取）。
- 主要在尾部进行插入 / 删除操作。
- 元素个数相对稳定，或扩容频率较低。
需与 C 语言接口交互（通过data()获取原生数组指针）。
例如：存储用户列表、实现动态数组、缓存临时数据等。
## list (双向链表)
$std::list$ 是一种双向链表容器，专为高效的插入和删除操作设计。它与 $std::vector$（动态数组）形成鲜明对比，不支持随机访问，但在元素中间位置的修改操作上具有显著优势。
#### 一、std::list的核心特性
- ##### 数据结构：
基于双向链表实现，每个节点包含数据域、前驱指针（指向前一个节点）和后继指针（指向后一个节点），节点在内存中非连续存储。
迭代器：提供双向迭代器（$bidirectional iterator$），支持向后移动和向前移动操作，但不支持随机访问（与$vector$的随机访问迭代器不同）。
- ##### 性能特点：
优势：在任意位置（头部、尾部、中间）插入（$insert$）或删除（$erase$）元素时，时间复杂度为 $O(1)$（只需修改指针指向，无需移动其他元素）。
劣势：访问指定位置元素时，需从头部或尾部遍历，时间复杂度为 $O(n)$ ；内存开销略高（需存储额外的指针）。
- ##### 模板定义：
```cpp
template <class T, class Allocator = allocator<T>> class list;
```
其中T为元素类型，Allocator为内存分配器（通常使用默认值）
#### 二、std::list的常用操作
##### 1. 初始化与赋值
```cpp
#include <list>//头文件
using namespace std;
// 初始化方式
list<int> l1; // 空链表
list<int> l2(3, 10); // 3个元素，均为10
list<int> l3(l2.begin(), l2.end()); // 用l2的元素初始化
list<int> l4 = {1, 2, 3, 4}; // 初始化列表（C++11及以上）
```
##### 2. 元素访问
- 不支持$[ ]$或$at()$，需通过迭代器或首尾元素接口访问：
```cpp
// 获取首尾元素（需确保链表非空）
int first = l4.front(); // 第一个元素（1）
int last = l4.back(); // 最后一个元素（4）
// 通过迭代器遍历
for (auto it = l4.begin(); it != l4.end(); ++it) {
cout << *it << " "; // 输出：1 2 3 4
}
```
##### 3. 插入与删除
- 插入：
```cpp
list<int> l = {1, 3, 4};
auto it = l.begin();
++it; // 指向元素3的位置
l.insert(it, 2); // 在3之前插入2，链表变为{1, 2, 3, 4}
l.push_front(0); // 头部插入0，变为{0, 1, 2, 3, 4}
l.push_back(5); // 尾部插入5，变为{0, 1, 2, 3, 4, 5}
```
- 删除：
```cpp
l.pop_front(); // 删除头部元素，变为{1, 2, 3, 4, 5}
l.pop_back(); // 删除尾部元素，变为{1, 2, 3, 4}
auto it = l.begin();
++it; ++it; // 指向元素3
l.erase(it); // 删除3，变为{1, 2, 4}
l.clear(); // 清空链表，变为空
```
##### 4. 其他常用操作
- $size()$：返回元素个数（C++11 前需用$distance(begin(), end())$，效率 $O(n)$）。
- $empty()$：判断链表是否为空。
- $sort()$：对链表排序（底层为归并排序，时间复杂度 $O (nlog_n)$，支持自定义比较函数）。
- $reverse()$：反转链表（$O (n)$）。
- $unique()$：删除连续重复元素（需先排序，否则只去重连续项）。
- $splice()$：将另一个链表的元素转移到当前链表（$O (1)$，无需复制元素，仅修改指针），例如：
```cpp
list<int> a = {1, 2};
list<int> b = {3, 4};
a.splice(a.end(), b); // a变为{1,2,3,4}，b变为空
```
#### 三、std::list与std::vector的对比
| 特性 | std::list | std::vector |
|:---:|:---:|:---:|
| 内存存储 | 非连续（双向链表节点） |连续内存（数组形式）|
|随机访问|支持 ($O (1)$)|不支持 ($O (n)$)|
|中间插入 / 删除 |$O(n)$（需移动后续元素）|$O(1)$（已知位置时）|
|尾部插入 / 删除|$O(1)$|$O(1)$（通常，可能触发扩容）|
|迭代器稳定性 |插入 / 删除不影响其他迭代器|扩容或中间操作可能失效|
|内存开销 |较高（需存储前后指针）|较低（仅存数据）|
#### 四、适用场景
$std::list$ 适合以下场景：
- 需要频繁在任意位置（尤其是中间）进行插入和删除操作。
- 不需要随机访问元素，主要通过遍历方式访问。
- 元素个数动态变化大，且修改操作频繁。
例如：实现链表结构、模拟队列或栈（但通常优先用 $std::queue$ / $std::stack$ ）、需要频繁重组的数据集合等。
## deque (双端队列)
在 C++ 标准模板库（STL）中， $std::deque$ $（double-ended queue）$ 是一种支持双端高效插入和删除操作的动态序列容器，结合了 $vector$ 和 $list$ 的部分特性，是处理两端操作频繁场景的理想选择。
#### 一、std::deque 的核心特性
- ##### 数据结构：
由多个连续的内存块（分段数组）组成，通过内部指针数组（控制块）管理这些内存块，逻辑上表现为连续的线性结构。每个内存块的大小固定，新元素插入时可在前端或后端分配新内存块。
- ##### 迭代器：
提供随机访问迭代器 $（Random Access Iterator）$ ，支持像数组一样的高效随机访问，迭代器内部会处理内存块之间的跳转。
- ##### 性能特点：
优势：两端插入 / 删除元素效率极高（时间复杂度 $O(1)$ ），随机访问效率接近 $vector（O(1)）$ 。
劣势：中间插入 / 删除元素需移动后续元素，时间复杂度 $O(n)$ ；内存布局较复杂，迭代器实现成本高，某些场景下缓存利用率略低于 $vector$ 。
- ##### 模板定义：
```cpp
template <class T, class Allocator = allocator<T>> class deque;
```
其中 $T$ 为元素类型（如 $int$ 、 $string$ 等）， $Allocator$ 为内存分配器（默认使用 $std::allocator$ ）。
#### 二、std::deque 的常用操作
##### 1. 初始化与赋值
```cpp
#include <deque> // 头文件
using namespace std;
// 初始化方式
deque<int> d1; // 空deque
deque<int> d2(5); // 包含5个元素，默认初始化为0（基础类型）
deque<int> d3(3, 10); // 包含3个元素，均为10
deque<int> d4(d3); // 拷贝构造，复制d3的所有元素
deque<int> d5 = {1, 2, 3, 4}; // 初始化列表（C++11及以上）
deque<int> d6(d5.begin(), d5.end()); // 用d5的迭代器范围初始化
```
##### 2. 元素访问
支持多种高效访问方式，体现随机访问特性：
```cpp
deque<int> d = {10, 20, 30, 40};
// 1. 下标访问（[]）：不检查越界
int a = d[1]; // 20
// 2. at()方法：检查越界，越界抛出out_of_range异常
int b = d.at(2); // 30
// 3. 访问首尾元素
int first = d.front(); // 10
int last = d.back(); // 40
// 4. 迭代器访问
for (auto it = d.begin(); it != d.end(); ++it) {
cout << *it << " "; // 输出10 20 30 40
}
```
##### 3. 插入与删除
- 双端操作（高效）：
```cpp
deque<int> d = {2, 3};
d.push_front(1); // 前端插入1，d变为{1, 2, 3}
d.push_back(4); // 后端插入4，d变为{1, 2, 3, 4}
d.pop_front(); // 前端删除，d变为{2, 3, 4}
d.pop_back(); // 后端删除，d变为{2, 3}
```
- 任意位置操作：
```cpp
deque<int> d = {1, 3, 4};
auto it = d.begin() + 1; // 指向索引1的位置（元素3）
// 在it位置插入元素2
d.insert(it, 2); // d变为{1, 2, 3, 4}
// 删除it位置的元素（此时it指向元素3）
d.erase(it); // d变为{1, 2, 4}
// 清空所有元素
d.clear(); // d变为空
```
##### 4. 容量与大小管理
```cpp
deque<int> d;
// 判断是否为空
bool is_empty = d.empty(); // true
// 获取元素个数
size_t size = d.size(); // 0
// 调整大小（新增元素用指定值初始化）
d.resize(5, 0); // 大小变为5，元素为{0, 0, 0, 0, 0}
// 交换两个deque的内容
deque<int> d2 = {1, 2};
d.swap(d2); // d变为{1, 2}，d2变为{0, 0, 0, 0, 0}
```
*注：$deque$ 没有 $reserve ($ $)$ 方法，其内存分配策略与 $vector$ 不同，无需提前预留容量。*
#### 三、std::deque 与 std::vector 的对比
| 特性 | std::duque | std::vector |
|:---:|:---:|:---:|
|内存结构 |分段连续内存（多块数组）|单一连续内存块|
|前端操作|前端插入 / 删除 $O(1)$|前端插入 / 删除 $O(n)$|
|后端操作|插入 / 删除 $O(1)$（通常）|插入 $O(1)$（可能扩容），删除 $O(1)$|
|随机访问|$O(1)$（略低于 $vector$ ）|$O(1)$（最优）|
|扩容开销|小（分配新块，无需拷贝全部元素）|可能大（需整体拷贝到新内存）|
|内存利用率|较低（可能有碎片）|较高（连续内存）|
|迭代器稳定性 |中间插入 / 删除可能失效，两端操作通常不影响其他迭代器|扩容或中间操作可能导致所有迭代器失效|
#### 四、适用场景
$std::deque$ 适合以下场景：
- 需要在两端频繁进行插入 / 删除操作的场景，如双端队列、缓冲区等。
- 作为 $std::queue$ 和 $std::stack$ 的默认底层容器（平衡两端操作需求）。
- 元素数量不确定，且可能需要频繁在头部操作，同时需要随机访问的场景。
例如：实现滑动窗口算法、模拟队列与栈的底层容器、处理流式数据的缓冲区等。
## queue(队列)
在 C++ 标准模板库（STL）中，$std::queue$ 是一种遵循先进先出 $（FIFO, First-In-First-Out）$ 原则的容器适配器，它提供了队列的基本操作，适用于需要按顺序处理元素的场景。
#### 一、std::queue 的核心特性
- ##### 数据结构：
基于底层容器（默认是 $std::deque$ ）实现的适配器，封装了底层容器的接口，仅提供队列相关操作，元素遵循先进先出原则。
- ##### 迭代器：
不提供迭代器访问，无法直接访问中间元素，只能访问队首和队尾元素，保证了队列操作的严格性。
- ##### 性能特点：
优势：队首删除和队尾插入操作效率高（时间复杂度通常为 O (1)，取决于底层容器）。
劣势：无法随机访问元素，不能在中间插入或删除元素，功能相对受限。
- ##### 模板定义：
```cpp
template <class T, class Container = deque<T>> class queue;
```
#### 二、std::queue 的常用操作
##### 1. 初始化与赋值
```cpp
#include <queue> // 头文件
#include <deque>
#include <list>
using namespace std;
// 初始化方式
queue<int> q1; // 空队列，底层使用deque
queue<int, deque<int>> q2; // 指定底层容器为deque
queue<int, list<int>> q3; // 指定底层容器为list
// 赋值操作
queue<int> q4 = q1; // 拷贝赋值
queue<int> q5;
q5.swap(q4); // 交换两个队列的内容
```
##### 2. 元素访问
仅支持访问队首和队尾元素：
```cpp
queue<int> q;
q.push(10);
q.push(20);
q.push(30);
// 访问队首元素（不删除）
int front_val = q.front(); // 10
// 访问队尾元素（不删除）
int back_val = q.back(); // 30
```
##### 3. 插入与删除
```cpp
queue<int> q;
// 队尾插入元素
q.push(1); // 队列变为{1}
q.push(2); // 队列变为{1, 2}
// 队首删除元素
q.pop(); // 队列变为{2}
// 注意：pop()不返回删除的元素，需先通过front()获取
if (!q.empty()) {
int val = q.front();
q.pop(); // 先获取再删除
}
```
##### 4. 容量相关操作
```cpp
queue<int> q;
// 判断队列是否为空
bool is_empty = q.empty(); // true
// 获取队列中元素的个数
size_t size = q.size(); // 0
q.push(1);
q.push(2);
size = q.size(); // 2
is_empty = q.empty(); // false
```
#### 三、std::queue 与 std::stack 的对比
| 特性 | std::queue | std::stack |
|:---:|:---:|:---:|
|数据结构|先进先出$（FIFO）$|后进先出$（LIFO）$|
|元素访问|队首$（front ($ $)$ , $O(1)）$、队尾$（back ($ $)$ , $O(1)）$|栈顶$（top ($ $)$ , $O(1)）$|
|插入操作|队尾插入$（push ($ $)$ , $O(1)）$|栈顶插入$（push ($ $)$ , $O(1)）$|
|删除操作|队首删除$（pop ($ $)$ , $O(1)）$|栈顶删除$（pop ($ $)$ , $O(1)）$|
|底层容器默认类型|$std::deque$|$std::deque$|
|适用场景 |广度优先搜索、任务调度等|深度优先搜索、表达式求值等|
#### 四、适用场景
$std::queue$ 适合以下场景：
- 需要按顺序处理元素的场景，如任务调度器中按提交顺序执行任务。
- 广度优先搜索（BFS）算法的实现，按层次遍历节点。
- 缓冲区设计，如打印队列、消息队列等，保证数据按接收顺序处理。
例如：实现打印机任务队列、处理网络请求的顺序队列、模拟银行排队系统等。
## stack (栈)
在 C++ 标准模板库（STL）中，$std::stack$ 是一种后进先出 $（LIFO, Last-In-First-Out）$ 的容器适配器，它基于其他容器实现，提供了栈的基本操作，适用于需要后进先出处理元素的场景。
#### 一、std::stack 的核心特性
- ##### 数据结构：
基于底层容器（默认是 $std::deque$ ）实现的适配器，封装了底层容器的接口，仅提供栈相关操作，元素遵循后进先出原则。
- ##### 迭代器：
不提供迭代器访问，无法直接访问中间元素，只能访问栈顶元素，保证了栈操作的严格性。
- ##### 性能特点：
优势：栈顶插入和删除操作效率高（时间复杂度通常为 $O(1)$ ，取决于底层容器）。
劣势：无法随机访问元素，不能在中间插入或删除元素，功能相对受限。
- ##### 模板定义：
```cpp
template <class T, class Container = deque<T>> class stack;
```
其中 $T$ 为元素类型（如 $int$ 、$string$ 等），$Container$ 为底层容器类型（需支持 $back ($ $)$ 、 $push_back ($ $)$ 、 $pop_back ($ $)$ 、 $empty ($ $)$ 、 $size ($ $)$ 等操作，默认使用 $std::deque$ ，也可使用 $std::vector$ 、 $std::list$ 等）。
#### 二、std::stack 的常用操作
##### 1. 初始化与赋值
```cpp
#include <stack> // 头文件
#include <deque>
#include <vector>
#include <list>
using namespace std;
// 初始化方式
stack<int> s1; // 空栈，底层使用deque
stack<int, deque<int>> s2; // 指定底层容器为deque
stack<int, vector<int>> s3; // 指定底层容器为vector
stack<int, list<int>> s4; // 指定底层容器为list
// 赋值操作
stack<int> s5 = s1; // 拷贝赋值
stack<int> s6;
s6.swap(s5); // 交换两个栈的内容
```
##### 2. 元素访问
仅支持访问栈顶元素：
```cpp
stack<int> s;
s.push(10);
s.push(20);
s.push(30);
// 访问栈顶元素（不删除）
int top_val = s.top(); // 30（最后插入的元素）
```
##### 3. 插入与删除
```cpp
stack<int> s;
// 栈顶插入元素
s.push(1); // 栈变为{1}（栈顶为1）
s.push(2); // 栈变为{1, 2}（栈顶为2）
s.push(3); // 栈变为{1, 2, 3}（栈顶为3）
// 栈顶删除元素
s.pop(); // 栈变为{1, 2}（栈顶为2）
// 注意：pop()不返回删除的元素，需先通过top()获取
if (!s.empty()) {
int val = s.top(); // 获取栈顶元素
s.pop(); // 再删除栈顶元素
}
```
##### 4. 容量相关操作
```cpp
stack<int> s;
// 判断栈是否为空
bool is_empty = s.empty(); // true
// 获取栈中元素的个数
size_t size = s.size(); // 0
s.push(1);
s.push(2);
size = s.size(); // 2
is_empty = s.empty(); // false
```
#### 三、std::stack 与 std::queue 的对比
| 特性 | std::stack | std::queue |
|:---:|:---:|:---:|
|数据结构|后进先出$（LIFO）$|先进先出$（FIFO）$|
|元素访问|栈顶$（top ($ $)$ , $O(1)）$|队首$（front ($ $)$ , $O(1)）$、队尾$（back ($ $)$ , $O(1)）$|
|插入操作|栈顶插入$（push ($ $)$ , $O(1)）$|队尾插入$（push ($ $)$ , $O(1)）$|
|删除操作|栈顶删除$（pop ($ $)$ , $O(1)）$|队首删除$（pop ($ $)$ , $O(1)）$|
|底层容器默认类型|$std::deque$|$std::deque$|
|适用场景 |深度优先搜索、表达式求值等|广度优先搜索、任务调度等|
#### 四、适用场景
$std::stack$ 适合以下场景：
- 需要后进先出处理元素的场景，如函数调用栈的模拟。
- 深度优先搜索 $（DFS）$ 算法的实现，按路径回溯处理节点。
- 表达式求值与转换（如中缀表达式转后缀表达式）、括号匹配验证等。
- 撤销操作 $（Undo）$ 功能的实现，记录操作历史并按逆序撤销。
例如：实现计算器的表达式解析、验证代码中的括号匹配、模拟浏览器的前进后退功能等。
## map (映射)
在 C++ 标准模板库（STL）中， $std::map$ 是一种基于键 - 值 $（key-value）$ 对的有序关联容器，它能够自动按照键的大小进行排序，适用于需要快速查找、插入和删除键值对的场景。
#### 一、std::map 的核心特性
- ##### 数据结构：
通常基于红黑树（一种自平衡二叉搜索树）实现，键值对按照键的比较规则（默认是小于运算符 $<$ ）有序排列，每个键在 $map$ 中是唯一的。
- ##### 迭代器：
提供双向迭代器 $（Bidirectional Iterator）$ ，支持遍历容器中的键值对，迭代顺序与键的排序顺序一致。
- ##### 性能特点：
优势：插入、删除和查找操作的平均时间复杂度为 $O(log_n)$ ，能够保持元素的有序性。
劣势：随机访问效率低（需通过迭代器顺序访问），内存开销较大（需存储树结构相关信息）。
- ##### 模板定义：
```cpp
template <
class Key,
class T,
class Compare = std::less<Key>,
class Allocator = std::allocator<std::pair<const Key, T>>
> class map;
```
其中 $Key$ 为键的类型，$T$ 为值的类型，$Compare$ 为键的比较函数（默认使用 $std::less<Key>$ ）， $Allocator$ 为内存分配器（默认使用 $std::allocator$ ）。
#### 二、std::map 的常用操作
##### 1. 初始化与赋值
```cpp
#include <map> // 头文件
#include <string>
using namespace std;
// 初始化方式
map<int, string> m1; // 空map，键为int类型，值为string类型
map<int, string> m2{{1, "one"}, {2, "two"}, {3, "three"}}; // 初始化列表（C++11及以上）
map<int, string> m3(m2); // 拷贝构造
map<int, string> m4(m2.begin(), m2.end()); // 用迭代器范围初始化
// 赋值操作
map<int, string> m5;
m5 = m2; // 拷贝赋值
m5.swap(m1); // 交换两个map的内容
```
##### 2. 元素访问与查找
```cpp
map<int, string> m{{1, "one"}, {2, "two"}, {3, "three"}};
// 1. 下标访问（[]）：若键不存在则插入默认值
string val1 = m[2]; // "two"
m[4] = "four"; // 插入键值对{4, "four"}
// 2. at()方法：访问指定键的值，键不存在则抛出out_of_range异常
string val2 = m.at(3); // "three"
// 3. 查找操作
auto it = m.find(2); // 查找键为2的元素，返回迭代器
if (it != m.end()) {
// 迭代器指向的是pair<const Key, T>类型
cout << "Key: " << it->first << ", Value: " << it->second << endl; // 输出Key: 2, Value: two
}
// 4. 检查键是否存在
bool exists = m.count(1); // 存在返回1，不存在返回0
```
##### 3. 插入与删除
```cpp
map<int, string> m;
// 插入操作
m.insert({1, "one"}); // 插入键值对{1, "one"}
m.insert(pair<int, string>(2, "two")); // 用pair插入
m.emplace(3, "three"); // 原位构造键值对（更高效）
// 删除操作
m.erase(2); // 按键删除，返回删除的元素个数（0或1）
auto it = m.find(1);
if (it != m.end()) {
m.erase(it); // 按迭代器删除
}
// 清空所有元素
m.clear();
```
##### 4. 容量与大小管理
```cpp
map<int, string> m{{1, "one"}, {2, "two"}};
// 判断是否为空
bool is_empty = m.empty(); // false
// 获取元素个数
size_t size = m.size(); // 2
// 获取最大可能容纳的元素个数（取决于系统和分配器）
size_t max_size = m.max_size();
```
#### 三、std::map 与 std::unordered_map 的对比
| 特性 | std::map | std::unordered_map |
|:---:|:---:|:---:|
|底层结构 |红黑树|哈希表|
|元素顺序|按键有序排列|无序|
|查找效率|$O(log_n)$|平均 $O(1)$ ，最坏 $O(n)$|
|插入 / 删除效率|$O(log_n)$|平均 $O(1)$ ，最坏 $O(n)$|
|键的要求|需支持比较运算符（如 $<$ ）|需支持哈希函数和相等运算符（ $==$ ）|
|内存开销|中等（树结构）|较大（哈希表可能有冗余空间）|
|迭代顺序|有序|无序|
#### 四、适用场景
$std::map$ 适合以下场景：
- 需要按键的顺序遍历元素的场景，如字典排序、范围查询等。
- 插入、删除和查找操作频率均衡，且对元素有序性有要求的场景。
- 键类型支持比较运算符，且对查找效率要求不是极端苛刻的情况。
例如：实现字典、电话簿、学生信息管理（按学号排序）、区间统计等。
## set (集合)
在 C++ 标准模板库（STL）中， $std::set$ 是一种存储唯一元素的有序关联容器，它能够自动按照元素的大小进行排序，适用于需要存储不重复元素且保持有序性的场景。
#### 一、std::set 的核心特性
- ##### 数据结构：
通常基于红黑树（一种自平衡二叉搜索树）实现，元素按照比较规则（默认是小于运算符 $<$ ）有序排列，且每个元素在 set 中是唯一的（不允许重复）。
- ##### 迭代器：
提供双向迭代器 $（Bidirectional Iterator）$ ，支持遍历容器中的元素，迭代顺序与元素的排序顺序一致。
- ##### 性能特点：
优势：插入、删除和查找操作的平均时间复杂度为 $O(log_n)$ ，能够保持元素的有序性和唯一性。
劣势：随机访问效率低（需通过迭代器顺序访问），内存开销较大（需存储树结构相关信息）。
- ##### 模板定义：
```cpp
template <
class T,
class Compare = std::less<T>,
class Allocator = std::allocator<T>
> class set;
```
其中 $T$ 为元素类型， $Compare$ 为元素的比较函数（默认使用 $std::less<T>$ ）， $Allocator$ 为内存分配器（默认使用 $std::allocator$ ）。
#### 二、std::set 的常用操作
##### 1. 初始化与赋值
```cpp
#include <set> // 头文件
using namespace std;
// 初始化方式
set<int> s1; // 空set，存储int类型元素
set<int> s2{1, 2, 3, 4}; // 初始化列表（C++11及以上）
set<int> s3(s2); // 拷贝构造
set<int> s4(s2.begin(), s2.end()); // 用迭代器范围初始化
set<int, greater<int>> s5{1, 2, 3}; // 指定比较函数（降序排列）
// 赋值操作
set<int> s6;
s6 = s2; // 拷贝赋值
s6.swap(s1); // 交换两个set的内容
```
##### 2. 元素访问与查找
```cpp
set<int> s{1, 2, 3, 4, 5};
// 1. 迭代器访问（无下标访问）
for (auto it = s.begin(); it != s.end(); ++it) {
cout << *it << " "; // 输出1 2 3 4 5（升序）
}
// 2. 查找操作
auto it = s.find(3); // 查找元素3，返回迭代器
if (it != s.end()) {
cout << "Found: " << *it << endl; // 输出Found: 3
}
// 3. 检查元素是否存在
bool exists = (s.count(2) == 1); // 存在返回1，不存在返回0
// 4. 范围查找（返回大于等于2且小于4的元素范围）
auto range = s.equal_range(2);
for (auto iter = range.first; iter != range.second; ++iter) {
cout << *iter << " "; // 输出2 3
}
```
##### 3. 插入与删除
```cpp
set<int> s;
// 插入操作
s.insert(3); // 插入元素3
s.insert({1, 2, 4}); // 插入多个元素
s.emplace(5); // 原位构造元素（更高效）
// 插入重复元素（会被忽略）
auto result = s.insert(3); // result.second为false，表示插入失败
// 删除操作
s.erase(2); // 按值删除，返回删除的元素个数（0或1）
auto it = s.find(4);
if (it != s.end()) {
s.erase(it); // 按迭代器删除
}
// 删除范围内的元素（删除大于2的元素）
s.erase(s.find(3), s.end());
// 清空所有元素
s.clear();
```
##### 4. 容量与大小管理
```cpp
set<int> s{1, 2, 3};
// 判断是否为空
bool is_empty = s.empty(); // false
// 获取元素个数
size_t size = s.size(); // 3
// 获取最大可能容纳的元素个数（取决于系统和分配器）
size_t max_size = s.max_size();
```
#### 三、std::set 与 std::unordered_set 的对比
| 特性 | std::set | std::unordered_set |
|:---:|:---:|:---:|
|底层结构 |红黑树|哈希表|
|元素顺序|有序排列（按比较规则）|无序|
|查找效率|$O(log_n)$|平均 $O(1)$ ，最坏 $O(n)$|
|插入 / 删除效率|$O(log_n)$|平均 $O(1)$ ，最坏 $O(n)$|
|键的要求|需支持比较运算符（如 $<$ ）|需支持哈希函数和相等运算符（ $==$ ）|
|内存开销|中等（树结构）|较大（哈希表可能有冗余空间）|
|迭代顺序|有序|无序|
#### 四、适用场景
$std::set$ 适合以下场景：
- 需要存储唯一元素且保持有序性的场景，如排序后的数据集、去重并排序的需求。
- 需要频繁进行查找、插入、删除操作，且对元素顺序有要求的场景。
- 需要进行范围查询（如查找大于 $x$ 且小于 $y$ 的所有元素）的场景。
例如：存储学生的学号（确保唯一且有序）、实现词汇表（去重并按字母顺序排列）、统计不重复的元素并排序等。