c++中如何使用std::partition划分容器_c++快速划分算法用法

std::partition 原地二分划分，满足谓词的元素移至前段、不满足的移至后段，不保证组内顺序；返回分界迭代器，要求双向迭代器、无异常谓词且不可修改容器。

std::partition 会原地重排容器，不保证相对顺序

它把满足谓词的元素移到前面，不满足的移到后面，但同一组内的原始顺序不保留。这和 std::stable_partition 有本质区别——后者保序，但性能略差。

常见误用是以为它像 std::sort 那样“整理”数据，其实它只做二分划分，不排序也不稳定。

• 必须传入双向迭代器（std::vector、std::list 可用；std::forward_list 不行）
• 谓词应为一元函数对象，返回 bool，不能修改元素本身
• 返回值是分界点迭代器，指向第一个“不满足条件”的元素

正确调用 std::partition 的三要素

以 std::vector 划分正负数为例：

std::vector v = {-2, 3, -1, 4, 0, -5};
auto pivot = std::partition(v.begin(), v.end(), [](int x) { return x > 0; });

执行后 v 可能变为 {3, 4, -2, -1, 0, -5}（正数在前，但 3 和 4 的相对位置可能交换），pivot 指向 -2。

立即学习“C++免费学习笔记（深入）”；

Lovart

全球首个AI设计智能体

下载

• 迭代器范围必须合法（不可用 end() 作起始，也不可越界）
• 谓词不能抛异常（否则行为未定义）
• 若容器为空，std::partition 直接返回 begin()，不报错

和 std::partition_copy 的关键区别

std::partition_copy 不修改原容器，而是把满足/不满足的元素分别拷贝到两个目标区间。适合“只读划分 + 分别处理”场景。

例如需要同时统计奇偶数量又保留原数组：

std::vector src = {1, 2, 3, 4, 5};
std::vector odds, evens;
std::partition_copy(src.begin(), src.end(),
                    std::back_inserter(odds), std::back_inserter(evens),
                    [](int x) { return x % 2 != 0; });

• std::partition：就地、快（O(n) 时间，O(1) 额外空间）、不保序
• std::partition_copy：非破坏性、需双倍空间、同样不保序，但避免副作用
• 没有 “partial partition” 或 “nth partition” 这类标准变体，别被名字误导

容易踩的坑：谓词捕获与迭代器失效

若谓词里捕获了容器引用并试图修改它，会导致未定义行为。例如：

std::vector data = {1,2,3};
std::partition(data.begin(), data.end(), [&data](int x) {
    data.push_back(x * 2); // ❌ 危险！可能使迭代器失效
    return x > 1;
});

• 谓词只能读取，不能触发重分配、插入、删除等操作
• 对 std::vector 使用时，确保容量足够，避免内部 realloc 导致迭代器全废
• 多线程下，不能在谓词中访问共享状态而无同步——这不是线程安全操作

实际项目中，最常被忽略的是：划分后没用返回的 pivot 迭代器去切分逻辑，而是重新遍历或硬编码索引，白白浪费了算法提供的分界信息。