std::partition 是原地二元划分算法，将满足谓词的元素全移至前段、不满足的移至后段，不保序，返回分界迭代器；时间复杂度 o(n)，空间复杂度 o(1)。
std::partition 是什么，它到底改了什么
它把容器里满足条件的元素“全挪到前面”，不满足的“全挪到后面”，但不保证各自内部顺序。不是排序，也不是复制新容器，是原地重排——std::partition 直接修改你传进去的迭代器范围。
常见错误现象：std::partition 返回一个迭代器，指向第一个“不满足条件”的元素位置，很多人忽略这个返回值，结果后续逻辑用错分界点。
- 使用场景：快速划分“有效/无效”、“就绪/未就绪”、“正数/非正数”这类二元状态，比如预处理数据、实现 quickselect 的分区步骤
- 参数差异：它只接受一个一元谓词（
UnaryPredicate），比如[](int x) { return x > 0; }，不能像std::stable_partition那样保序，也不能像std::partition_copy那样不改动原容器 - 性能影响：平均 O(n)，单次遍历，空间复杂度 O(1)，比先拷贝再筛选快，但会破坏原有顺序
怎么安全拿到前后两段的迭代器边界
别靠猜，std::partition 的返回值就是关键分界点。用它来切分，否则容易越界或漏判。
示例：
立即学习“C++免费学习笔记（深入）”；
std::vector<int> v = {−3, 1, −5, 2, 0, 4};
auto pivot = std::partition(v.begin(), v.end(), [](int x) { return x > 0; });
// pivot 指向第一个 ≤0 的元素，比如可能指向 v[2]（值为−5）
// [v.begin(), pivot) 是所有 >0 的数
// [pivot, v.end()) 是剩下的
- 常见错误：直接用
v.size() / 2或固定下标当分界，实际分区后长度完全取决于谓词结果分布 - 如果需要稳定顺序（比如保持正数之间的原始先后），得换用
std::stable_partition，但代价是 O(n) 空间 - 注意：谓词不能修改元素本身，否则行为未定义；也不要抛异常，标准要求谓词必须是无异常的
和 std::stable_partition、std::partition_copy 有什么实质区别
三者目标相似，但约束和开销不同，选错会影响正确性或性能。
-
std::partition：最快，O(1) 额外空间，但顺序全乱 —— 适合中间计算、不在乎顺序的场景 -
std::stable_partition：保持各自段内原顺序，但需 O(n) 额外内存（或 O(log n) 如果分配失败回退）—— 适合输出要可读、可调试的场合 -
std::partition_copy：不碰原容器，把两组分别拷进两个目标范围 —— 适合只读输入或需要保留原始数据时 - 兼容性：三者都要求前向迭代器，
std::partition在 C++98 就有，后两者是 C++11 加入
谓词写错会导致什么，怎么验证是否真分对了
谓词逻辑反了、捕获变量失效、或者用了有副作用的操作，std::partition 仍会“成功”执行，但结果完全不对——而且编译器几乎不报错。
- 常见错误现象：分区后发现“满足条件”的段里混着 0 或负数，大概率是谓词用了
x >= 0却误以为是“正数”，或忘了 0 的归属 - 调试建议：分区后手动检查分界点两侧各一两个元素，比如打印
*pivot和*(pivot−1)（确保 pivot 不等于 begin） - 避免副作用：谓词里不要调
std::cout、不要改外部变量、不要调用可能抛异常的函数 - 注意 const 正确性：如果容器元素是 const 或来自 const 容器，谓词参数类型得匹配，比如用
const int&而不是int&
最易被忽略的是：分区操作本身不验证谓词是否自洽——比如谓词对同一元素多次调用返回不同结果（比如依赖全局计数器），行为就未定义。写谓词时得把它当成纯函数对待。
