Confronto C++ profondo e pigro con sintassi elegante?

Question

Ho una classe C++ per la quale ho bisogno di definire un comparatore che dovrebbe considerare il risultato di diversi metodi potenzialmente costosi. Non voglio memorizzare nel cache il risultato di questi metodi per tutti gli oggetti nel mio set, perché i criteri con la priorità più alta sono più economici, e mi aspetto che quelli molto costosi in basso si attivino solo in rari casi.

Se avessi una funzione cmp() restituita rispettivamente -1, 0 o 1 quando il primo argomento è minore, uguale o superiore al secondo e con gli operatori logici di scelta rapida che conservano gli interi, potrei scrivere facilmente

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

Purtroppo ho bisogno di lavorare con l'operatore <, così diventa brutto, costoso e soggetto a errori:

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

Oppure, in alternativa, meno costoso ma ancora piuttosto brutta:

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; 

Ho letto su std :: tie a This altra domanda, ma se ho capito bene, la cravatta valuterà tutti i miei metodi prima di iniziare il confronto, e voglio che questi argomenti siano pigramente valutati.

ho pensato sulla definizione di un macro preprocessore come questa:

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

che avrei usato come:

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

sperando che le parentesi graffe avrebbero racchiudere la mia _x e _y in un ambito privato, ma ahimè, clang++ si lamenta di più definizioni di _x e _y.

C'è un modo più carino per aggirare questo?

Answer 1

È possibile inoltrare tutte le funzioni membro che si desidera chiamare a un modello di supporto che cammina attraverso di loro, se necessario:

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

La funzione variadica di lazy_compare attraverserà le funzioni da un puntatore a un membro alla volta, se necessario.Il caso base è solo true:

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

E il caso ricorsivo è quello di pop off il primo membro puntatore-a-e vedere se siamo in grado di fermarsi a che uno:

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

Vorrei attenersi a un bel confrontare metodo, scritta in questo modo:

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

In questo modo si ritorna con il corretto segno non appena un metodo dà risultati diversi e scende fino alla fine solo in caso di uguaglianza.

E si può utilizzare direttamente in tutti i comparatori:

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

Si può solo implementare in questo modo:

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

si tornerà non appena uno dei metodi restituisce true, senza valutare gli altri.

Answer 4

Ecco un oggetto di confronto lazy. Essa detiene alcuni arbitrario callable F, e si invoca quando si chiama cmp(lhs, rhs) su un paio di lazy_comp_f<?> oggetti, memorizza i risultati, e ti dice chi vince:

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

Ecco una funzione di supporto modello di fabbrica che fa la deduzione di il tipo F:

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

Ecco un legame artificiale. Ci vuole una serie di funzioni che vengono utilizzati per la produzione di oggetti costosi:

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

Qui è la nostra base cmp. Utilizza < e produce un'operazione ragionevolmente efficiente cmp. ricerca ADL locale può trovare un sovraccarico migliore per i casi in cui si può fare meglio:

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

Ora uno sforzo per consentire cmp di tuple. Due aiutanti:

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

e che chiamiamo l'aiutante, con la difesa contro il numero senza precedenti di LHS/args sd:

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

ora il problema è quello di fornire solo callable!

All'interno class effettuare le seguenti operazioni:

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

e abbiamo finito?

Si noti che questa soluzione funziona in modo ricorsivo. Chi sostituisce cmp ottiene una versione ottimale, chiunque non ne abbia una basata su <. Se qualche sottostruttura ha il proprio lazy basato su cmp, viene chiamato.

In C++ 14 questo viene eseguito con un overhead di cancellazione di tipo basso. In C++ 11, alcune assegnazioni inutili (per la cancellazione del testo) vengono eseguite - possono essere eseguite più rapidamente con un approccio di tipo delegato (peso leggero std::function s) o altre microottimizzazioni.

Alcune caratteristiche di C++ 14 utilizzate. Sono facili da implementare in C++ 11 (diverso dal tipo di ritorno auto, dove fornisco una soluzione alternativa).