如何高效找出ID最值范围内不在数据库表中的整数？

问题背景 #

需找出数据库表中ID最小值至最大值范围内不在表中的所有ID，因MySQL无简便序列生成方式，计划在应用层处理。表中ID来自外部源，最值范围内约80%为空缺（2亿范围含约4000万行），且ID作为主键已排序取出。问题本质为求集合差集C = A\B（A为最值间所有整数，B为表中ID集合）

现有方案分析 #

• 方案1（std::set生成A再删除B元素）：完全不可行。2亿个整数存入std::set的内存开销极大（每个节点至少24字节，总内存超4.8GB），且遍历删除4000万元素的时间成本极高，属于典型的资源浪费。
• 方案2（std::set_difference+vector A）：内存爆炸。2亿个int的vector需占用800MB，加上存储B的160MB、结果C的640MB，总内存接近1.6GB，完全没必要预生成完整的A集合。
• 方案3（std::ranges::views::iota替代vector A）：方向正确，但需配合更高效的遍历逻辑，单纯用iota配合set_difference仍需遍历2亿次，效率不如直接处理B的间隙。
• 方案4（自定义遍历A+二分查B）：可行但效率一般。2亿次二分查找（每次O(log 4000万)）的时间成本远高于直接遍历B的间隙。

最优实现思路（兼顾内存与效率） #

核心逻辑：利用已排序的B集合，直接遍历其间隙生成缺失ID，无需生成A的任何实体，时间复杂度O(M)（M为B的元素数量），内存占用仅为B和结果C的大小，是最优解。

具体步骤 #

1. 从数据库获取ID的最小值min_id和最大值max_id。
2. 初始化变量prev_id = min_id - 1，用于记录上一个遍历到的ID。
3. 遍历已排序的B集合中的每个current_id：
   • 若current_id > prev_id + 1，说明[prev_id + 1, current_id - 1]范围内的ID均缺失，将这些ID逐个加入结果C（若只需统计范围，可直接存储区间进一步节省内存）。
   • 更新prev_id = current_id。
4. 遍历结束后，若prev_id < max_id，将[prev_id + 1, max_id]范围内的ID加入结果C。

数据结构选择 #

• 存储B：使用std::vector<int64_t>，数据库取出的已排序主键可直接按顺序存入，内存紧凑（4000万int64_t仅占320MB）。
• 存储结果C：使用std::vector<int64_t>，若需要每个缺失的ID，提前预分配内存可大幅提升性能。

是否需要使用reserve预分配 #

必须使用。缺失ID的数量可精确计算：missing_count = (max_id - min_id + 1) - B.size()。提前调用C.reserve(missing_count)能让vector一次性分配足够内存，避免多次扩容带来的内存拷贝开销——尤其是当缺失数量达1.6亿时，扩容的性能损耗会非常显著。

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