C++ so sánh lười biếng sâu với cú pháp thanh lịch?

Question

Tôi có một lớp C++ mà tôi cần để xác định một bộ so sánh nên xem xét kết quả của một số phương pháp có khả năng tốn kém. Tôi không muốn cache kết quả của các phương thức này cho tất cả các đối tượng trong tập của tôi, bởi vì các tiêu chí có mức ưu tiên cao nhất là rẻ hơn, và tôi mong đợi những cái rất đắt ở phía dưới chỉ kích hoạt trong những trường hợp hiếm hoi.

Nếu tôi có hàm cmp() trả về -1, 0 hoặc 1 khi đối số đầu tiên nhỏ hơn, bằng hoặc lớn hơn đối số thứ hai, và với toán tử logic giữ nguyên số nguyên, tôi có thể dễ dàng viết

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

Đáng tiếc là tôi cần phải làm việc với các nhà điều hành <, vì vậy nó trở nên xấu xí, tốn kém, và dễ bị lỗi:

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

Hoặc cách khác, ít tốn kém nhưng vẫn còn khá xấu xí:

Tôi đã đọc về std :: tie tại This câu hỏi khác, nhưng nếu tôi hiểu chính xác, tie sẽ đánh giá tất cả các phương pháp của tôi trước khi bắt đầu comparaison, và tôi muốn các đối số được lazily đánh giá.

Tôi nghĩ về việc xác định một macro tiền xử lý như thế này:

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

Rằng tôi sẽ sử dụng như:

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

hy vọng rằng niềng răng sẽ kèm theo _x tôi và _y trong một phạm vi tư nhân, nhưng than ôi, clang++ than phiền nhiều định nghĩa của _x và _y.

Có cách nào đẹp hơn không?

Answer 1

Bạn có thể chuyển tiếp tất cả các chức năng thành viên mà bạn muốn gọi một mẫu helper mà đi qua chúng khi cần thiết:

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

Hàm lazy_compare variadic sẽ đi qua từng hàm một thành viên một khi cần thiết.Trường hợp cơ sở chỉ là true:

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

Và trường hợp đệ quy là để bật tắt các thành viên con trỏ-to-đầu tiên và xem liệu chúng ta có thể dừng lại ở một rằng:

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

tôi sẽ dính vào một thoải mái so sánh phương pháp, được viết theo cách đó:

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

Bằng cách đó nó sẽ trả về với dấu hiệu chính xác ngay sau khi một phương pháp cho kết quả khác nhau và đi xuống đến cuối cùng chỉ trong trường hợp bình đẳng.

Và bạn có thể sử dụng nó trực tiếp trong tất cả các bộ so sánh:

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

Bạn chỉ có thể thực hiện nó như thế này:

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

nó sẽ trở lại ngay khi một trong các phương pháp đánh giá là đúng, mà không đánh giá các phương pháp khác.

Answer 4

Đây là đối tượng so sánh lười biếng. Nó chứa một số tùy ý callable F, và nó gọi nó khi bạn gọi cmp(lhs, rhs) trên một cặp lazy_comp_f<?> đối tượng, lưu trữ các kết quả, và cho bạn biết ai thắng:

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

Đây là một chức năng mẫu máy helper mà không khấu trừ loại F:

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

Đây là một mối quan hệ lười biếng. Phải mất một loạt các chức năng được sử dụng để sản xuất các mặt hàng đắt tiền:

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

Đây là số cmp cơ bản của chúng tôi. Nó sử dụng < và tạo ra một hoạt động hợp lý hiệu quả cmp. tra cứu ADL địa phương có thể tìm thấy một tình trạng quá tải tốt hơn cho trường hợp chúng ta có thể làm điều đó tốt hơn:

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

Bây giờ một nỗ lực để cho phép cmp của các bộ. Hai người giúp đỡ:

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

và chúng ta gọi là helper, với bảo vệ chống lại số chưa từng có của LHS/args 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); 
} 

bây giờ vấn đề là chỉ cần cung cấp callables!

Bên class thực hiện như sau:

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

và chúng tôi đang thực hiện?

Lưu ý rằng giải pháp này hoạt động đệ quy. Bất kỳ ai ghi đè cmp sẽ nhận được phiên bản tối ưu, bất kỳ ai không nhận được một số < có trụ sở. Nếu một số cấu trúc con có lazy dựa trên cmp, nó sẽ được gọi.

Trong C++ 14, thao tác này được thực hiện với chi phí tẩy xóa loại thấp. Trong C++ 11, một số phân bổ vô nghĩa (đối với loại tẩy xoá) được thực hiện - chúng có thể được thực hiện nhanh hơn với cách tiếp cận giống như đại biểu (trọng lượng nhẹ std::function s) hoặc các vi dữ liệu khác.

Một số tính năng C++ 14 được sử dụng. Chúng dễ thực hiện trong C++ 11 (ngoài loại trả về auto, nơi tôi cung cấp giải pháp thay thế).