std::partition 分区算法

学习用 partition 将容器元素按条件分为两组。 · 难度：入门 · +15XP

std::partition 分区算法

std::partition 对范围 first, last) 内的元素进行重排，使满足谓词的元素位于前半部分，不满足的位于后半部分。返回指向第二个子序列首元素的迭代器。复杂度为 O(n)，属于不稳定分区（相等元素相对顺序可能改变）；若需稳定分区可使用 std::stable_partition。常用于快速筛选、划分数据集。

#include <iostream>
#include <vector>
#include <algorithm>
int main() {
    std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    auto it = std::partition(v.begin(), v.end(),
                             [{ return n % 2 == 1; }); // 奇数在前
    std::cout << "奇数部分: ";
    for (auto i = v.begin(); i != it; ++i) std::cout << *i << ' ';
    std::cout << "
偶数部分: ";
    for (auto i = it; i != v.end(); ++i) std::cout << *i << ' ';
    // 输出可能: 1 9 3 7 5 | 6 4 8 2 （顺序可能不同）
    return 0;
}