增加二分搜索以查找排序范围内的不匹配情况

Question

我有非常大的向量（千兆字节），其中包含重复的排序值，并且经常需要跳转到向量中的下一个不同值。向量中的实际值不是整数，比较是耗时的操作，因此使用

std::upper_bound

在这里无效，因为它涉及 log2(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
    }
}

Answer 1

根据上面来自 来自莫斯科的 Vlad 和 Ben Voigt 的评论，这里是算法的更新版本。

#include <algorithm>
#include <vector>

// Algorithm works similarly to std::upper_bound, but uses element specified by iterator *first* to find first element in range which is not equal to it.
template<class RandomIt, class Comp = std::less<>>
constexpr RandomIt increasingMismatchBinarySearch(RandomIt first, RandomIt last, Comp comp = {}, size_t starting_search_range = 1)
{
    if (first == last)
        return last;
    
    const auto current = *first++;

    size_t short_search_range = starting_search_range;

    while (first != last) {
        const auto short_search_end = std::distance(first, last) < starting_search_range ? last : std::next(first, short_search_range);

        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
    }
}

根据 Sam Varshavchik 的评论，没有内置的 STL 实现。

无论如何，我仍在寻找一种组合 STL 算法的方法（可能带有谓词或带有视图/投影的范围），以便用纯 STL 来实现这一点。