C++ deep lazy comparison with elegant syntax?

Question

I have a C++ class for which I need to define a comparator that should consider the result of several potentially expensive methods. I do not want to cache the result of these methods for all the objects in my set, because the criteria with the highest priority are cheaper, and I expect the very expensive ones at the bottom to trigger only in rare cases.

If I had a cmp() function that returned respectively -1, 0, or 1 when the first argument is lesser, equal, or greater to the second, and with shortcut logical operators that preserve integers, I could easily write

int compare(const Class &rhs) const {
    return cmp(expensive_method_a(), rhs.expensive_method_b()) ||
           cmp(expensive_method_b(), rhs.expensive_method_b()) ||
           ...
}

Unfortunately I need to work with the < operator, so it becomes ugly, costly, and error-prone:

bool operator<(const Class &rhs) const {
    return expensive_method_a() < rhs.expensive_method_a() ||
           (expensive_method_a() == rhs.expensive_method_a() &&
            (expensive_method_b() < rhs.expensive_method_b() ||
             (expensive_method_b() == rhs.expensive_method_b() &&
              (...
           ))))
}

Or alternatively, less costly but still pretty ugly:

bool operator<(const Class &rhs) const {
    auto al = expensive_method_a(), ar = rhs.expensive_method_a();
    if (al != ar) return al < ar;
    auto bl = expensive_method_b(), br = rhs.expensive_method_b();
    if (bl != br) return bl < br;

I've read about std::tie at This other question, but if I understand correctly, the tie would evaluate all my methods before starting the comparaison, and I want these arguments to be lazily evaluated.

I thought about defining a preprocessor macro such as this:

#define CUT_COMPARE(a,b) { auto _x = (a); auto _y = (b); if (_x != _y) return (_x < _y); }

That I would use like:

bool operator<(const Class &rhs) const {
    CUT_COMPARE(expensive_method_a(), rhs.expensive_method_a());
    CUT_COMPARE(expensive_method_b(), rhs.expensive_method_b());
    ...
}

hoping that the braces would enclose my _x and _y in a private scope, but alas, clang++ complains of multiple definitions of _x and _y.

Is there a prettier way around this ?

Answer 1

You can forward all the member functions you want to call to a helper template that walks through them as necessary:

bool operator<(const Class& rhs) const {
    return lazy_compare(*this, rhs, &Class::expensive_1,
                                    &Class::expensive_2,
                                    &Class::expensive_3);
}   

The lazy_compare variadic function will walk through those pointer-to-member functions one at a time, as necessary. The base case is just true:

template <typename T, typename... MFs>
bool lazy_compare(const T&, const T&, MFs...) {
    return true;
}

And the recursive case is to pop off the first pointer-to-member and see if we can stop at that one:

template <typename T, typename R, typename... MFs>
bool lazy_compare(const T& left, const T& right, R (T::*mf)() const, MFs... rest) {
    R vleft = (left.*mf)(), vright = (right.*mf)();
    if (vleft != vright) {
        return vleft < vright;
    }   
    else {
        return lazy_compare(left, right, rest...);
    }   
}

Answer 2

Here is a lazy comparer object. It holds some arbitrary callable F, and it invokes it when you call cmp(lhs, rhs) on a pair of lazy_comp_f<?> objects, stores the results, and tells you who wins:

template<class F>
struct lazy_comp_f {
  F f;
  template<class F1, class F2>
  friend int cmp( lazy_comp_f<F1>const& lhs, lazy_comp_f<F2>const& rhs) {
    auto l = lhs.f();
    auto r = rhs.f();
    // using cmp_ns::cmp; here
    return cmp(l,r);
  }

  // ctors
  lazy_comp_f(F&& fin):f(std::forward<F>(fin)) {}
  lazy_comp_f(lazy_comp_f&&)=default;
  lazy_comp_f(lazy_comp_f const&)=default;
  template<class O, class=std::enable_if_t<std::is_convertible<O const&,F>>>
  lazy_comp_f(lazy_comp_f<O> const&o):f(o.f){}
  template<class O, class=std::enable_if_t<std::is_convertible<O,F>>>
  lazy_comp_f(lazy_comp_f<O>&&o):f(std::move(o).f){}
};
template<class T>
using lazy_comp_t = lazy_comp_f<std::function<T()>>;

Here is a template factory function helper that does deduction of the F type:

template<class F>
lazy_comp_f<std::decay_t<F>>
lazy_comp(F&& f){ return {std::forward<F>(f)}; }

Here is a lazy tie. It takes a series of functions that are used to produce expensive items:

template<class...Fs, class R=std::tuple< lazy_comp_f<std::decay_t<Fs>>... >>
R lazy_tie( Fs&& fs ) {
  return R( lazy_comp(std::forward<Fs>(fs)...) );
}

Here is our basic cmp. It uses < and produces a reasonably efficient cmp operation. Local ADL lookup can find a better overload for cases where we can do it better:

template<class T, class U>
int cmp( T const& lhs, U const& rhs ) {
  if (lhs < rhs) return -1;
  if (rhs < lhs) return 1;
  return 0;
}

Now an effort to allow cmp of tuples. Two helpers:

namespace details {
  template<class...Ts, class...Us>
  int cmp(
    std::index_sequence<>,
    std::tuple<Ts...> const& lhs,
    std::tuple<Us...> const& rhs
  ) {
    return 0;
  }
  template<size_t I, size_t...Is,class...Ts, class...Us>
  int cmp(
    std::index_sequence<I, Is...>,
    std::tuple<Ts...> const& lhs,
    std::tuple<Us...> const& rhs
  ) {
    // maybe using comp_ns::cmp here?
    int c = cmp( std::get<I>(lhs), std::get<I>(rhs) );
    if (c!=0) return c;
    return cmp(std::index_sequence<Is...>{}, lhs, rhs);
  }
}

and we call the helper, with defence against unmatched number of lhs/rhs args:

template<class...Ts, class...Us>
std::enable_if_t<sizeof...(Ts)==sizeof...(Us), int>
cmp(
  std::tuple<Ts...> const& lhs,
  std::tuple<Us...> const& rhs
) {
  return details::cmp( std::make_index_sequence<sizeof...(Ts)>{}, lhs, rhs );
}

now the problem is to just provide callables!

Inside class do the following:

auto lazy_comparer() const
// std::tuple< lazy_comp_t<A>, lazy_comp_t<B>, lazy_comp_t<C> > in C++11
// where `A`, `B` and `C` are the return types of expensive_method_a etc
{
  return lazy_tie(
    [=]{ return expensive_method_a(); },
    [=]{ return expensive_method_b(); },
    [=]{ return expensive_method_c(); }
    // etc
  );
}
friend int cmp( Class const& lhs, Class const& rhs ) {
  // using namespace cmp_ns::cmp here
  return cmp( lhs.lazy_comparer(), rhs.lazy_comparer() ) < 0;
}
friend bool operator<( Class const& lhs, Class const& rhs ) {
  return cmp(lhs,rhs)<0;
}

and we are done?

Note that this solution works recursively. Anyone who overrides cmp gets an optimal version, anyone who doesn't gets a < based one. If some substructure has its own lazy based cmp, it gets called.

In C++14 this is done with low type erasure overhead. In C++11, some pointless allocations (for type erasure) are done -- they can be made faster with a delegate-like approach (light weight std::functions) or other microoptimizations.

Some C++14 features used. They are easy to implement in C++11 (other than the auto return type, where I provide a workaround).

Answer 3

I would stick to a nice compare method, written that way :

int compare(const Class &rhs) const {
    int cr;
    cr = cmp(expensive_method_a(), rhs.expensive_method_a());
    if (cr != 0) return cr;
    cr = cmp(expensive_method_b(), rhs.expensive_method_b());
    if (cr != 0) return cr;
    ...
}

That way it returns with correct sign as soon as one method gives different result and goes down to the end only in case of equality.

And you can use it directly in all comparators :

bool operator<(const Class &rhs) const {
    return compare(rhs) < 0;
}
bool operator<=(const Class &rhs) const {
    return compare(rhs) <= 0;
}
bool operator>(const Class &rhs) const {
    return compare(rhs) > 0;
}
bool operator>=(const Class &rhs) const {
    return compare(rhs) >= 0;
}
bool operator==(const Class &rhs) const {
    return compare(rhs) == 0;
}
bool operator!=(const Class &rhs) const {
    return compare(rhs) != 0;
}

Answer 4

You can just implement it like this:

bool operator<(const Class &rhs) const {
    return expensive_method_a() < rhs.expensive_method_a() ||
           expensive_method_b() < rhs.expensive_method_b() ||
           ..
           expensive_method_N() < rhs.expensive_method_N() ||
}

it will return as soon as one of the methods evaluates to true, without evaluating the other ones.