You need to enable JavaScript to run this app. C++17下实现满足谓词的最长连续连通子向量的优雅精简算法
优惠活动
大模型
产品
解决方案
定价
更多

C++17下实现满足谓词的最长连续连通子向量的优雅精简算法

问题背景
  • 输入为连续元素组成的向量,例如示例输入:
    std::vector<std::int32_t> allnumbers{1,2,-3,4,5,-6,7,8,9};
  • 给定任意布尔判断谓词,要求输出满足该谓词的最长连续相邻子向量,子向量元素必须和原输入顺序一致、完全相邻,不能跳过中间元素取散列值。

正误输出对照(以“元素大于3”为判断条件为例):

  • 错误输出1:std::vector<std::int32_t> allnumbers{4,5,7,8,9}; 原因:原序列中5和7之间存在元素-6,元素不相邻
  • 错误输出2:std::vector<std::int32_t> allnumbers{4,5}; 原因:不是最长的满足条件的连续子段
  • 正确输出:std::vector<std::int32_t> allnumbers{7,8,9};
实现要求
  • 基于C++17标准编写,不引入Boost等第三方依赖
  • 优先复用C++标准库设施,在不损失可读性的前提下精简冗余代码
  • 保持原有单次遍历的逻辑,仅用少量迭代器跟踪执行状态,不需要额外优化性能或内存(原暴力实现的性能已经满足使用需求)
精简后的参考实现
#include <algorithm>
#include <iostream>
#include <stdint.h>
#include <vector>

template <class Pred, class T>
std::vector<T> longest_connected_subvector(Pred pred, const std::vector<T>& input) {
    auto longest_beg = input.cend(), longest_end = input.cend();
    size_t longest_len = 0;
    auto cur = input.cbegin();

    while (cur != input.cend()) {
        // 定位下一段满足条件的连续区间起点
        cur = std::find_if(cur, input.cend(), pred);
        // 定位当前连续区间的终点(第一个不满足谓词的位置)
        auto seg_end = std::find_if_not(cur, input.cend(), pred);
        auto seg_len = std::distance(cur, seg_end);

        // 更新最长区间记录
        if (seg_len > longest_len) {
            longest_len = seg_len;
            longest_beg = cur;
            longest_end = seg_end;
        }
        cur = seg_end;
    }

    return {longest_beg, longest_end};
}

int main() {
    const auto larger_than_3 = [](std::int32_t v) { return v > 3; };
    const std::vector<std::int32_t> allnumbers{1, 2, -3, 4, 5, -6, 7, 8, 9};
    
    for (auto v : longest_connected_subvector(larger_than_3, allnumbers)) {
        std::cout << v << '\n';
    }
}
优化说明
  • 直接使用标准库提供的std::find_if_not,替代原有代码中手写的“取反谓词”lambda,减少冗余代码,可读性更强
  • 将原有硬绑定std::function和std::int32_t的函数改为通用模板,既减少了谓词拷贝的额外开销,也能适配任意类型的向量、任意可调用对象作为谓词,通用性更强
  • 统一使用const版本的迭代器,匹配常量输入的场景,避免暴露不必要的可修改权限
  • 合并冗余的中间变量命名,保持逻辑链路清晰:定位区间起点→定位区间终点→对比更新最长记录→跳到当前区间终点开启下一轮遍历

内容的提问来源于stack exchange,提问作者Jan Hackenberg

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.20 00:45:08