三元组稀疏矩阵加法的核心逻辑是双指针归并合并两个按行主序排序且无重复位置的三元组列表，时间复杂度O(nnz_A + nnz_B)，需手动处理同位置元素相加及零值过滤。
三元组稀疏矩阵加法的核心逻辑是什么
本质是合并两个已按行主序（row 优先，col 次之）排序的三元组列表。不能暴力嵌套遍历，必须用双指针一次扫描完成——类似归并排序的合并过程，时间复杂度 O(nnz_A + nnz_B)。
关键约束：输入三元组数组必须已排序，且无重复位置（(i,j) 相同的元素需预先合并）。否则结果不可靠，后续所有优化都白搭。
常见错误现象：segmentation fault（越界访问）、结果中漏项、同一位置出现两次非零元、输出顺序错乱——基本都是没保证输入有序或指针越界导致的。
如何安全实现双指针合并（C++示例）
假设三元组结构体为 struct Triple { int row, col; double val; };，输入为 vector<triple> A</triple> 和 B，输出存入 vector<triple>& C</triple>：
立即学习“C++免费学习笔记（深入）”；
int i = 0, j = 0;
while (i < A.size() && j < B.size()) {
if (A[i].row < B[j].row || (A[i].row == B[j].row && A[i].col < B[j].col)) {
C.push_back(A[i++]);
} else if (A[i].row > B[j].row || (A[i].row == B[j].row && A[i].col > B[j].col)) {
C.push_back(B[j++]);
} else { // same (row, col)
double sum = A[i].val + B[j].val;
if (abs(sum) > 1e-12) C.push_back({A[i].row, A[i].col, sum});
i++; j++;
}
}
// 剩余部分
while (i < A.size()) C.push_back(A[i++]);
while (j < B.size()) C.push_back(B[j++]);
注意点：
- 比较逻辑必须严格按
(row, col)字典序，不能只比row - 浮点相加后需判断是否为有效非零值（
abs(sum) > eps），避免引入冗余零元 -
C需预先reserve()容量（如A.size() + B.size()），避免频繁 realloc
为什么不能直接用 std::merge？
可以，但必须自定义比较和合并逻辑，std::merge 默认只做“归并”，不处理相同位置的数值相加。若强行用，得配套写一个带状态的仿函数或 lambda，反而增加出错概率。
更现实的问题是：标准库不提供“合并+约简”一体化操作。你仍需在 merge 后遍历结果，对相邻相同 (row,col) 的项做合并——这反而多了一次遍历，失去 O(n) 优势。
所以推荐手写双指针：控制力强、边界清晰、易调试。尤其当你要扩展支持不同数据类型（如 complex<double></double>）或自定义精度阈值时，手写更灵活。
实际使用中容易被忽略的细节
稀疏矩阵加法不是纯数学运算——它依赖底层存储约定。三元组本身不记录维度，rows 和 cols 必须由调用方传入或从上下文获取，否则无法构造完整矩阵视图。
另一个坑：输入三元组若含非法索引（如 row >= rows 或 col >= cols），加法过程不会报错，但后续转 CSR 或乘法会崩溃。建议在加法前加轻量级校验（仅 debug 模式启用）。
最后，如果加法只是中间步骤（比如 A+B 再乘 C），别急着把结果转成稠密矩阵——保持三元组或立即转 CSR，才能延续稀疏性优势。
