Как использовать std :: sort с вектором структур и функцией сравнения?

Question

Спасибо за solution in C, теперь я хотел бы, чтобы добиться этого в C++ с использованием зОго :: сортировки и вектора:

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

vector<pkt> wektor; заполняется с использованием push_back(); функция сравнения:

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 

Что можно исправить? Как правильно использовать std :: sort в этом случае?

Answer 1

std::sort принимает другую функцию сравнения от той, которая используется в qsort. Вместо возврата -1, 0 или 1 ожидается, что эта функция вернет значение bool, указывающее, является ли первый элемент меньше второго.

У вас есть два варианта: реализовать operator < для ваших объектов; в этом случае будет работать вызов по умолчанию sort без третьего аргумента; или вы можете переписать свою вышеприведенную функцию, чтобы выполнить ту же самую вещь.

Обратите внимание, что вам необходимо использовать сильную типизацию в аргументах.

Кроме того, хорошо не использовать функцию здесь вообще. Вместо этого используйте объект функции. Эти преимущества от встраивания.

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

В C++, вы можете использовать функторы как boost::bind, которые делают эту работу хорошо:

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

Если вам нужно сделать это много раз, вы можете решить эту проблему, сделав объект функции, которая принимает указатели на элементы и выполняет сортировку. Вы можете повторно использовать его для любого объекта и членов. Сначала как вы его используете:

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

Здесь код для make_cmp. Вы можете копировать его (с помощью 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

С решением C++ 0x и лямбды Конрада выглядит следующим образом:

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