有序区间找首个不同元素的递增二分查找方案问询

修复代码缺陷后，该问题已重新整理为代码评审请求。

我有一个容量达千兆字节的超大有序向量，里面包含大量重复值，经常需要跳转到下一个不同值。向量中的元素不是整数，且比较操作耗时，用std::upper_bound效率很低——它需要约log₂(n)次比较，但目标元素通常离当前位置很近（大多1-10个元素，极少情况11-100个，超过101个的情况几乎没有）。

我测试发现，递增式二分查找比直接用std::upper_bound快约30%。

我觉得自己可能在重复造轮子，这种算法肯定有人已经实现过了。STL里有没有现成的解决方案？

另外，我写的这段代码是否正确？有没有遗漏什么坑？还有优化空间吗？

演示代码：

#include <algorithm>
#include <vector>

template<class ForwardIt, class Comp = std::less<>>
constexpr ForwardIt increasingMismatchBinarySearch(ForwardIt first, ForwardIt last, Comp comp = {}, size_t starting_search_range = 1)
{
    const auto current = *first++;

    size_t short_search_range = starting_search_range;

    while (first != last) {
        const auto short_search_end = std::min(first + short_search_range, last);

        first = std::upper_bound(first, short_search_end, current, comp);

        if (first != short_search_end)
            return first;

        short_search_range *= 2;
    }

    return last;
}

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

    for (auto it = v.begin(); it != v.end(); it = increasingMismatchBinarySearch(it, v.end())) {
        // Some work
    }
}

STL现成方案说明 #

STL中没有直接匹配该场景的算法。标准库查找算法分为两类：全范围二分查找（如std::upper_bound）、线性扫描（如std::find_if），你这种“小范围二分+范围翻倍”的混合策略属于针对特定数据分布的定制优化，不在标准库的通用算法覆盖范围内。

代码正确性与潜在陷阱 #

1. 正确性问题：
   • 函数开头直接执行*first++，若传入first == last会触发未定义行为，需先判断first != last再取值。
   • 模板参数标注为ForwardIt，但代码中使用了+算术运算，仅支持随机访问迭代器（如std::vector::iterator），对非随机访问迭代器（如std::list::iterator）会编译失败，需在模板中添加静态断言明确限制，或修改注释说明适用迭代器类型。
2. 潜在陷阱：
   • 若starting_search_range默认值设置过大，会直接退化为普通std::upper_bound，失去优化意义，需根据数据分布调整。
   • 依赖比较函数comp满足严格弱序，否则std::upper_bound结果不可预料，需保证传入的比较函数符合要求。

优化方向 #

1. 迭代器类型校验：添加静态断言限制仅接受随机访问迭代器：

   static_assert(std::is_same_v<typename std::iterator_traits<ForwardIt>::iterator_category, std::random_access_iterator_tag>,
                 "This algorithm requires random access iterators.");
   

2. 起始范围调优：根据实际数据分布，将starting_search_range默认值设为更贴合场景的数值（如10），减少初始循环次数。
3. 边界安全处理：在函数开头增加if (first == last) return last;，避免空范围导致的未定义行为。
4. 代码精简：可以将short_search_end的计算合并，但现代编译器会自动优化，影响不大。

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