Làm thế nào để sử dụng std :: sắp xếp với một vector cấu trúc và so sánh chức năng?

Question

Cám ơn một solution in C, bây giờ tôi muốn đạt được điều này trong C++ sử dụng std :: sắp xếp và vector:

typedef struct 
{ 
    double x; 
    double y; 
    double alfa; 
} pkt; 

vector<pkt> wektor; lấp đầy bằng push_back(); so sánh hàm:

int porownaj(const void *p_a, const void *p_b) 
{ 
    pkt *pkt_a = (pkt *) p_a; 
    pkt *pkt_b = (pkt *) p_b; 

    if (pkt_a->alfa > pkt_b->alfa) return 1; 
    if (pkt_a->alfa < pkt_b->alfa) return -1; 

    if (pkt_a->x > pkt_b->x) return 1; 
    if (pkt_a->x < pkt_b->x) return -1; 

    return 0; 
} 

sort(wektor.begin(), wektor.end(), porownaj); // this makes loads of errors on compile time 

Điều gì là đúng? Làm thế nào để sử dụng đúng std :: sắp xếp trong trường hợp đó?

Answer 1

std::sort có chức năng so sánh khác với chức năng được sử dụng trong qsort. Thay vì trả về -1, 0 hoặc 1, hàm này được mong đợi trả về giá trị bool cho biết phần tử đầu tiên có nhỏ hơn giá trị thứ hai hay không.

Bạn có hai tiện ích: triển khai operator < cho các đối tượng của bạn; trong trường hợp đó, yêu cầu sort mặc định không có đối số thứ ba sẽ hoạt động; hoặc bạn có thể viết lại hàm trên để hoàn thành cùng một điều.

Lưu ý rằng bạn phải sử dụng gõ mạnh mẽ trong các đối số.

Ngoài ra, tốt nhất là không nên sử dụng chức năng ở đây. Thay vào đó, hãy sử dụng một đối tượng hàm. Những lợi ích từ nội tuyến.

struct pkt_less { 
    bool operator()(pkt const& a, pkt const& b) const { 
     if (a.alfa < b.alfa) return true; 
     if (a.alfa > b.alfa) return false; 

     if (a.x < b.x) return true; 
     if (a.x > b.x) return false; 

     return false; 
    } 
}; 

// Usage: 

sort(wektor.begin(), wektor.end(), pkt_less()); 

Answer 2

Trong C++, bạn có thể sử dụng functors như boost::bind mà làm công việc này độc đáo:

#include <vector> 
#include <algorithm> 

struct pkt { 
    double x; 
    double y; 
    double alfa; 
    pkt(double x, double y, double alfa) 
     :x(x), y(y), alfa(alfa) { } 
}; 

int main() { 
    std::vector<pkt> p; 
    p.push_back(pkt(10., 0., 20.)); 
    p.push_back(pkt(10, 0., 30.)); 
    p.push_back(pkt(5., 0., 40.)); 

    std::sort(p.begin(), p.end(), 
       boost::bind(&pkt::alfa, _1) < boost::bind(&pkt::alfa, _2) || 
       boost::bind(&pkt::alfa, _1) == boost::bind(&pkt::alfa, _2) && 
       boost::bind(&pkt::x, _1) < boost::bind(&pkt::x, _2)); 
} 

Nếu bạn cần phải làm điều này nhiều lần, bạn cũng có thể giải quyết vấn đề bằng cách làm cho một đối tượng chức năng mà chấp nhận con trỏ thành viên và thực hiện sắp xếp. Bạn có thể tái sử dụng nó cho bất kỳ loại đối tượng và thành viên. Đầu tiên bạn sử dụng nó như thế nào:

int main() { 
    /* sorting a vector of pkt */ 
    std::vector<pkt> p; 
    p.push_back(pkt(10., 0., 20.)); 
    p.push_back(pkt(5., 0., 40.)); 

    std::sort(p.begin(), p.end(), make_cmp(&pkt::x, &pkt::y)); 
} 

Đây là mã cho make_cmp. Cảm thấy tự do để rip nó (sử dụng boost::preprocessor):

#include <boost/preprocessor/repetition.hpp> 
#include <boost/preprocessor/facilities/empty.hpp> 

// tweak this to increase the maximal field count 
#define CMP_MAX 10 

#define TYPEDEF_print(z, n, unused) typedef M##n T::* m##n##_type; 
#define MEMBER_print(z, n, unused) m##n##_type m##n; 
#define CTORPARAMS_print(z, n, unused) m##n##_type m##n 
#define CTORINIT_print(z, n, unused) m##n(m##n) 

#define CMPIF_print(z, n, unused)    \ 
    if ((t0.*m##n) < (t1.*m##n)) return true; \ 
    if ((t0.*m##n) > (t1.*m##n)) return false; \ 

#define PARAM_print(z, n, unused) M##n T::* m##n 

#define CMP_functor(z, n, unused)          \ 
    template <typename T            \ 
       BOOST_PP_ENUM_TRAILING_PARAMS(n, typename M)>    \ 
    struct cmp##n {              \ 
     BOOST_PP_REPEAT(n, TYPEDEF_print, ~)       \ 
     BOOST_PP_REPEAT(n, MEMBER_print, ~)        \ 
     cmp##n(BOOST_PP_ENUM(n, CTORPARAMS_print, ~))     \ 
      BOOST_PP_IF(n, :, BOOST_PP_EMPTY())       \ 
      BOOST_PP_ENUM(n, CTORINIT_print, ~) { }      \ 
                     \ 
     bool operator()(T const& t0, T const& t1) const {    \ 
      BOOST_PP_REPEAT(n, CMPIF_print, ~)       \ 
      return false;            \ 
     }                \ 
    };                 \ 
                     \ 
    template<typename T             \ 
      BOOST_PP_ENUM_TRAILING_PARAMS(n, typename M)>    \ 
    cmp##n<T BOOST_PP_ENUM_TRAILING_PARAMS(n, M)>      \ 
     make_cmp(BOOST_PP_ENUM(n, PARAM_print, ~))      \ 
    {                 \ 
     return cmp##n<T BOOST_PP_ENUM_TRAILING_PARAMS(n, M)>(   \ 
      BOOST_PP_ENUM_PARAMS(n, m));        \ 
    } 

BOOST_PP_REPEAT(CMP_MAX, CMP_functor, ~) 


#undef TYPEDEF_print 
#undef MEMBER_print 
#undef CTORPARAMS_print 
#undef CTORINIT_print 
#undef CMPIF_print 
#undef PARAM_print 
#undef CMP_functor 

Answer 3

Với giải pháp C++ 0x và lambdas Konrad trông như thế này:

sort(wektor.begin(), wektor.end(), [](pkt const& a, pkt const& b) 
{ 
    if (a.alfa < b.alfa) return true; 
    if (a.alfa > b.alfa) return false; 

    if (a.x < b.x) return true; 
    if (a.x > b.x) return false; 

    return false; 
});