正确做法是自定义结构体并重载 operator
三元组结构体怎么设计才不踩内存和排序坑
直接用 std::vector<:tuple int double>></:tuple> 存三元组，看似省事，但加法时遍历+查找效率极低，而且 std::tuple 无默认比较，std::sort 会报错。更关键的是：稀疏矩阵加法必须按行列优先顺序合并，否则无法线性扫描合并。
正确做法是自定义结构体并重载 operator：
struct Triple {
int row, col;
double val;
bool operator
<p>注意两点：<br>• 必须先比 <code>row</code> 再比 <code>col</code>，这是 CSR/CSC 的隐含顺序要求；<br>• <code>val</code> 不参与比较，否则相同位置不同值会被误判为不同元素；<br>• 不要用 <code>std::pair<:pair>, double></:pair></code>，嵌套 pair 构造/访问慢且易出错。</p>
<h3>加法运算如何避免重复遍历和临时内存暴涨</h3>
<p>两个已排序三元组向量做加法，本质是归并过程：双指针同步扫描，相同位置累加、不同位置直接搬运。不能先合并再去重，那会浪费 O(nnz₁ + nnz₂) 额外空间存重复项。</p>
<p>实操要点：</p><div class="aritcle_card flexRow artxards">
<div class="artcardd flexRow">
<a class="aritcle_card_img" rel="nofollow" href="/xiazai/gongju/2823" title="C++14"><img
src="https://img.php.cn/upload/manual/001/431/639/6ac8b33c327c4749.png" alt="C++14" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a>
<div class="aritcle_card_info flexColumn">
<a rel="nofollow" href="/xiazai/gongju/2823" title="C++14" class="overflowclass">C++14</a>
<p class="overflowclass">C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。</p>
</div>
<a rel="nofollow" href="/xiazai/gongju/2823" title="C++14" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span>
</a>
</div>
</div>
- 输入的两个
std::vector<triple></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
<h3>为什么不能直接用 map 或 unordered_map 替代三元组 vector</h3>
<p><code>std::map<:pair>, double></:pair></code> 看起来自动去重+排序，但实际性能差很多：</p>
<ul>
<li>每次插入是 O(log n)，总构建复杂度 O(nnz·log nnz)，而 vector+sort 是 O(nnz·log nnz) 但常数小得多</li>
<li>加法时遍历 map 是缓存不友好（节点分散在堆上），vector 是连续内存，CPU 预取高效</li>
<li>
<code>unordered_map</code> 虽然平均 O(1)，但哈希冲突+动态扩容导致实际性能波动大，且不保证顺序，后续转 CSR 仍需额外排序</li>
<li>map 键是 <code>std::pair</code>，构造开销比裸 <code>int</code> 成员大；且无法像 vector 那样用 reserve 预分配</li>
</ul>
<p>结论：三元组 vector + 手动归并，是兼顾可读性、性能和可控性的最简方案。</p>
<h3>加法后要不要压缩？哪些场景必须做</h3>
<p>加法函数本身已跳过 <code>val == 0</code> 的项，所以输出天然“压缩”——没有冗余零元。但要注意边界情况：</p>
<ul>
<li>若输入中存在本就为 0 的 <code>val</code>（比如用户手动构造非法三元组），需在加法前或加法中过滤，否则会影响后续计算</li>
<li>如果后续要转成 CSR 格式，必须确保三元组严格按行主序，且无重复位置——当前归并逻辑已满足</li>
<li>不做额外去重（如用 <code>std::set</code> 二次处理），那会把 O(n+m) 拉回 O((n+m) log(n+m))</li>
</ul>
<p>真正容易被忽略的是：加法结果可能比任一输入还稀疏（大量抵消），但 vector 容量不会自动 shrink，如果反复加法又不复用 vector，得手动调 <code>shrink_to_fit()</code>。</p></triple></triple></triple></triple>C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
