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”“谓词里有没有隐式构造或锁”。这些比语法重要得多。