基于判断函数的原地单循环数组重排实现问题

需要实现一个C++模板函数，接收数组、数组大小以及判断函数（或Lambda表达式），根据判断函数的返回值对数组进行重排。例如传入数组{1,2,3,4,5,6}和判断偶数的isEven函数后，数组应变为[2 4 6 1 5 3]。

当前实现使用了额外数组，现在要求必须不使用额外数组，且仅通过一次循环完成。

当前实现代码 #

template <typename T, typename FUN>
size_t part(T* arr, size_t size, FUN f) {
    T new_arr[size] = {};
    int first = 0;
    int last = size - 1;
    int index = 0;
    bool changed = false;
    for(int i = 0; i < size; i++){
        if(f(arr[i])){
            new_arr[first] = arr[i];
            first++;
        } else { 
            if(!changed){index = i;}
            new_arr[last] = arr[i];
            last--;
        }
    }
    for(int j = 0; j < size; j++){
        std::cout << new_arr[j] << " ";
    }
    return new_arr;
}

采用双指针法可以在不使用额外数组的前提下，通过一次遍历完成重排：

#include <algorithm>

template <typename T, typename FUN>
size_t part(T* arr, size_t size, FUN f) {
    if (size == 0) return 0;

    size_t left = 0;
    size_t right = size - 1;

    while (left < right) {
        // 左指针定位第一个不满足条件的元素
        while (left < right && f(arr[left])) {
            left++;
        }
        // 右指针定位第一个满足条件的元素
        while (left < right && !f(arr[right])) {
            right--;
        }
        // 交换元素，让满足条件的移到左侧，不满足的移到右侧
        if (left < right) {
            std::swap(arr[left], arr[right]);
            left++;
            right--;
        }
    }

    // 返回满足判断条件的元素总数
    return f(arr[left]) ? left + 1 : left;
}

方案说明 #

• 双指针left从数组头部出发，right从尾部出发，向中间遍历：
  • left找到第一个不满足判断条件的元素时停下；
  • right找到第一个满足判断条件的元素时停下；
  • 交换两个元素的位置，让满足条件的元素移到左侧区域，不满足的移到右侧区域；
• 整个过程仅需一次遍历数组的核心逻辑，符合“一次循环完成”的要求；
• 最终返回值为满足判断条件的元素个数，方便调用者后续处理；
• 测试验证：传入数组{1,2,3,4,5,6}和Lambda表达式[](int x){ return x % 2 == 0; }，数组会被重排为[2,4,6,1,5,3]，完全符合需求。

内容的提问来源于stack exchange，提问作者Kamil