17370845950

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 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) 额外空间）且稍慢。

• 需要保留正数原来的先后顺序？用 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 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()），行为就未定义——这比编译报错更难排查。