稀疏数组不能直接用std::vector因其空间复杂度O(rows×cols)，浪费内存；应只存非零元并支持快速定位与操作，常用三元组表、std::map、CSR三种方案，选择取决于读写比例和访问模式。
稀疏数组为什么不能直接用 std::vector<:vector>></:vector>
因为大部分元素为 0，二维 std::vector 会为每个位置分配内存，空间复杂度是 O(rows × cols)，哪怕只有 3 个非零元也要占几 MB。真实场景（比如大规模矩阵运算、图的邻接矩阵）里，这直接导致内存爆炸或缓存失效。
核心思路是：只存非零元素 + 能快速定位（行、列 → 值）+ 支持常见操作（访问、修改、遍历）。
常用方案有三种：三元组表、std::map 键值对、压缩稀疏行（CSR）。选哪个取决于读写比例和访问模式：
- 频繁随机读 + 极少修改 →
std::map<:pair int>, int></:pair>最直观 - 需要按行遍历（如矩阵乘法）→ CSR 更高效，但实现稍重
- 纯存储 + 索引简单 → 三元组表（
std::vector<:tuple int>></:tuple>）最轻量，但查值要O(n)
用 std::map 实现带行列索引的稀疏数组
这是平衡开发效率与运行效率的首选——插入、查找、删除都是 O(log n)，支持任意行列下标（负数、大整数也 OK），且代码清晰。
立即学习“C++免费学习笔记（深入）”；
关键点不是“怎么存”，而是“怎么封装成像二维数组一样用”：
- 重载
operator()或operator[]，但operator[]对 const 对象不友好，推荐at(row, col)和set(row, col, val) - 默认返回 0 而不是抛异常，符合稀疏语义
- 避免在
at()中做find()+ 条件返回 —— 直接用map.count({r,c}) ? map[{r,c}] : 0
示例：
class SparseArray {
std::map<std::pair<int, int>, int> data;
public:
int at(int r, int c) const {
auto it = data.find({r, c});
return (it != data.end()) ? it->second : 0;
}
void set(int r, int c, int val) {
if (val == 0) data.erase({r, c}); // 写 0 就删掉，保持真正稀疏
else data[{r, c}] = val;
}
};
CSR（Compressed Sparse Row）适合高性能计算场景
当你要做矩阵乘、迭代求解器、或数据量上百万非零元时，std::map 的指针跳转和内存不连续会拖慢速度。CSR 把所有非零值、列号、行偏移全摊平成三个 std::vector，CPU 缓存友好。
结构三要素：
-
values：按行主序存放所有非零值 -
col_indices：对应每个值的列下标 -
row_ptr：长度为rows + 1，row_ptr[i]是第i行第一个非零元在values中的起始索引
访问 (r, c) 需二分查找 col_indices[row_ptr[r] ... row_ptr[r+1])，比 map 慢一点但常数极小；按行遍历就是裸循环，无分支无间接寻址。
注意：row_ptr 必须严格递增，且 row_ptr[rows] == values.size()，否则 at() 会越界或漏查。
容易踩的坑：默认值、内存释放和线程安全
稀疏数组的“空”不是未初始化，而是逻辑上等于 0。别在构造函数里预填 0 值——那就不稀疏了。
std::map 版本中，set(r,c,0) 必须触发 erase，否则内存只增不减；CSR 版本中，清空后三个 vector 要同时 clear，否则大小不一致会导致后续访问崩溃。
两个版本都不自带线程安全：并发 set 同一位置会出错。std::map 可加 mutable std::shared_mutex；CSR 若只读多写少，建议写时复制（copy-on-write）而非锁整个结构。
最后提醒：如果只是临时存几十个非零点，别上 CSR——手写三元组 + 线性查找反而更快，编译器优化得更好。
