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

Question

Спасибо за решение в C , Теперь я хотел бы добиться этого в C ++, используя std :: sort и vector:

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