search - C++ lambdas for std::sort and std::lower_bound/equal_range on a struct element in a sorted vector of structs

Question

I have a std::vector of this struct:

struct MS
{        
  double aT;
  double bT;
  double cT;
};

which I want to use std::sort on aswell as std::lower_bound/equal_range etc...

I need to be able to sort it and look it up on either of the first two elements of the struct. So at the moment I have this:

class MSaTLess 
{
public:
  bool operator() (const MS &lhs, const MS &rhs) const
  {
    return TLess(lhs.aT, rhs.aT);
  }
  bool operator() (const MS &lhs, const double d) const
  {
    return TLess(lhs.aT, d);
  }
  bool operator() (const double d, const MS &rhs) const
  {
    return TLess(d, rhs.aT);
  }
private:
  bool TLess(const double& d1, const double& d2) const
  {
    return d1 < d2;
  }
};


class MSbTLess 
{
public:
  bool operator() (const MS &lhs, const MS &rhs) const
  {
    return TLess(lhs.bT, rhs.bT);
  }
  bool operator() (const MS &lhs, const double d) const
  {
    return TLess(lhs.bT, d);
  }
  bool operator() (const double d, const MS &rhs) const
  {
    return TLess(d, rhs.bT);
  }
private:
  bool TLess(const double& d1, const double& d2) const
  {
    return d1 < d2;
  }
};

This allows me to call both std::sort and std::lower_bound with MSaTLess() to sort/lookup based on the aT element and with MSbTLess() to sort/lookup based on the bT element.

I'd like to get away from the functors and use C++0x lambdas instead. For sort that is relatively straightforward as the lambda will take two objects of type MS as arguments.

What about for the lower_bound and other binary search lookup algorithms though? They need to be able to call a comparator with (MS, double) arguments and also the reverse, (double, MS), right? How can I best provide these with a lambda in a call to lower_bound? I know I could create an MS dummy object with the required key value being searched for and then use the same lambda as with std::sort but is there a way to do it without using dummy objects?

Answer 1

It's a little awkward, but if you check the definitions of lower_bound and upper_bound from the standard, you'll see that the definition of lower_bound puts the dereferenced iterator as the first parameter of the comparison (and the value second), whereas upper_bound puts the dereferenced iterator second (and the value first).

So, I haven't tested this but I think you'd want:

std::lower_bound(vec.begin(), vec.end(), 3.142, [](const MS &lhs, double rhs) {
    return lhs.aT < rhs;
});

and

std::upper_bound(vec.begin(), vec.end(), 3.142, [](double lhs, const MS &rhs) {
    return lhs < rhs.aT;
});

This is pretty nasty, and without looking up a few more things I'm not sure you're actually entitled to assume that the implementation uses the comparator only in the way it's described in the text - that's a definition of the result, not the means to get there. It also doesn't help with binary_search or equal_range.

It's not explicitly stated in 25.3.3.1 that the iterator's value type must be convertible to T, but it's sort of implied by the fact that the requirement for the algorithm is that T (in this case, double) must be LessThanComparable, not that T must be comparable to the value type of the iterator in any particular order.

So I think it's better just to always use a lambda (or functor) that compares two MS structs, and instead of passing a double as a value, pass a dummy MS with the correct field set to the value you're looking for:

std::upper_bound(vec.begin(), vec.end(), MS(3.142,0,0), [](const MS &lhs, const MS &rhs) {
    return lhs.aT < rhs.aT;
});

If you don't want to give MS a constructor (because you want it to be POD), then you can write a function to create your MS object:

MS findA(double d) {
    MS result = {d, 0, 0};
    return result;
}
MS findB(double d) {
    MS result = {0, d, 0};
    return result;
}

Really, now that there are lambdas, for this job we want a version of binary search that takes a unary "comparator":

double d = something();
unary_upper_bound(vec.begin(), vec.end(), [d](const MS &rhs) {
    return d < rhs.aT;
});

C++0x doesn't provide it, though.