Hopefully all C++ developers have by now learned about the std::tie()-idiom.
std::tie() creates a std::tuple<> with references to the parameters, and the comparison operators for std::tuple<> does its work memberwise, creating a lexicographical compare. It's all done inline and is as efficient as can be.
But what if you want different ordering relations at different times? Take as an example the classic employee record, where you may some times want to sort employees by name, some times by age, some times by employee number, some times by years employed, some times by... you get the idea.
You can, of course, write comparator classes for each, implementing each function with std::tie() as above, but it's still a repetitive tedium. Isn't that what computers are good at?
What if we could create a comparator by listing the ordering relation and which members, like this?
Pointers to members are an old obscure construct in C++, so rarely used that they deserve a short intro before continuing. &S::a is a pointer to the member a in a struct S. It is used to access the member a in any instance of struct S. A short example:
Above, the type of ptr is int S::*, which means that it can be reassigned to any member in struct S that is of type int. That's why the assignment on line 16 works, both members a and b are of type int.
Now it is not a far stretch of the imagination to see that with a number of pointers to members, we can access the member variables to compare in the desired order. For example, pointers to members in a std::tuple<> can be used like this:
This doesn't look like much of an improvement, but it's a start to get the compiler engaged in generating code for us. Time to switch to templates.
Above, Ms is a template parameter pack. At this stage we know nothing about it, except that it is 0 or more types. The member variable ms holds values of all such types, as provided by the constructor. This is all that is known currently. The previous example also showed how the members of a std::tuple<...> can be accessed, but this requires knowledge at compile time of their position in the std::tuple<...>.
All that is needed to reveal the magic is available, but only indirectly. A first start is operator sizeof...(Ms), which will tell, as a constexpr which can be used as a template parameter, how many elements the parameter pack, and thus the std::tuple<Ms...>, holds.
C++14 introduced in the standard library a set of templates that are really handy for this. Two nearly indispensable tools are std::index_sequence<Ns...> and its helper std::make_index_sequence<N>.
These two takes us almost all the way to the magic.
Disappointed? You shouldn't be. idxs is a type std::index_sequence<...> that holds all indexes, from 0 up until, but not including, the number of elements in the std::tuple<Ms...>, in sequence. This is all that is required to pick the members and do the comparison. It is, however, necessary to go through the extra indirection. The compare function then becomes:
Wait, what? Is that it? Yes, it is. Although perhaps a little explanation is useful.
Earlier I mentioned that std::make_index_sequence<N> generates a sequence of all indexes from 0 up until, but not including N. Those are the Ns parameter pack above. The construction lh.*std::get<Ns>(ts)... is repeated for every index is Ns, so the function effectively becomes (provided the parameter pack size is 3):
This is what's wanted, isn't it?
Getting to the end goal is more or less trivial. A function to create the comparator object, and use a compare argument instead of always using operator<.
Using inheritance for the comparator is just to enable the empty base class optimization, since there is no way as written to provide a comparator object that may hold state, and most state less comparators have no data, so it reduces the size of the comparator object slightly.
What about performance then? After all, this is C++ and we care about performance, and also everybody knows that this type of encapsulated abstraction and templates cause bloat and kills the optimizer? Or?
Here's a short example function, compiled in a separate translation unit, so that it can be followed.
When compiled with g++ 5.2 for x86_64 and optimized with -O3, the resulting code is:
.file "sorts.cpp"The entire loop is between .L13 and .L3, and the two element comparison is between .L6 and .L8. All overhead of indirection is gone. Compilers are good at this.
.type _Z9is_sortedRKSt6vectorI1SSaIS0_EE, @function
movq 8(%rdi), %r8
movq (%rdi), %rdx
cmpq %rdx, %r8
leaq 12(%rdx), %rax
cmpq %rax, %r8
movl 16(%rdx), %esi
movl 4(%rdx), %edx
cmpl %esi, %edx
movl %ecx, %esi
cmpl %edx, %esi
movl -12(%rax), %edi
cmpl %edi, (%rax)
addq $12, %rax
cmpq %rax, %r8
movl 4(%rax), %ecx
movl %esi, %edx
cmpl %esi, %ecx
cmpq %rax, %r8
movl $1, %eax
.size _Z9is_sortedRKSt6vectorI1SSaIS0_EE, .-_Z9is_sortedRKSt6vectorI1SSaIS0_EE
.ident "GCC: (Ubuntu 5.2.1-22ubuntu2) 5.2.1 20151010"
I thought this was cool and just wanted to share. Work can be made to allow stateful comparators, and to ensure more helpful compiler error messages in case of usage mistakes.