如何用C++标准库算法组合实现条件替换相邻重复值？

功能需求 #

若向量中某值相邻重复次数超过repetitions，且未被指定predicate排除，则将所有该重复值替换为指定新值。

核心疑问 #

能否借助C++标准库算法或其组合实现上述逻辑，提升代码通用性、避免重复造轮子？

现有代码（存在越界bug） #

#include <iostream>
#include <vector>

bool pred(int value) { const int excluder = 1; return value == excluder; }

void replace_repeating(int* first, int* last, const auto& pred, size_t repetitions, int replacement) {
    size_t count = 0;
    for (; first < last; ++first) {
        if (*first == *(first+1)) { // 当first为last-1时，访问*(first+1)属于越界
            count++;
        }
        else {
            if (count >= repetitions && !pred(*first)) {
                std::fill(first - count +1 , first +1, replacement);
            }
            count = 1;
        }
    }
}

int main() {
    std::vector<int> v = { 1, 1, 1, 7, 7, 7, 7, 3, 3, 4, 4, 5, 6, 6, 6 };
    size_t repetitions = 3;
    int replacement = 0;

    replace_repeating(v.data(), v.data()+v.size(), pred, repetitions, replacement);

    for (size_t i = 0; i < v.size(); i++) {
        std::cout << v[i] << " ";
    }
}

补充约束 #

• 性能至关重要，需避免冗余操作（向量规模可达GB级）；
• 计划使用执行策略（execution policies），因此范围（ranges）的适用性存疑。

基于标准库算法的实现方案 #

可以通过组合std::find_if_not、std::fill等标准库算法实现需求，同时解决原代码的越界问题，提升通用性并支持执行策略：

#include <iostream>
#include <vector>
#include <algorithm>
#include <execution>

template <typename Iterator, typename Predicate, typename T>
void replace_repeating(Iterator first, Iterator last, Predicate pred, size_t repetitions, const T& replacement) {
    while (first != last) {
        // 用标准库算法定位当前连续重复元素的区间末尾
        const auto current_val = *first;
        const auto range_end = std::find_if_not(
            std::next(first), 
            last, 
            [current_val](const auto& val) { return val == current_val; }
        );

        // 计算重复次数（随机访问迭代器下std::distance是O(1)操作）
        const size_t count = std::distance(first, range_end);
        
        // 满足条件则替换整个区间
        if (count >= repetitions && !pred(current_val)) {
            // 可直接替换执行策略，比如std::execution::par_unseq（需确保元素可安全并行修改）
            std::fill(std::execution::seq, first, range_end, replacement);
        }

        // 移动到下一个不同元素的起始位置
        first = range_end;
    }
}

bool pred(int value) { const int excluder = 1; return value == excluder; }

int main() {
    std::vector<int> v = { 1, 1, 1, 7, 7, 7, 7, 3, 3, 4, 4, 5, 6, 6, 6 };
    const size_t repetitions = 3;
    const int replacement = 0;

    replace_repeating(v.begin(), v.end(), pred, repetitions, replacement);

    for (const auto& num : v) {
        std::cout << num << " ";
    }
}

方案优势 #

1. 通用性提升：模板化迭代器支持任意容器（vector、array、deque等）和可比较的元素类型，不再局限于int*指针；谓词参数支持任意可调用对象（函数、lambda、函数对象）。
2. 安全性修复：通过std::find_if_not定位区间，彻底避免原代码的越界访问问题。
3. 性能优化：
   • 标准库算法std::find_if_not和std::fill均经过平台特定优化，性能不逊于手动遍历；
   • 支持C++17的执行策略，对于GB级大容器，切换为std::execution::par_unseq可利用多核并行填充，大幅提升处理速度（需确保元素类型可平凡复制、无线程间数据竞争）；
   • 随机访问迭代器下std::distance是O(1)操作，无额外性能损耗。
4. 代码简洁性：复用标准库算法，避免手动维护计数变量的冗余逻辑，代码可读性更强。

执行策略注意事项 #

• 使用std::execution::par_unseq时，需确保：
  • 元素类型满足std::is_trivially_copyable_v<T>，避免并行赋值时的未定义行为；
  • 谓词pred是无副作用的纯函数，不会在并行执行中引发数据竞争。

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