C++如何使用std::partition对容器进行分区？（代码示例）

std::partition将满足谓词的元素移到前面、不满足的留在后面，不保证内部顺序，返回首个不满足元素的迭代器；原地重排，时间复杂度O(n)，空间复杂度O(1)。

std::partition 会将容器中满足条件的元素“挪到前面”，不满足的“留在后面”，但不保证各自内部顺序，也不要求容器有序。它返回一个迭代器，指向第一个不满足条件的元素位置。

基本用法：传入迭代器范围和谓词

需要头文件 #include gorithm>。谓词可以是函数指针、lambda 或函数对象，接收一个参数并返回 bool。

• 原容器会被**原地重排**（in-place），不新建容器
• 分区后，[first, 返回值) 内所有元素满足谓词；[返回值, last) 内都不满足
• 时间复杂度为 O(n)，空间复杂度 O(1)

简单示例：按奇偶性分区

把 vector 中的奇数放在前面，偶数放在后面（顺序不保证）：

#include 
#include 
#include 

int main() {
    std::vector 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 更激进——直接重排）：

// 继续上面的 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）。