Is it possible to use lower_bound() to binary search a plain array of structs?

Question

I have in memory an array of 16 byte wide entries. Each entry consists of two 64 bit integer fields. The entries are in sorted order based upon the numerical value of the first 64 bit integer of each entry. Is it possible to binary search this with the STL without first loading the data into a std::vector?

I have seen that I can use the STL lower_bound() method on plain arrays, but I need it to ignore the second 64 bit field of eachy entry. Is this possible?

Answer 1

You don't need to use std::vector<>, but it is easiest if you get your data into a proper data type first:

#include <cstdint>

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

Your question is unclear as to the way you're storing this data now, but I'm assuming it's something like the above.

Then you can either overload operator< for your data type:

#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);
}

Or you can define a custom comparator and pass that to 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());
}

Naturally, in C++11, a lambda can be used instead of a full-fledged functor for the comparator.