std::partition：把容器“掰开”——一次真正有用的元素分组实践

你有没有过这种时刻：手头一堆数据，想快速筛出满足条件的放左边，不满足的甩右边，不关心顺序，只求快、稳、不额外分配内存？
这时候，std::partition 就不是教科书里的冷门算法，而是你调试到凌晨两点时，能少写三行循环、少建一个临时 vector 的真实帮手。

它不排序，不复制，不构造新容器——它就地“掰开”原容器，像用刀切豆腐一样利落。但很多人用错，或者压根没意识到它比 std::stable_partition 或手写循环更贴合某些场景。

它到底干了什么？

std::partition 接收一个迭代器区间和一个一元谓词（比如 [](int x) { return x > 0; }），然后重排元素，使得所有满足谓词的元素移到前面，不满足的移到后面。返回值是第一个“不满足条件”元素的迭代器——这个位置，就是天然的分割点。

关键在“重排”二字：它不保证各自内部顺序，也不要求随机访问，只要求前向迭代器（vector、deque、list 都行，但 list 得用 std::list::splice 配合，稍后细说）。

举个实在例子：

std::vector<int> v = {-3, 5, -1, 8, 0, -7, 4};
auto pivot = std::partition(v.begin(), v.end(), [](int x) { return x > 0; });
// v 可能变成：{5, 8, 4, -3, 0, -7, -1}
// pivot 指向 -3 —— 即 [begin, pivot) 全是正数，[pivot, end) 全是非正数

注意：0 被归到右边，因为 0 > 0 是 false。这很合理——它只认谓词真假，不讲人情。

为什么不用 std::copy_if + 两个 vector？

有人图省事，这么写：

std::vector<int> pos, neg;
std::copy_if(v.begin(), v.end(), std::back_inserter(pos), [](int x){return x>0;});
std::copy_if(v.begin(), v.end(), std::back_inserter(neg), [](int x){return x<=0;});

问题在哪？
三次遍历 + 两倍内存占用 + 缓存不友好。
而 std::partition：单次遍历、原地操作、空间复杂度 O(1)。
尤其当 v 有十万级元素、每个元素是带成员变量的 class 时，拷贝成本肉眼可见——partition 的交换（move 或 swap）远轻于构造+析构。

实战中容易踩的坑

▶️ 谓词必须“稳定”

别在谓词里偷偷改状态。比如：

int threshold = 10;
std::partition(v.begin(), v.end(), [&](int x) {
    if (x > threshold) threshold++; // 错！行为未定义
    return x > threshold;
});

标准明确要求谓词不能修改传入参数以外的状态，否则结果不可预测。真要动态阈值？先算好，再传进去。

▶️ 迭代器失效？不存在的

partition 对 vector/deque 是安全的——它只做元素交换，不增删节点。但对 list，标准库实现通常用 splice，同样不导致迭代器失效（这点比很多人想象得更健壮）。

▶️ 和 std::stable_partition 怎么选？

只差一个字，代价差很多：

• partition：平均 O(N)，最坏 O(N)，不稳定（内部顺序打乱）；
• stable_partition：O(N log N) 时间 + O(N) 额外空间，保持各自内部相对顺序。

你真需要保留正数原来的先后顺序吗？多数业务逻辑不需要。比如“把已支付订单提到前面”，谁在乎它们原本谁先下单？用 partition 更干脆。

一个接地气的应用场景

假设你在写一个日志分析小工具，原始日志按时间追加，每条含 level（DEBUG/INFO/WARN/ERROR）。现在要快速提取所有 ERROR + WARN，同时保留原始 vector 供后续处理（比如导出全量 CSV）。

struct LogEntry {
    std::string level;
    std::string msg;
    std::time_t ts;
};

std::vector<LogEntry> logs = /* ... */;
auto err_warn_end = std::partition(logs.begin(), logs.end(), [](const auto& e) {
    return e.level == "ERROR" || e.level == "WARN";
});

// 现在 [begin, err_warn_end) 就是所有高危日志
for (auto it = logs.begin(); it != err_warn_end; ++it) {
    std::cout << it->level << ": " << it->msg << "\n";
}

没有新建容器，没动原始数据结构，连 reserve() 都省了。如果后续还要处理 INFO/DEBUG，直接用 err_warn_end 到 end() 这段就行——一次划分，多处复用。

再进一步：自定义分割策略

有时“满足条件”不是布尔判断，而是带上下文的。比如按奇偶分组，但希望偶数在前、且偶数内部按升序排？partition 不负责排序，但它可以搭台：

// 先 partition 出偶数块
auto even_end = std::partition(v.begin(), v.end(), [](int x) { return x % 2 == 0; });

// 再只对偶数段 sort —— 范围精准，不波及奇数
std::sort(v.begin(), even_end);

这就是组合的力量：partition 做粗筛，其他算法做精修。它不越界，也不妥协。

最后一句实在话

std::partition 不是炫技工具，它是当你面对“二分归属”问题时，C++ 标准库递来的一把薄刃刀——不花哨，但够快、够省、够可靠。
下次看到“把 A 类和 B 类分开”，别急着开两个容器，先问问自己：我真需要保留各自内部顺序吗？我愿意多花一倍内存和时间吗？
如果答案是否定的，那就伸手拿刀。
毕竟，写代码不是堆砌语法，而是用最贴切的工具，解最具体的题。