CODEWITHSUNDEEP
c++
Samuel Danielson
Samuel Danielson

Reputation: 5471

How can I use std::lower_bound when I'm only interested in comparing part of the value and can't assume a default constructor for the other part

Here's what I wish to do. Using a generic sorted container. For associative containers search for a key, find a generic value. For non-associative containers search for key, find nullptr_t nullptr. It would be useful for set intersections between associative and non-associative containers.

I have a search function that should leave &it on the lower bound of a std::pair where i <= it->first.

template <typename Iter, typename End>
bool search (unsigned i, Iter& it, End& end) {...}

Here's where I'm stumped. std::lower_bound's 3rd argument takes a reference to a type. I'm only interested in searching for the value of it->first. Previously I've made a dummy value using a default constructor for value.second, but that seems janked.

std::lower_bound

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

Upvotes: 3

Views: 1001

Answers (2)

Benjamin Lindley
Benjamin Lindley

Reputation: 103741

You can pass a heterogeneous comparator (i.e. one which takes arguments who's types are not the same) to lower_bound. The first argument will come from a dereferenced iterator from the range, the second argument will come from the value passed as the third argument to lower_bound. So, you can use something like this:

struct Compare
{
    template<typename T1, typename T2>
    bool operator()(T1 const& lhs, T2 const& rhs) const
    {
        return lhs.first < rhs;
    }
};

Then you can call lower_bound like this:

lower_bound(container.begin(), container.end(), value, Compare());

Upvotes: 5

davidhigh
davidhigh

Reputation: 15518

You can use std::lower_bound as follows (in C++14):

using T=int;
std::vector<std::pair<unsigned, T> > pairVector;
T searchedValue=1;
std::lower_bound(pairVector.begin(), pairVector.end(), searchedValue
               , [](auto a, auto b) {return a.first < b;} )

See here why such a binary function works.

EDIT: that is basically the same as the former answer by Benjamin Lindley, just that it uses a lambda closure instead of a pre-defined class. I'll let it stand, though.

Upvotes: 1

Related Questions