直接调用std::set_intersection判断不相交效率低，因会完整构造交集；更优方案是手写双指针遍历（有序容器）或小集合转unordered_set后遍历查找（哈希容器），时间复杂度仍为o(m+n)但常数更小、可提前终止、无需额外内存。
用 std::set_intersection 判断是否不相交效率低吗？
直接调用 std::set_intersection 并检查结果为空，逻辑正确但浪费——它会实际构造交集，哪怕你只关心“有没有交集”。对两个大小为 m 和 n 的有序集合，时间复杂度仍是 O(m + n)，但常数更大，且额外分配内存。
更轻量的做法是手写双指针遍历：利用 std::set（或已排序的 std::vector）的有序性，同步推进两个迭代器，一发现相等元素就立刻返回 false。
- 适用于
std::set、std::map键集，或任何已升序排列的容器 - 提前终止，最坏
O(m + n)，最好O(1)（首元素就相等） - 无需额外空间，也不修改原容器
bool is_disjoint(const std::set<int>& a, const std::set<int>& b) {
auto it_a = a.begin(), it_b = b.begin();
while (it_a != a.end() && it_b != b.end()) {
if (*it_a == *it_b) return false;
if (*it_a
<h3>用 <code>std::find_first_of</code> 一行解决，但要注意什么？</h3>
<p><code>std::find_first_of</code> 看似简洁：<code>std::find_first_of(a.begin(), a.end(), b.begin(), b.end()) == a.end()</code>，但它对无序容器（如 <code>std::unordered_set</code>）才真正有意义；对 <code>std::set</code> 这类有序容器，它退化为 <code>O(m × log n)</code> 或更差（取决于实现），因为内部仍做线性扫描 + 查找。</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>
<ul>
<li>仅推荐用于 <code>std::unordered_set</code> 与 <code>std::vector</code> 等混合场景</li>
<li>若 <code>b</code> 是哈希表，<code>std::find_first_of</code> 内部会遍历 <code>a</code>，对每个元素查 <code>b</code>，平均 <code>O(m)</code>
</li>
<li>但若 <code>a</code> 很大而 <code>b</code> 很小，不如把小集合转成 <code>unordered_set</code> 后遍历大集合</li>
</ul>
<h3>对 <code>std::unordered_set</code>，怎么避免 <code>O(n²)</code> 陷阱？</h3>
<p>别用嵌套循环暴力判断——比如对 <code>a</code> 中每个元素调用 <code>b.count()</code> 是安全的，但若误写成 <code>for (auto& x : a) for (auto& y : b) if (x == y) return false;</code>，就掉进 <code>O(|a| × |b|)</code> 坑里了。</p>
<ul>
<li>正确做法：确保至少一个集合支持 <code>O(1)</code> 查找，优先遍历较小集合</li>
<li>示例：<code>if (a.size() > b.size()) return is_disjoint(b, a); // 交换参数</code>
</li>
<li>
<code>std::unordered_set::count()</code> 平均 <code>O(1)</code>，最坏 <code>O(n)</code>（哈希冲突严重时），但实践中足够快</li>
</ul>
<pre class="brush:php;toolbar:false;">bool is_disjoint(const std::unordered_set<int>& a, const std::unordered_set<int>& b) {
if (a.empty() || b.empty()) return true;
if (a.size() > b.size()) return is_disjoint(b, a);
for (const auto& x : a)
if (b.find(x) != b.end()) return false;
return true;
}</int></int>
为什么不能直接用 std::includes？
std::includes(a, b) 检查的是 “a 是否包含 b 的所有元素”，不是不相交。有人误以为 !std::includes(a,b) && !std::includes(b,a) 能等价于不相交，这是错的：两个集合互不包含，但仍有公共元素（比如 a={1,2}, b={2,3}），此时 includes 全为 false，但它们显然相交。
-
std::includes解决的是子集问题，语义完全不同 - 即使容器有序，也不能复用它来判断 disjoint
- 混淆这两个概念会导致逻辑 bug，且不易通过测试用例暴露（边界 case 少）
includes 和暴力二重循环。C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
