C++ STL

STL（Standard Template Library，标准模板库）是 C++ 标准库的核心组成部分，提供了通用的数据结构和算法。

# 数据结构分类总表
| 分类维度 | 结构名称 | 子类型 / 常见实现 | 元素间关系 | 典型应用场景 |
|:---:|:---:|:---|:---|:---|
| **逻辑结构** | **线性结构** | 线性表（顺序表/链表） | 一对一 | 通用数据存储 |
| | | 栈（Stack） | 一对一（受限） | 函数调用、撤销操作、括号匹配 |
| | | 队列（Queue） | 一对一（受限） | 任务调度、消息队列、BFS |
| | | 串（String） | 一对一 | 文本处理、模式匹配 |
| | **树形结构** | 二叉树、BST、AVL、红黑树 | 一对多 | 文件系统、数据库索引、表达式解析 |
| | | 堆（Heap） | 一对多（受限） | 优先队列、堆排序、Top-K |
| | | 并查集（Union-Find） | 一对多（集合） | 连通性问题、最小生成树 |
| | **图形结构** | 有向图、无向图、带权图 | 多对多 | 社交网络、路径规划（GPS）、网络拓扑 |
| | **集合结构** | 哈希表（Hash Table） | 无明确关系 | 缓存、O(1)快速查找、去重 |
| **物理结构** | **顺序存储** | 数组（Array） | 物理地址连续 | 固定大小、随机访问频繁 |
| | **链式存储** | 单/双链表、循环链表 | 地址不连续，通过指针链接 | 频繁插入/删除、大小动态变化 |
| | **索引存储** | 索引表、散列表 | 建立索引目录 | 数据库索引（B+树） |
| | **散列存储** | 哈希表（Hash） | 通过哈希函数计算地址 | 快速存取、字典实现 |
| **抽象数据类型** | **线性容器** | vector、deque、list | 按位置组织 | C++ STL 序列容器 |
| | **关联容器** | set、map（红黑树实现） | 按键值组织（有序） | 自动排序、范围查询 |
| | **无序容器** | unordered_set/map（哈希实现） | 按哈希组织（无序） | 常数时间查找 |
| | **适配器** | stack、queue、priority_queue | 封装底层容器接口 | 特定行为约束 |

```
问题是否可分解为子问题？
├─ 否 → 枚举 / 递推 / 贪心（简单逻辑）
└─ 是
   ├─ 子问题是否独立？
   │  ├─ 是 → 分治法
   │  └─ 否 → 子问题重叠 → 动态规划
   └─ 是否需要遍历所有可能解？
      ├─ 是 → 回溯 / 分支限界
      └─ 否 → 贪心（如果满足贪心选择性）
```

| 算法领域 | 对应思想 | 覆盖比例 | 说明 |
|:---|:---|:---:|:---|
| 排序 / 查找 | 分治、枚举 | 100% | 快速排序、归并排序、二分查找等完全覆盖 |
| 图论基础 | 贪心、动态规划、回溯 | 100% | 最短路径、最小生成树、拓扑排序全覆盖 |
| 字符串匹配 | 动态规划、递推 | 100% | KMP、Boyer-Moore 本质是动态规划思想 |
| 组合优化 | 回溯、分支限界、近似算法 | 100% | 八皇后、TSP、背包问题全覆盖 |
| 数值计算 | 递推、分治 | 95% | 快速幂、大整数乘法覆盖；少数数论技巧独立存在 |
| 计算几何 | 分治、枚举（扫描线、旋转卡壳） | 90% | 思想本质属于分治/枚举，但实现技巧独立 |
| 网络流 | BFS/DFS + 贪心（增广路） | 85% | Dinic、ISAP 是混合实现，未单列为独立思想 |
| 机器学习/神经网络 | — | 0% | 属于不同范式（统计学/最优化），不在本分类内 |
| 量子/遗传/模拟退火 | — | 0% | 属于元启发式/软计算，与确定性算法思想并列 |

# 六大组件
| 特性 | vector | deque | list | set/map | unordered_set/map |
|------|--------|-------|------|---------|-------------------|
| 随机访问 | O(1) | O(1) | 不支持 | 不支持 | 不支持 |
| 中间插入/删除 | O(n) | O(n) | O(1) | O(log n) | O(1)平均 |
| 查找 | O(n) | O(n) | O(n) | O(log n) | O(1)平均 |
| 是否有序 | 插入顺序 | 插入顺序 | 插入顺序 | 自动排序 | 无序 |
| 底层结构 | 动态数组 | 分段数组 | 双向链表 | 红黑树 | 哈希表 |

容器、迭代器、算法、函数对象、适配器、分配器

# 基础语法
## 容器
```
#include <iostream>
#include <vector>

int main() {
    std::vector<int> v(5, 10);     // 5个元素，都是10
    std::vector<int> w = {1, 2, 3};

w.push_back(4);                // w 变为 {1,2,3,4}
    w.pop_back();                  // w 变回 {1,2,3}

// 使用 size() 和 empty()
    std::cout << "size w: " << w.size() << std::endl;
    std::cout << "empty w: " << w.empty() << std::endl;

// 打印 v 的内容
    std::cout << "v content: ";
    for (int x : v) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

return 0;
}
```