std::partition与std::stable_partition的区别
解释std::partition和std::stable_partition的工作原理和复杂度差异。各自适用于什么场景？partition的返回值和典型用法是什么？如何实现一个高效的partition？
回答
苦行僧
std::partition(first, last, pred)将范围划分为满足/不满足谓词的两部分，返回首个不满足元素的迭代器。不稳定：相等元素的相对顺序可能改变。复杂度：O(n)次谓词调用，O(1)额外空间，最多n/2次交换。std::stable_partition保持相对顺序，但需要额外O(n)临时缓冲区（buffer可能需要动态分配），复杂度O(n)，但内存开销大。实现：stable_partition通常通过临时数组或旋转(rotate)实现。应用场景：partition适合快速分组(如快排分区)；stable_partition用于需要保持原始顺序的分组(如按性别排序并保持内部顺序)。C++17新增std::partition_copy将结果输出到两个序列。配合nth_element可实现快速选择。