c++中如何使用std::partition将数组按奇偶分组_c++分区算法【实例】

std::partition可原地奇偶分区且效率高，但不保持内部顺序；推荐用n & 1判断奇偶以避免负数取模问题；返回分界迭代器必须保存以便后续使用。

std::partition 会原地重排，不保证奇偶内部顺序

它只保证满足谓词的元素在前、不满足的在后，不会像 std::stable_partition 那样保持相对位置。如果你只需要“所有奇数在前、偶数在后”或反过来，std::partition 足够快（O(n) 时间、O(1) 空间），且无需额外内存。

用 lambda 表达式判断奇偶，注意取模符号行为

C++ 中负数取模结果依赖实现，n % 2 == 1 对负奇数可能为 false（如 -3 % 2 在多数编译器是 -1）。更安全的做法是用 abs(n) % 2 == 1 或直接判断 n & 1 —— 后者对有符号整数也可靠，因为补码下奇数最低位恒为 1。

• 推荐谓词：[](int n) { return n & 1; }（奇数在前）
• 若要偶数在前：[](int n) { return !(n & 1); }
• 避免：[](int n) { return n % 2 == 1; }（负数时失效）

必须传入左闭右开区间，迭代器类型要匹配

std::partition 接受两个前向迭代器，范围是 [first, last)。传错边界（比如把 end() 写成 end() - 1）会导致未定义行为；用原生数组时别忘了加 std::begin()/std::end() 或指针偏移。

int arr[] = {1, 2, 3, 4, 5, 6};
size_t n = sizeof(arr) / sizeof(arr[0]);
auto it = std::partition(std::begin(arr), std::end(arr), [](int x) { return x & 1; });
// it 指向第一个偶数（或 end），此时 arr 变为 {1, 3, 5, 4, 2, 6}（顺序不定）

返回值是指向分区边界的迭代器，别忽略它

返回的迭代器指向第一个「不满足谓词」的元素，也就是奇偶分界点。你可以用它快速切分、统计数量，或继续处理某一段：

• std::distance(std::begin(arr), it) 得到奇数个数
• std::partition(it, std::end(arr), ...) 可对后半段再分区（但通常没必要）
• 如果后续要分别遍历奇数段和偶数段，直接用 [begin, it) 和 [it, end)

没保存这个

返回值，就只能重新扫描找分界——白费了 partition 的一趟遍历代价。