How to use std::sort with a vector of structures and compare function?

Question

Thanks for a solution in C, now I would like to achieve this in C++ using std::sort and vector:

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

vector< pkt > wektor; filled up using push_back(); compare function:

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

What is to correct? How to use properly std::sort in that case?

Solution 1

std::sort takes a different compare function from that used in qsort. Instead of returning –1, 0 or 1, this function is expected to return a bool value indicating whether the first element is less than the second.

You have two possibilites: implement operator < for your objects; in that case, the default sort invocation without a third argument will work; or you can rewrite your above function to accomplish the same thing.

Notice that you have to use strong typing in the arguments.

Additionally, it's good not to use a function here at all. Instead, use a function object. These benefit from inlining.

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

Solution 2

In C++, you can use functors like boost::bind which do this job nicely:

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

If you need to do this many times, you can also solve the problem by making a function object which accepts member pointers and does the sort. You can reuse it for any kind of object and members. First how you use it:

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

Here is the code for make_cmp. Feel free to rip it (using 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

Solution 3

With C++0x and lambdas Konrad's solution looks like this:

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

Comments

[Johannes Schaub - litb]

Dave, the reason is that functors can be inlined, since the functors type will tell the compiler which function is called at compile time. using function pointers, the compiler only knows this at runtime, and this it cannot inline.

[Martin York]

@onebyone.livejournal.com: Not true. A function pointer can NOT be inlined. The compiler is not allowed to make that optimization. (Though a pointer is a functor).

[Martin York]

@Konrad Rudolph: Your method does not do the same as the original: The final return should not compare y but just return false.

[Johannes Schaub - litb]

some say a pointer to a normal function is not a functor, and say only class types having overloaded op() are functors. but function pointers are definitely function objects.

[Johannes Schaub - litb]

onebyone. see: bool(*)(T const&, T const&) may that be the type the compiler sees. There are infinitely functions having that type that all do different things. But if you have U with U being a classtype overloading op(), there is only one overloading resolution will be able to figure out.

[Johannes Schaub - litb]

(assuming the usual properties of a function object. i.e not being polymorph)

[josesuero]

A function ptr can be used as when a functor is expected, and depending on your definition, we can call it a functor if you like, but it suffers from the problem that the function it represents is not known at compile-time, making it hard to inline. A class overloading op() avoids this problem.

[Zan Lynx]

It seems crazy to me that C is not allowed to inline a function pointer. A constant pointer such as &compare can never be any function other than compare. So why not inline it?

[Johannes Schaub - litb]

Zan. you misunderstand it. the point is, in the std::sort function, the function doesn't know that it's calling compare. it only knows it's calling some function. if std::sort can be inlined, then indeed the function itself could be inlined too. but it requires a good compiler to figure that out.

[Steve Jessop]

@litb, @Martin York - you guys need to figure out whether the compiler is permitted to inline &compare or not: litb says it's allowed but is too dumb, Martin says it's not allowed because it's a function pointer. tbh, I thought plain "compare" was a function pointer, and obviously that can inline.

[Johannes Schaub - litb]

template<void(*fptr)()> void call() { fptr(); } // can be inlined just as well as the class type overloading op() version.

[Johannes Schaub - litb]

onebyone, this is also why functors should not be polymorph. you should get the template-book (C++ Templates - The Complete Guide). Thy explain the matter there. The compiler is not forbidden to inline calls by function pointers - by no means.