c++ - 是否可以使用 lower_bound() 对结构的普通数组进行二进制搜索？

Question

我在内存中有一个 16 字节宽的条目数组。每个条目由两个 64 位整数字段组成。这些条目根据每个条目的前 64 位整数的数值进行排序。是否可以在不先将数据加载到 std::vector 的情况下使用 STL 进行二进制搜索？

我已经看到我可以在普通数组上使用 STL lower_bound() 方法，但我需要它来忽略每个条目的第二个 64 位字段。这可能吗？

Answer 1

您不需要使用std::vector<>，但如果您首先将数据转换为正确的数据类型，则最简单：

#include <cstdint>

struct mystruct
{
    std::int64_t first, second;
};

您的问题尚不清楚您现在存储这些数据的方式，但我假设它与上述类似。

然后，您可以operator<为您的数据类型重载：

#include <algorithm>

bool operator <(mystruct const& ms, std::int64_t const i)
{
    return ms.first < i;
}

int main()
{
    mystruct mss[10] = { /*populate somehow*/ };
    std::int64_t search_for = /*value*/;
    mystruct* found = std::lower_bound(mss, mss + 10, search_for);
}

或者您可以定义一个自定义比较器并将其传递给std::lower_bound：

#include <algorithm>

struct mystruct_comparer
{
    bool operator ()(mystruct const& ms, std::int64_t const i) const
    {
        return ms.first < i;
    }
};

int main()
{
    mystruct mss[10] = { /*populate somehow*/ };
    std::int64_t search_for = /*value*/;
    mystruct* found = std::lower_bound(mss,
                                       mss + 10,
                                       search_for,
                                       mystruct_comparer());
}

自然地，在 C++11 中，可以使用 lambda 来代替比较器的完整仿函数。

Answer 2

struct Foo {
    int64_t lower;
    int64_t upper;
};

Foo arr[N];

Foo f;
f.lower = 42;

auto it = std::lower_bound(arr, arr + N, f,
    [](const Foo& lhs, const Foo& rhs){ return lhs.lower < rhs.lower; });

Answer 3

是的，这是可能的。您需要创建一个满足 ForwardIterator 要求的类，该类以正确的方式迭代您的元素（16 字节结构的指针可能会解决问题）。然后您需要定义自己的比较来比较忽略第二个 64 位字段的元素。 更多信息。

template <class ForwardIterator, class T, class Compare>
  ForwardIterator lower_bound ( ForwardIterator first, ForwardIterator last,
                                const T& value, Compare comp );