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).