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 是好用的工具，但不是快排“底层”的一部分——它是更高层的抽象，而快排实现要的是可控、紧凑、可微调的原始循环。
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”“谓词里有没有隐式构造或锁”。这些比语法重要得多。
关注官方公众号