C++ tiefer Lazy Vergleich mit eleganter Syntax?

Question

Ich habe eine C++ - Klasse, für die ich einen Komparator definieren muss, der das Ergebnis mehrerer potenziell teurer Methoden berücksichtigen sollte. Ich möchte nicht das Ergebnis dieser Methoden für alle Objekte in meinem Set zwischenspeichern, weil die Kriterien mit der höchsten Priorität billiger sind, und ich erwarte, dass die sehr teuren unten nur in seltenen Fällen ausgelöst werden.

Wenn ich eine cmp() -Funktion hatte, die -1, 0 oder 1 zurückgab, wenn das erste Argument kleiner, gleich oder größer als das zweite Argument ist, und mit logischen Verknüpfungen, die Ganzzahlen beibehalten, könnte ich leicht schreiben

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

Leider muss ich mit dem < Operator arbeiten, so wird es hässlich, teuer und fehleranfällig:

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() && 
       (... 
      )))) 
} 

oder alternativ weniger teuer, aber immer noch ziemlich hässlich:

Ich habe über std :: tie bei This andere Frage gelesen, aber wenn ich richtig verstehe, würde die Krawatte alle meine Methoden vor Beginn der Vergleiche bewerten, und ich möchte, dass diese Argumente faul ausgewertet werden.

Ich dachte über einen Präprozessormakro wie diese definieren:

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

, die ich mag verwenden würde:

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

der Hoffnung, dass die Streben meine _x und _y in einem privaten Rahmen würde einschließen, aber ach, clang++ klagt über mehrere Definitionen von _x und _y.

Gibt es einen schöneren Weg dazu?

Answer 1

Sie alle Funktionen Mitglied weiterleiten können Sie zu einem Helfer-Vorlage nennen wollen, die durch sie geht wie nötig:

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

Die Variadic-Funktion lazy_compare führt diese Zeiger-zu-Stab-Funktionen einzeln durch, je nach Bedarf.Der Basisfall ist nur true:

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

Und der rekursive Fall ist das erste Zeiger-to-Mitglied abspringt und sehen, ob wir an diesem einen stoppen:

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

ich zu einem schön vergleichen Methode bleiben würde, geschrieben, dass die Art und Weise:

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; 
    ... 
} 

diese Weise ist es mit dem richtigen Zeichen gibt, sobald ein Verfahren anderes Resultat und geht bis zum Ende nur für den Fall, der Gleichheit.

Und Sie können es direkt in allen Komparatoren verwenden:

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 3

Sie können einfach implementieren es dieses mag:

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() || 
} 

es wird zurückkehren, sobald eine der Methoden wahr ergibt, ohne die anderen zu bewerten.

Answer 4

Hier ist ein Lazy Comparer Objekt. Es hält eine willkürliche aufrufbar F, und es ruft es, wenn Sie cmp(lhs, rhs) auf einem Paar lazy_comp_f<?> Objekte aufrufen, speichert die Ergebnisse, und sagt Ihnen, wer gewinnt:

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()>>; 

Hier ist eine Funktion Helfer Vorlage Fabrik, die tut Abzug die typ:

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

Hier ist eine faule Krawatte. Es dauert eine Reihe von Funktionen, die teure Gegenstände zu produzieren, werden verwendet, um:

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

Hier ist unser Grund cmp. Es verwendet < und erzeugt einen einigermaßen effizienten cmp-Vorgang. Lokale ADL-Lookup kann eine bessere Überlast für die Fälle, in denen wir es besser machen können:

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; 
} 

Jetzt schießt cmp von Tupeln zu ermöglichen. Zwei Helfer:

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); 
    } 
} 

und wir rufen Sie die Helfer, mit der Verteidigung gegen unerreichte Anzahl von LHS/RHS argumente:

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); 
} 

jetzt das Problem ist nur Callables bieten!

Innen class wie folgt vor:

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; 
} 

und wir fertig sind?

Beachten Sie, dass diese Lösung rekursiv funktioniert. Jeder, der cmp außer Kraft setzt, bekommt eine optimale Version, wer nicht < basiert. Wenn eine Unterstruktur ihre eigene lazy basierte cmp hat, wird sie aufgerufen.

In C++ 14 wird dies mit geringem Löschaufwand durchgeführt. In C++ 11 werden einige sinnlose Zuordnungen (zum Löschen von Typen) vorgenommen - sie können mit einem Delegaten-ähnlichen Ansatz (leichtgewichtig std::function s) oder anderen Mikrooptimierungen schneller gemacht werden.

Einige C++ 14 Funktionen verwendet. Sie sind einfach in C++ 11 zu implementieren (anders als der Rückgabetyp auto, wo ich eine Problemumgehung zur Verfügung stelle).