C ++ deep lazy comparison with elegant syntax?

Question

I have a C ++ class for which I need to define a comparator that should take into account the result of several potentially expensive methods. I don’t want to cache the result of these methods for all objects in my set, because the criteria with the highest priority are cheaper, and I expect that the very expensive ones at the bottom will be launched only in rare cases.

If I had a cmp () function that returned -1, 0 or 1, respectively, when the first argument is less, equal to or greater than the second, and using the labels of logical operators that store 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, expensive 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, conversely, less expensive, 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 read about std :: tie at This is another question, but if I understand correctly, a tie will evaluate all my methods before running comparaison and I want these arguments to be lazily evaluated.

I was thinking about defining a preprocessor macro such as:

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

What I will use as:

 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 curly braces will enclose my _x and _y in a private area, but, alas, clang++ complains about several definitions of _x and _y .

Is there a nicer way around this?

Answer 1

You can redirect all the member functions that you want to call to a helper template that views 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 paradigm will go through these element pointer functions one at a time, if necessary. The main 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 jump from the first pointer to a member and see if we can stop there:

 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 comparator object. It contains an arbitrary callable F , and it calls it when you call cmp(lhs, rhs) on a pair of lazy_comp_f<?> Objects, saves the results and tells who will win:

 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(of){} 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 the factory function template helper that infers type F :

 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 performs a number 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 main cmp . It uses < and produces a fairly efficient cmp operation. A local ADL search can find the best 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 try to resolve cmp tuples. Two assistants:

 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 an assistant with protection against an unrivaled number of arguments lhs / rhs:

 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 simply providing the calling files!

Inside the 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 are we done?

Please note that this solution works recursively. Anyone who overrides cmp gets the optimal version, anyone who doesn't get < . If some substructure has its own lazy based on cmp , it is called.

In C ++ 14, this is accomplished with low erase overhead. In C ++ 11, some meaningless selections have been made (to erase the type) - they can be made faster using an approach similar to delegates (low weight std::function s) or other microoptimizations.

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

Answer 3

I would stick with a good comparison method written this 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; ... } 

Thus, it returns with the right sign, as soon as one method gives an excellent result and ends 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 simply implement it as follows:

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