CODEWITHSUNDEEP
c++algorithmstl
Martin Beckett
Martin Beckett

Reputation: 96109

compare function for upper_bound / lower_bound

I want to find the first item in a sorted vector that has a field less than some value x.
I need to supply a compare function that compares 'x' with the internal value in MyClass but I can't work out the function declaration.
Can't I simply overload '<' but how do I do this when the args are '&MyClass' and 'float' ?

 float x;
 std::vector< MyClass >::iterator last = std::upper_bound(myClass.begin(),myClass.end(),x);

Upvotes: 21

Views: 50371

Answers (4)

bigdata2
bigdata2

Reputation: 1041

Pass a lambda function to upper_bound

 float x;
 MyClass target;
 target.x_ = x;
 std::vector< MyClass >::iterator last = 
 std::upper_bound(myClass.begin(),myClass.end(),target, 
 [](const MyClass& a, const MyClass& b){return a.x_ < b.x_;});

Upvotes: 4

Mark Ransom
Mark Ransom

Reputation: 308140

What function did you pass to the sort algorithm? You should be able to use the same one for upper_bound and lower_bound.

The easiest way to make the comparison work is to create a dummy object with the key field set to your search value. Then the comparison will always be between like objects.

Edit: If for some reason you can't obtain a dummy object with the proper comparison value, then you can create a comparison functor. The functor can provide three overloads for operator() :

struct MyClassLessThan
{
    bool operator() (const MyClass & left, const MyClass & right)
    {
        return left.key < right.key;
    }
    bool operator() (const MyClass & left, float right)
    {
        return left.key < right;
    }
    bool operator() (float left, const MyClass & right)
    {
        return left < right.key;
    }
};

As you can see, that's the long way to go about it.

Upvotes: 20

Ghostrider
Ghostrider

Reputation: 7775

You can further improve Mark's solution by creating a static instance of MyClassLessThan in MyClass

class CMyClass 
{
   static struct _CompareFloatField
   {
      bool operator() (const MyClass & left, float right) //...
      // ...
   } CompareFloatField;
};

This way you can call lower_bound in the following way:

std::lower_bound(coll.begin(), coll.end(), target, CMyClass::CompareFloatField);

This makes it a bit more readable

Upvotes: 9

Borbus
Borbus

Reputation: 593

I think what you need is std::bind2nd(std::less<MyClass>(), x). But, of course, the operator< must be defined for MyClass.

Edit: oh and I think you will need a constructor for MyClass that accepts only a float so that it can be implicitly converted. However, there might be a better way to do this.

Upvotes: 0

Related Questions