Template magic for sorting

[mark]

I'm looking for a sort function that can sort standard library
containers based on member fields.

struct A {
int v1;
std::string v2;
};

std::vector<A> v;
bool ascending = true;

I would like to perform sorting like this:
my_sort(v, ascending, A::v2);

There must be some nice C++11 magic that can do that...

[SG]

Anything wrong with just using std::sort and a lambda function?

std::sort(v.begin(), v.end(), [](A const& l, A const& r) {
return l.v2 < r.v2;
});

Using the Boost.Bind library, this could be:

std::sort(v.begin(), v.end(),
bind(&A::v2, _1) < bind(&A::v2, _2)
);

But you could also write your own generic functor. Something like this
perhaps:

template<class T>
struct member_less_than;

template<class C, class T>
struct member_less_than<T C::*> {
T C::*member_pointer;

bool operator()(C const& a, C const& b) const {
return (a.*member_pointer) < (b.*member_pointer);
}
};

template<class C, class T>
member_less_than<T C::*> make_mlt(T C::*member_ptr) {
member_less_than<T C::*> result = { member_ptr };
return result;
}

:::

std::sort(v.begin(), v.end(), make_mlk(&A::v2));

Another option would be to move the member pointer out of the struct
and turn it into a template parameter (yes, that's actually doable
and might be preferable).

All the code you see here is untested and probably buggy but should
work "in principle". In particular, I'm not sure if I got the member
pointer syntax right because I hardly use member pointers.

Cheers!
SG

[bartekltg]

On 06.09.2015 13:08, mark wrote:
> I'm looking for a sort function that can sort standard library
> containers based on member fields.
>
> struct A {
> int v1;
> std::string v2;
> };
>
> std::vector<A> v;
> bool ascending = true;
>
> I would like to perform sorting like this:
> my_sort(v, ascending, A::v2);

Old C++ magic was enough:

The first is a very simple example, but it looks
at values ascending and field_index every time
it compare two "A" object.
The second comparator should have this optimized out
by compilator. Still, there are better ways to do it
(for example, there you have tu maintain a class, enum,
and body od comparator, and keep it consistent. Idea
described by SG, with pointers to members may be much
better for larger classes/structures) but with more
'template magic'.


#include <iostream>
#include <algorithm>
#include <vector>


using namespace std;

struct A {
int v1;
std::string v2;

A(int number, std::string string):v1(number),v2(string) {} ;

};

std::vector<A> v;
bool ascending = true;

enum field
{
V1 = 1,
V2 = 2
};


struct A_comparator
{
bool ascending;
int field_index;

A_comparator (bool Ascending, int Field_index):
ascending(Ascending), field_index(Field_index) {};
bool operator () (const A &x, const A &y)
{
if (ascending)
{
if (field_index==1)
return x.v1<y.v1;
else
return x.v2<y.v2;
}else
{
if (field_index==1)
return x.v1>y.v1;
else
return x.v2>y.v2;
}
}
};

template <bool ascending, field field_index>
struct A_comparator2
{
A_comparator2 () {};
bool operator () (const A &x, const A &y)
{
if (ascending)
{
if (field_index==V1)
return x.v1<y.v1;
else
return x.v2<y.v2;
}else
{
if (field_index==V1)
return x.v1>y.v1;
else
return x.v2>y.v2;
}
}
};



int main()
{
std::vector<A> v;

v.push_back(A(70,"70"));
v.push_back(A(30,"93"));
v.push_back(A(40,"67"));

bool ascending = true;


sort (v.begin(), v.end(), A_comparator(true,2));

sort (v.begin(), v.end(), A_comparator2<true,V1>());


return 0;
}


bartekltg

[mark]

Thanks for the replies. I figured out the template magic.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

template<class container_t_, class el_t_, class field_t_>
void my_sort(container_t_& cnt, field_t_ el_t_::* field, bool asc) {
std::sort(cnt.begin(), cnt.end(), [field,asc](el_t_ a, el_t_ b) {
return asc ? a.*field < b.*field : a.*field > b.*field;
});

}

struct A {
int v1;
std::string v2;
};

void printVec(const std::vector<A>& v) {
for(auto& val : v) std::cout << val.v1 << " ";
std::cout << std::endl;
}

int main() {
std::vector<A> v = { {2, "2"}, {3, "3"}, {1, "1"} };
my_sort(v, &A::v2, true);
printVec(v);
my_sort(v, &A::v1, false);
printVec(v);
}

[mark]

On 2015-09-06 19:12, mark wrote:
> Thanks for the replies. I figured out the template magic.
>

> template<class container_t_, class el_t_, class field_t_>
> void my_sort(container_t_& cnt, field_t_ el_t_::* field, bool asc) {
> std::sort(cnt.begin(), cnt.end(), [field,asc](el_t_ a, el_t_ b) {
> return asc ? a.*field < b.*field : a.*field > b.*field;
> });
> }

GCC in C++14 mode can do some nice auto magic (but it's apparently part
of concepts lite and not in the standard):

void my_sort(auto& cnt, auto field, bool asc) {
std::sort(cnt.begin(), cnt.end(), [field,asc](auto a, auto b) {

return asc ? a.*field < b.*field : a.*field > b.*field;
});
}

This should be valid C++14:

auto my_sort = [](auto& cnt, auto field, bool asc) {
std::sort(cnt.begin(), cnt.end(), [field,asc](auto a, auto b) {

};

[SG]

Am Sonntag, 6. September 2015 19:13:17 UTC+2 schrieb mark:
>
> template<class container_t_, class el_t_, class field_t_>
> void my_sort(container_t_& cnt, field_t_ el_t_::* field, bool asc) {
> std::sort(cnt.begin(), cnt.end(), [field,asc](el_t_ a, el_t_ b) {
> return asc ? a.*field < b.*field : a.*field > b.*field;
> });
> }

A couple of suggestions:

(1) Since you are now generic over the kind of container to sort, you
should probably use the non-member begin/end functions to be a
little more flexible. This way, the function will work for raw
arrays as well, for example.

(2) The signature of your lambda function is suboptimal because you
take its arguments by value which will produce unnecessary copies
which is quite costly for non-trivial types like std::string.

(3) You can avoid the "asc?:" branch by moving the check outside of
the sort function. There should not be a big difference if your
CPU does branch prediction.

So, after some tweaking I get:

template<class Cont, class Clazz, class T, class Func>
void sort_by_member_func(Cont& cnt, T Clazz::* field, Func func) {
using std::begin; // With these we can avoid the std:: later
using std::end; // which then also allows ADL to kick in.
std::sort(begin(cnt), end(cnt),
[field, &func](T const& a, T const& b) {
return func(a.*field, b.*field);
}
);
}

template<class Cont, class Clazz, class T>
void sort_by_member(Cont& cnt, T Clazz::* field, bool asc) {
if (asc) {
sort_by_member_func(cnt, field, std::less<T>());
} else {
sort_by_member_func(cnt, field, std::greater<T>());
}
}

Cheers!
SG

[mark]

On 2015-09-06 19:56, SG wrote:

Thanks for your comments.

> (2) The signature of your lambda function is suboptimal because you
> take its arguments by value which will produce unnecessary copies
> which is quite costly for non-trivial types like std::string.

You are right. The 'real' code actually has pointer containers, so it
doesn't matter there.

> (3) You can avoid the "asc?:" branch by moving the check outside of
> the sort function. There should not be a big difference if your
> CPU does branch prediction.

I had too much compiler faith and was expecting the test to be pulled
out. I did a test and it does make a small difference on both GCC and VC++.