Geek asks and answers

Is it possible to use lower_bound () to binary search a simple array of structures?

I have an array of 16 bytes in my memory. Each record consists of two 64-bit integer fields. Entries are sorted based on the numerical value of the first 64-bit integer of each entry. Is it possible to binary search for this using STL without first loading data into std :: vector?

I saw that I can use the STL lower_bound () method for simple arrays, but I need it to ignore the second 64-bit field of each record. Is it possible?

+5
source share
3 answers

You do not need to use std::vector<>, but this is easiest if you first get your data into the correct data type:

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

, ++ 11 .

+5
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; });
+2

Yes it is possible. You need to create a class that satisfies the requirements for ForwardIterator that correctly iterates your elements (a pointer to a structure of 16 bytes is likely to do the trick). Then you need to define your own Compare to compare elements ignoring the second 64-bit field. more details .

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

More articles:


All Articles