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
相关产品推荐
相关产品推荐

