Cómo usar std :: sort con un vector de estructuras y función de comparación?

Question

Gracias por un solution in C, ahora me gustaría lograr esto en C++ usando std :: sort y el vector:

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

vector<pkt> wektor; llenado usando push_back(); función de comparación:

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 

¿Qué hay para corregir? Cómo usar correctamente std :: sort en ese caso?

Answer 1

std::sort toma una función de comparación diferente de la utilizada en qsort. En lugar de devolver -1, 0 o 1, se espera que esta función devuelva un valor bool que indica si el primer elemento es menor que el segundo.

Tiene dos posibilidades: implementar operator < para sus objetos; en ese caso, la invocación predeterminada sort sin un tercer argumento funcionará; o puede reescribir su función anterior para lograr lo mismo.

Tenga en cuenta que tiene que escribir fuertemente en los argumentos.

Además, es bueno no usar ninguna función aquí. En cambio, use un objeto de función. Estos se benefician de la creación de líneas.

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

En C++, puede utilizar palabras funcionales como boost::bind el que hacer este trabajo muy bien:

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

Si necesita hacer esto muchas veces, también se puede resolver el problema haciendo un objeto función que acepta punteros de miembro y hace el tipo. Puede reutilizarlo para cualquier tipo de objeto y miembros. Primero cómo lo usa:

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

Aquí está el código de make_cmp. Se sienten libres para hacerla pedazos (usando 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

Con la solución de Konrad C++ 0x y lambdas se parece a esto:

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