C++: Supplying a templated compare function to std::sort

Question

Suppose I want to get std::sort to sort a vector of pointers to int's, based on the value of the int's the pointers point to. Ignore the obvious performance issue there. Simple huh? Make a function:

bool sort_helper(const int *a, const int *b) { return *a < *b; }

and supply to the std::sort.

Now, if we also want to do the same thing with a vector of pointers to large objects. The same thing applies: first we define a < operator in the object, then make a function along the following lines:

bool sort_helper(const ob_type *a, const ob_type *b) { return *a < *b; }

or whatever, supply that to std::sort.

Now, and this is where it gets tricky: what if we want to sort a vector of pointers to any type, with any arbitrary compare function (we make the assumption that whatever type we use that function with, will be able to work with it)- supplying a template version of the sort_helper function above is easy:

template <class ob_type> bool sort_helper(const ob_type *a, const ob_type *b) { return *a < *b; }

However, supplying an arbitrary compare function is harder: Something like this-

template <typename comparison_function, class ob_type> bool sort_template_helper(const ob_type *a, const ob_type *b) { return comparison_function(*a, *b); } template <typename comparison_function, class iterator_type> void t_sort(const iterator_type &begin, const iterator_type &end, comparison_function compare) { std::sort(begin, end, sort_template_helper<compare>); }

is what I'd like to do, but doing this:

bool less_than(const int a, const int b) { return a < b; } void do_stuff() { t_sort(ipoint_vector.begin(), ipoint_vector.end(), sort_template_helper<less_than>); }

Doesn't work. How can I sort a vector of pointers to a known type, by the value of the objects pointed to, using an arbitrary comparison function, supplied to std::sort? Assume that the test case I am presenting here is an insanely simplified version of the actual scenario, and that there are valid reasons for wanting to do things this way, that would take too long to go into and distract from the problem.

[EDIT: for various reasons, am looking for a solution that also works in C++03 - Thanks to Nir for his C++14 answer tho']

Nir Friedman · Accepted Answer · 2017-05-10 11:04:26Z

Basically what you need is a higher order function: a function that returns a function.

template <class T, class F> auto make_pointee_comparison(F f) { return [=] (T const * l, T const * r) { return f(*l, *r); }; }

Here I have T be explicitly specified; you might be able with extra programming to deduce T but it can be quite tricky to make it work correctly for both function objects and function pointers.

Edit: to make this work in C++03, we have to obviously remove our usage of lambdas. Converting a lambda to a function object is pretty straightforward though. We declare a struct:

template <class F> struct PointeeComparisonHelper { PointeeComparisonHelper(F f) : m_f(f) {} template <class T> bool operator()(T const * l, T const * r) const { return m_f(*l, *r); } F m_f; }; template <class F> PointeeComparisonHelper<F> make_pointee_comparison(F f) { return PointeeComparisonHelper<F>(f); }

Edit: I templated the call operator in the 03 example; to do this with a lambda you need C++14, not just 11. If you are using the 03 form, then you don't need to explicitly specify <int> to make_pointee_comparison.

Usage:

auto c = make_pointee_comparison<int>([] (int x, int y) { return x < y; }); int x = 5; int y = 6; std::cerr << c(&x, &y) << c(&y, &x);

Which prints 10 (true false). Note that this takes a function object rather than a function pointer, which is more idiomatic in C++. But you can pass a function pointer too:

bool compare(int x, int y) { return x > y; } auto c2 = make_pointee_comparison<int>(&compare); std::cerr << c2(&x, &y) << c2(&y, &x);

You could then write your function like this:

template <typename comparison_function, class iterator_type> void t_sort(const iterator_type &begin, const iterator_type &end, comparison_function compare) { using deref_type = const decltype(*begin); std::sort(begin, end, make_pointee_comparison<deref_type>(compare)); }

Thanks! Have tested it, and, amazingly, it works! is there an equivalent for C++03?
@metamorphosis ah shit :-). We should probably start encouraging people to use the 03 tag, I think people sort of assume that 11 is the default. Okay, is it alright if I give a sketch of the 03 solution without nearly as much detail?
Absolutely. For anyone reading, the first solution above is C++14 and above only (otherwise deduced return type won't work).
Don't worry, unless you've got something to add I think W.T got the 03 side solution. But thank you. Upvoted you both.

W.F. · Accepted Answer · 2017-05-10 11:25:04Z

You cannot pass function template pointer in c++, what you can do is to create functor with operator() template (something very similar to lambda with auto parameters):

#include <algorithm> #include <vector> #include <cassert> struct less { template <class T> bool operator()(T first, T second) const { return first < second; } }; template <class Cmp> struct cmp_ptr { Cmp cmp; cmp_ptr(Cmp cmp):cmp(cmp) { } cmp_ptr() { } template <class T> bool operator()(T first, T second) const { return cmp(*first, *second); } }; template <class Iter, class Cmp> bool is_sorted(Iter beg, Iter end, Cmp cmp) { Iter prev = beg; Iter next = beg; for (next++; next != end; prev++, next++) { if (cmp(*next, *prev)) { return false; } } return true; } int main() { std::vector<int*> v; v.push_back(new int(10)); v.push_back(new int(1)); v.push_back(new int(5)); v.push_back(new int(7)); v.push_back(new int(3)); v.push_back(new int(2)); std::sort(v.begin(), v.end(), cmp_ptr<less>()); assert(::is_sorted(v.begin(), v.end(), cmp_ptr<less>())); }

[live demo]

Remember that operator must have const qualifier to make caller to be able to access to it from temporary object.

Doesn't actually answer the question, which was how to call sort on an arbitrary type using an arbitrary comparison function to sort pointers via the elements they point to - your solution assumes a templated comparison function which caters specifically to this scenario, does not allow for use of an arbitrary comparison function designed to work with the element rather than the element pointer.
@metamorphosis I mean - why bother to specify collection element type explicitly when it can be easily deduced...
@metamorphosis This answer is incorrect; it doesn't work for stateful functors which are completely legal things to use as comparators. Unlike, say, a certain other answer cough which does this correctly.
@NirFriedman you haven't used the mutual lambda neither... ;)

Andrei R. · Accepted Answer · 2017-05-10 06:33:02Z

guess you are looking for something like this:

template <typename comparison_function, class iterator_type> void sort_deref(const iterator_type &begin, const iterator_type &end, comparison_function compare) { std::sort(begin, end, [compare](auto *a, auto *b) { compare(*a,*b); }); } // example usage: sort_deref(std::begin(container), std::end(container), std::less<>());

You are trying to pass value of type comparison_function to a template expecting type.

Collectives™ on Stack Overflow

C++: Supplying a templated compare function to std::sort

3 Answers 3

4 Comments

9 Comments

Comments

Linked

Hot Network Questions