正确做法是自定义结构体并重载 operator<，按 row 优先、col 次之排序，val 不参与比较；加法采用双指针归并，预分配容量、跳过零值，避免 map 或 tuple 带来的性能与顺序问题。
三元组结构体怎么设计才不踩内存和排序坑
直接用 std::vector<std::tuple<int, int, double>> 存三元组，看似省事，但加法时遍历+查找效率极低，而且 std::tuple 无默认比较，std::sort 会报错。更关键的是：稀疏矩阵加法必须按行列优先顺序合并，否则无法线性扫描合并。
正确做法是自定义结构体并重载 operator<：
struct Triple {
int row, col;
double val;
bool operator<(const Triple& other) const {
return row != other.row ? row < other.row : col < other.col;
}
};
注意两点：
• 必须先比 row 再比 col，这是 CSR/CSC 的隐含顺序要求；
• val 不参与比较，否则相同位置不同值会被误判为不同元素；
• 不要用 std::pair<std::pair<int,int>, double>，嵌套 pair 构造/访问慢且易出错。
加法运算如何避免重复遍历和临时内存暴涨
两个已排序三元组向量做加法，本质是归并过程：双指针同步扫描，相同位置累加、不同位置直接搬运。不能先合并再去重，那会浪费 O(nnz₁ + nnz₂) 额外空间存重复项。
立即学习“C++免费学习笔记（深入）”；
实操要点：
- 输入的两个
std::vector<Triple>必须已调用std::sort排序（否则结果错） - 输出 vector 预分配容量：
result.reserve(a.size() + b.size())，避免多次 realloc - 遇到相同
(row, col)时，只 push 一次，val累加；值为 0 时跳过（稀疏矩阵不存零元） - 别用
find_if或嵌套循环查坐标——那是 O(n²)，不是 O(n+m)
核心逻辑片段：
std::vector<Triple> add(const std::vector<Triple>& a, const std::vector<Triple>& b) {
std::vector<Triple> res; res.reserve(a.size() + b.size());
size_t i = 0, j = 0;
while (i < a.size() && j < b.size()) {
if (a[i].row == b[j].row && a[i].col == b[j].col) {
double sum = a[i].val + b[j].val;
if (sum != 0.0) res.emplace_back(a[i].row, a[i].col, sum);
++i; ++j;
} else if (a[i] < b[j]) {
res.push_back(a[i++]);
} else {
res.push_back(b[j++]);
}
}
while (i < a.size()) res.push_back(a[i++]);
while (j < b.size()) res.push_back(b[j++]);
return res;
}
为什么不能直接用 map 或 unordered_map 替代三元组 vector
std::map<std::pair<int,int>, double> 看起来自动去重+排序，但实际性能差很多：
- 每次插入是 O(log n)，总构建复杂度 O(nnz·log nnz)，而 vector+sort 是 O(nnz·log nnz) 但常数小得多
- 加法时遍历 map 是缓存不友好（节点分散在堆上），vector 是连续内存，CPU 预取高效
-
unordered_map虽然平均 O(1)，但哈希冲突+动态扩容导致实际性能波动大，且不保证顺序，后续转 CSR 仍需额外排序 - map 键是
std::pair，构造开销比裸int成员大；且无法像 vector 那样用 reserve 预分配
结论：三元组 vector + 手动归并，是兼顾可读性、性能和可控性的最简方案。
加法后要不要压缩？哪些场景必须做
加法函数本身已跳过 val == 0 的项，所以输出天然“压缩”——没有冗余零元。但要注意边界情况：
- 若输入中存在本就为 0 的
val（比如用户手动构造非法三元组），需在加法前或加法中过滤，否则会影响后续计算 - 如果后续要转成 CSR 格式，必须确保三元组严格按行主序，且无重复位置——当前归并逻辑已满足
- 不做额外去重（如用
std::set二次处理），那会把 O(n+m) 拉回 O((n+m) log(n+m))
真正容易被忽略的是：加法结果可能比任一输入还稀疏（大量抵消），但 vector 容量不会自动 shrink，如果反复加法又不复用 vector，得手动调 shrink_to_fit()。
