std::partition将满足谓词的元素移到前面、不满足的留在后面，不保证内部顺序，返回首个不满足元素的迭代器；原地重排，时间复杂度O(n)，空间复杂度O(1)。
std::partition 会将容器中满足条件的元素“挪到前面”，不满足的“留在后面”，但不保证各自内部顺序，也不要求容器有序。它返回一个迭代器，指向第一个不满足条件的元素位置。
基本用法：传入迭代器范围和谓词
需要头文件 #include <algorithm>。谓词可以是函数指针、lambda 或函数对象，接收一个参数并返回 bool。
- 原容器会被**原地重排**（in-place），不新建容器
- 分区后，[first, 返回值) 内所有元素满足谓词；[返回值, last) 内都不满足
- 时间复杂度为 O(n)，空间复杂度 O(1)
简单示例：按奇偶性分区
把 vector 中的奇数放在前面，偶数放在后面（顺序不保证）：
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8};
auto pivot = std::partition(v.begin(), v.end(), [](int x) {
return x % 2 != 0; // 奇数为 true
});
// 输出：奇数段 + 偶数段
for (int x : v) std::cout << x << " "; // 可能输出：1 3 5 7 2 4 6 8
std::cout << "\n";
std::cout << "pivot points to: " << *pivot << "\n"; // 输出 2（首个偶数）
}
配合 erase 删除不满足条件的元素
若想“移除”所有偶数，可结合 partition + erase 模拟 remove_if 的效果（但 partition 更激进——直接重排）：
立即学习“C++免费学习笔记（深入）”；
// 继续上面的 v
auto new_end = std::partition(v.begin(), v.end(), [](int x) { return x % 2 != 0; });
v.erase(new_end, v.end()); // 删除所有偶数（现在都在末尾）
// v 变为 {1, 3, 5, 7}（顺序仍不保证，但全是奇数）
注意：与 std::stable_partition 的区别
如果需要保持各组内原有相对顺序，必须用 std::stable_partition：
-
std::partition：快，O(1) 额外空间，但不稳定 -
std::stable_partition：稳定（满足/不满足各自的顺序不变），但可能用 O(n) 额外空间，稍慢
例如对 {2,1,4,3,6,5} 按奇偶分区：partition 可能得 {1,3,5,2,4,6}；stable_partition 一定得 {1,3,5,2,4,6}（奇数保持 1→3→5，偶数保持 2→4→6）。
