std::partition 是标准库算法，用于原地二分重排容器元素：满足谓词的移至前段，不满足的移至后段，不保证组内顺序，时间复杂度 O(n)，空间复杂度 O(1)，返回指向第一不满足元素的迭代器。
std::partition 是什么，它能做什么
它把容器中满足条件的元素“全挪到前面”，不满足的“全挪到后面”，但不保证各自内部顺序。不是排序，也不创建新容器，是原地重排，时间复杂度 O(n)，空间复杂度 O(1)。
关键点：它只做一次逻辑分组，返回一个迭代器，指向“满足条件部分”的末尾（即第一个不满足条件的元素位置）。
怎么写 predicate 才不会出错
predicate 必须是可调用对象，接受一个 const T&（或 T），返回 bool。常见错误是捕获局部变量时生命周期不对，或用了带副作用的 lambda 导致行为不可预测。
- 避免在 lambda 中修改外部变量（比如
[&count] { ++count; return x > 0; }），std::partition不保证调用次数和顺序 - 不要返回未定义值：比如对
int*解引用空指针再判断，或者除零 - 如果要用成员变量，确保对象生命周期长于 partition 调用；推荐用值捕获或传入稳定参数
std::vector<int> v = {1, -2, 3, -4, 5};
auto it = std::partition(v.begin(), v.end(), [](int x) { return x > 0; });
// v 变成 {1, 3, 5, -2, -4}（顺序可能不同），it 指向 -2
std::partition 和 std::stable_partition 有什么实际区别
std::partition 不保序，快；std::stable_partition 保持各自组内原有相对顺序，但多耗内存（最坏 O(n) 额外空间）且稍慢。
立即学习“C++免费学习笔记（深入）”；
- 需要保留正数原来的先后顺序？用
std::stable_partition - 只是快速分个类（比如把非空指针提前，方便后续批量处理），用
std::partition就够了 - 对
std::list，std::partition不能直接用（没有随机访问迭代器），但std::list::partition成员函数可用，且是稳定的
常见误用：以为它能按多个条件分三组或更多
它只能分两组：满足 predicate 的 + 不满足的。想实现“负数 / 零 / 正数”三分组，不能靠一次 std::partition 解决。
- 错误做法：
std::partition(..., [](int x){ return x != 0; })只能把零单独分出来，剩下正负混在一起 - 正确思路：先用
std::partition分出零，再对非零部分再 partition 一次；或改用std::sort配合自定义比较，或手写循环 - 注意：多次 partition 会改变迭代器有效性——每次都要用新的 begin/end 范围，别拿上一轮的
it直接当新范围起点用错位置
std::vector<int> v = {-1, 0, 2, 0, -3, 4};
auto zero_end = std::partition(v.begin(), v.end(), [](int x) { return x != 0; });
// 现在 [begin, zero_end) 是非零，[zero_end, end) 是零
auto pos_end = std::partition(v.begin(), zero_end, [](int x) { return x > 0; });
// [begin, pos_end) 是正数，[pos_end, zero_end) 是负数，[zero_end, end) 是零
真正要注意的是：predicate 的语义必须明确、无歧义，且在整个 partition 过程中保持纯函数特性。一旦 predicate 在不同调用中返回不一致结果（比如依赖全局时钟或 rand()），行为就未定义——这比编译报错更难排查。
