是否可以使用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代替比较器的完整仿函数.