c++如何使用std::partition分割容器_c++ 快速排序底层算法逻辑应用【教程】

c++kquote>std::partition用于原地二路分割，将满足谓词的元素移至前段、不满足的移至后段，不保证各自内部顺序，返回分割点迭代器；适用于vector等支持前向迭代器的容器，但list需用成员函数partition。

std::partition 怎么用：原地分割，不保证顺序

std::partition 的作用是把容器中满足条件的元素“全挪到前面”，不满足的“全挪到后面”，但不保证各自内部顺序。它不排序，也不要求随机访问迭代器以外的能力（比如 std::list 也能用），时间复杂度是 O(n)，空间复杂度 O(1)。

常见错误是把它当 std::sort 或 std::stable_partition 用——前者会错乱预期顺序，后者才保序但更慢。

• 必须传入一对前向迭代器（begin(), end()）和一个一元谓词（返回 bool 的函数或 Lambda）
• 返回值是第一个“不满足条件”元素的迭代器，即分割点，可直接用于后续操作
• 对 std::vector、std::deque、std::Array 都适用；std::list 要用成员函数 list::partition（因需重连指针）

std::vector v = {3, 1, 4, 1, 5, 9, 2, 6}; auto pivot = std::partition(v.begin(), v.end(), [](int x) { return x < 5; }); // v 可能变成 {3, 1, 4, 1, 2, 9, 5, 6} —— 前半都 < 5，后半都 ≥ 5，但各自无序 // pivot 指向 9

为什么快速排序底层不用 std::partition 做主轴划分？

快速排序的核心是“主轴划分（partitioning）”，但标准库的 std::sort 实现（如 GCC libstdc++ 或 LLVM libc++）通常不用 std::partition，而是手写内联划分逻辑。原因很实际：

• std::partition 是通用算法，需通过函数调用反复判断谓词，有间接调用开销；手写划分可内联比较逻辑，且常做分支预测优化
• 快排需要“三路划分”或“双轴划分”时（比如处理大量重复元素），std::partition 只支持二路，无法直接复用
• 某些实现（如 introsort）会在递归深度过深时切到堆排序，此时划分逻辑需与整个状态机耦合，无法靠独立算法解耦

换句话说：std::partition 是好用的工具，但不是快排“底层”的一部分——它是更高层的抽象，而快排实现要的是可控、紧凑、可微调的原始循环。

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

std::partition 和 std::stable_partition 的关键区别

两者语义相同，但 std::stable_partition 保持同侧元素的相对顺序，代价是额外 O(n) 空间（多数实现用临时缓冲区）或 O(n log n) 时间（分治式稳定划分）。

• 若你只关心“奇数在前、偶数在后”，不介意 {1,3,5} 内部顺序 → 用 std::partition
• 若你还要保持输入中奇数出现的先后（如原序列 {2,1,4,3} 分割后希望是 {1,3,2,4}）→ 必须用 std::stable_partition
• 对小容器（size ），某些标准库实现会降级为插入排序式稳定划分；大容器则分配内存，注意可能触发异常（加 noexcept 判断或预分配）

std::vector words = {"cat", "dog", "bird", "ant"}; // 按长度 ≤ 3 分割，保持原序 auto stable_pivot = std::stable_partition(words.begin(), words.end(),     [](const std::string& s) { return s.length() <= 3; }); // 结果大概率是 {"cat", "dog", "ant", "bird"} —— "cat"/"dog"/"ant" 顺序不变

容易被忽略的边界与陷阱

std::partition 看似简单，但在真实项目里容易栽在几个细节上：

• 谓词不能修改元素，否则行为未定义；若需就地转换再判断（如转小写比较），应先预处理或用 std::transform + std::partition 两步走
• 对空容器调用是安全的，返回 begin()，但若误用该返回值做 *it 解引用会崩溃
• 迭代器失效规则：仅对 std::vector 等连续容器，元素移动不导致迭代器失效；但若在 partition 后又调用了 resize() 或 push_back()，之前获得的 pivot 迭代器立即失效
• 自定义类型要注意谓词中的拷贝成本；避免在 lambda 中捕获大对象，或改用引用捕获（[&ctx]）并确保生命周期覆盖整个 partition 调用

真正难的从来不是调用那行代码，而是想清楚“我到底要保序还是不保序”“这个 pivot 迭代器接下来会不会被意外 invalidate”“谓词里有没有隐式构造或锁”。这些比语法重要得多。