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 代替比较器的完整仿函数。