# Selection sorting a type list (compile-time)

This question has the tuple_selection_sort<> template that sorts the variadic template of a tuple using a comparator (any template taking two types that has a value data member of type bool).

If the following tuple...

// sizeof:    1,   4,    1,      8,    1,     4
std::tuple<char, int, char, double, char, float>


Is sorted with a comparator that sorts based on type size (descending), we would get:

// sizeof:      8,   4,     4,    1,    1,    1
std::tuple<double, int, float, char, char, char>


## Refresher on the simple selection sort

This is a simple implementation of a selection sort on which the template-meta-programming version is based:

template <class T, class Comparator>
void selection_sort( std::vector<T>& v, Comparator c )
{
for ( std::vector<T>::size_type i{ 0 }, sz{ v.size() }; i < sz; ++i )
{
for ( std::vector<T>::size_type j{ i + 1 }; j < sz; ++j )
{
if ( c( v[ i ], v[ j ] ) )
{
using std::swap;
swap( v[ i ], v[ j ] );
}
}
}
}


Selection sort runs in $O(n^2)$. However, it was chosen for very simple reasons:

• Simple to implement.
• Common usage instances of std::tuple<> do not have many types. Thus, compile-time performance shouldn't become an issue.

## Implementation

Swapping two types inside a std::tuple<>:

#include <tuple>
#include <utility>

// swap types at index i and index j in the template argument tuple
template <std::size_t i, std::size_t j, class Tuple>
class tuple_element_swap
{
template <class IndexSequence>
struct tuple_element_swap_impl;

template <std::size_t... indices>
struct tuple_element_swap_impl<std::index_sequence<indices...>>
{
using type = std::tuple
<
std::tuple_element_t
<
indices != i && indices != j ? indices : indices == i ? j : i, Tuple
>...
>;
};

public:
using type = typename tuple_element_swap_impl
<
std::make_index_sequence<std::tuple_size<Tuple>::value>
>::type;
};


The selection sort template:

// selection sort template argument tuple's variadic template's types
template <template <class, class> class Comparator, class Tuple>
class tuple_selection_sort
{
// selection sort's "loop"
template <std::size_t i, std::size_t j, std::size_t tuple_size, class LoopTuple>
struct tuple_selection_sort_impl
{
// this is done until we have compared every element in the type list
using tuple_type = std::conditional_t
<
Comparator
<
std::tuple_element_t<i, LoopTuple>,
std::tuple_element_t<j, LoopTuple>
>::value,
typename tuple_element_swap<i, j, LoopTuple>::type, // true: swap(i, j)
LoopTuple                                           // false: do nothing
>;

using type = typename tuple_selection_sort_impl // recurse until j == tuple_size
<
i, j + 1, tuple_size, tuple_type // using the modified tuple
>::type;
};

template <std::size_t i, std::size_t tuple_size, class LoopTuple>
struct tuple_selection_sort_impl<i, tuple_size, tuple_size, LoopTuple>
{
// once j == tuple_size, we increment i and start j at i + 1 and recurse
using type = typename tuple_selection_sort_impl
<
i + 1, i + 2, tuple_size, LoopTuple
>::type;
};

template <std::size_t j, std::size_t tuple_size, class LoopTuple>
struct tuple_selection_sort_impl<tuple_size, j, tuple_size, LoopTuple>
{
// once i == tuple_size, we know that every element has been compared
using type = LoopTuple;
};

public:
using type = typename tuple_selection_sort_impl
<
0, 1, std::tuple_size<Tuple>::value, Tuple
>::type;
};


## Sample usage

template <class T, class U>
struct descending
: std::conditional_t<( sizeof( U ) > sizeof( T ) ), std::true_type, std::false_type>
{};

int main()
{
using input_tuple_t = std::tuple<char, int, char, double, char, float>;
using expected_tuple_t = std::tuple<double, int, float, char, char, char>;
using result_tuple_t = tuple_selection_sort<descending, input_tuple_t>::type;

static_assert( std::is_same<expected_tuple_t, result_tuple_t>::value , "!" );
}

• So what's the problem/question? Does it work? Is this a stable sort? (do you want a stable sort?) What are use cases? – Walter Jun 6 '16 at 19:43
• @Walter I put down a sample program, so yes, it works. It doesn't matter if it's stable for the end goal. The use case is as follows: sizeof( std::tuple<char, int, char> == 12, but sizeof( std::tuple<int, char, char> ) is 8. Thus sorting the types in descending order saves memory. – user2296177 Jun 7 '16 at 0:31
• @Walter I plan on using this to provider some sort of tuple_wrapper<> to keep memory usage down while maintaining usage as if the types were unsorted. – user2296177 Jun 7 '16 at 1:11
• The stability of the sort may matter if there are types with the same size – Incomputable Jun 8 '16 at 19:48
• Which compiler was used when writing the tuple_selection_sort<> and supporting structs? I compiled the code with MS-VS 14 and MS-VS 17 and received error C1001. – Curt M Aug 23 '18 at 2:48

I recommend a naming style that uses CamelCase for template parameters and snake_case (only) for plain old variables and functions, so that the reader can tell at a glance if something is a template parameter. For example, in the code that follows, you use indices as the name of a parameter pack; where I would name that pack Is (Is being the plural of I, and I being the natural name for a template parameter of type int just as i is the natural name for a plain old variable of type int).

I recommend a whitespace style that is much more compact than what you've got. I think your uncuddled < brackets make reading hard for both the human reader and (I would think) for the IDE. When you write

using type = std::tuple


I (and the IDE?) expect "hey, you're missing a semicolon!" whereas the actual diagnosis is "the line continues on the next source line, with an angle bracket." You wouldn't write

int value = sqrt
(
pow(2, 10)
)+1;


would you? So how is it acceptable to write

using type = typename tuple_element_swap_impl
<
std::make_index_sequence<std::tuple_size<Tuple>::value>
>::type;


?

// swap types at index i and index j in the template argument tuple
template <std::size_t i, std::size_t j, class Tuple>
class tuple_element_swap
{
template <class IndexSequence>
struct tuple_element_swap_impl;

template <std::size_t... indices>
struct tuple_element_swap_impl<std::index_sequence<indices...>>
{
using type = std::tuple
<
std::tuple_element_t
<
indices != i && indices != j ? indices : indices == i ? j : i, Tuple
>...
>;
};

public:
using type = typename tuple_element_swap_impl
<
std::make_index_sequence<std::tuple_size<Tuple>::value>
>::type;
};


Purely by applying my naming and whitespace rules, we get

// swap types at index I and index J in the template argument Tuple
template<size_t I, size_t J, class Tuple>
class tuple_element_swap {
template<class>
struct tuple_element_swap_impl;

template<size_t... Is>
struct tuple_element_swap_impl<std::index_sequence<Is...>> {
using type = std::tuple<
std::tuple_element_t<
Is != I && Is != J ? Is : Is == I ? J : I, Tuple
>...
>;
};

public:
using type = typename tuple_element_swap_impl<
std::make_index_sequence<std::tuple_size<Tuple>::value>
>::type;
};


And we can rewrite the expression Is != I && Is != J ? Is : Is == I ? J : I as simply Is == I ? J : Is == J ? I : Is — which is both cleaner and shorter.

In C++17, you could use std::tuple_size_v<Tuple> in place of std::tuple_size<Tuple>::value. That wouldn't be any more performant — in fact it would be a minor harm to compile-time performance — but it would be a little shorter in terms of readability.

Okay, I've looked at the sort part now, too, a little bit.

I notice that you're using the equivalent of

if (condition) {
return true;
} else {
return false;
}


right here:

template <class T, class U>
struct descending
: std::conditional_t<( sizeof( U ) > sizeof( T ) ), std::true_type, std::false_type>
{};


That can be written more compactly in C++14 as

template<class T, class U>
struct descending : std::bool_constant<sizeof(T) < sizeof(U)> {};


or in C++11 as

template<class T, class U>
struct descending : std::integral_constant<bool, sizeof(T) < sizeof(U)> {};


Notice that your sort uses the comparator backwards! You named the comparator descending, which is correct for what your sort algorithm does; but in reality your comparator is a lifted version of std::less, a.k.a. "ascending" (when passed to std::sort)! You should probably reverse the sense in which your sort algorithm uses the comparator, and then reverse the sense of your comparator. That is,

template<class T, class U>  // analogous to std::less
struct ascending : std::bool_constant<(sizeof(T) < sizeof(U))> {};

template<class T, class U>  // analogous to std::greater
struct descending : std::bool_constant<(sizeof(T) > sizeof(U))> {};


This code screams out at me for SCARY-fication, or what Odin Holmes calls the "Rule of Chiel." Rather than instantiating new struct types for std::conditional<true, int, float>, std::conditional<false, float, double>, and so on, let's just instantiate two concrete types — conditional_<true> and conditional_<false> — and use type aliases for everything else.

template<class T, class U>
struct descending : std::bool_constant<sizeof(T) < sizeof(U)> {};


you'd write

template<bool B>
struct conditional_ {
template<class T, class> using type = T;
};
template<>
struct conditional_<false> {
template<class, class U> using type = U;
};

template<class T, class U>
using descending = conditional_<sizeof(T) < sizeof(U)>;


template <std::size_t i, std::size_t j, std::size_t tuple_size, class LoopTuple>
struct tuple_selection_sort_impl
{
// this is done until we have compared every element in the type list
using tuple_type = std::conditional_t
<
Comparator
<
std::tuple_element_t<i, LoopTuple>,
std::tuple_element_t<j, LoopTuple>
>::value,
typename tuple_element_swap<i, j, LoopTuple>::type, // true: swap(i, j)
LoopTuple                                           // false: do nothing
>;

using type = typename tuple_selection_sort_impl // recurse until j == tuple_size
<
i, j + 1, tuple_size, tuple_type // using the modified tuple
>::type;
};


you'd write

template<size_t I, size_t J, size_t N, class LoopTuple>
struct tuple_selection_sort_impl {
using NextLoopTuple = typename Comparator<
std::tuple_element_t<I, LoopTuple>,
std::tuple_element_t<J, LoopTuple>
>::template type<
typename tuple_element_swap<I, J, LoopTuple>::type,
LoopTuple
>;
using type = typename tuple_selection_sort_impl<I, J+1, N, NextLoopTuple>::type;
};


You could perform the same transformation on tuple_element_swap; that is, instead of writing typename tuple_element_swap<I, J, LoopTuple>::type above, you could write typename tuple_element_swap<I, J>::template type<LoopTuple>. This again cuts down on unnecessary type instantiations.

As to whether any of this SCARY-fication actually matters to your compile times in practice, I don't know, you'd have to benchmark it. (For example, by running your sort on a whole bunch of very long and not-identical inputs.) For your single 6-element example that compiles in under a second, of course none of this matters, except for getting comfortable with the idiom.

Notice that I renamed your snake_case template parameter tuple_size to N. This not only flags it for the reader as a template parameter, but also makes the code significantly less confusing, since you do use some instantiations of std::tuple_size (a class template) sprinkled in among your references to tuple_size (an integer constant). Using different names for these different entities helps the reader understand what's going on. Additionally, the reader is already familiar with the runtime idea of "i looping up to n and then stopping," so the idea of I looping up to N and then stopping is immediately accessible in a way that it wasn't accessible when the name of N wasn't N.

EDITED AGAIN TO ADD: I actually tried out a complete rewrite into "SCARY" style, and compilation with Clang got drastically slower. Maybe I'm doing something wrong, or maybe I've misunderstood the advice that I was trying to pass on. :/ In any event, please benchmark before committing to any of my advice above!

The only thing that did noticeably improve compile time in practice was to replace your repeated use of std::tuple_element_t with a bare-bones compiler-intrinsic implementation as described by Louis Dionne in late 2015:

template<size_t, class> struct nth_;
template<size_t I, class... Ts>
struct nth_<I, std::tuple<Ts...>> {
using type = __type_pack_element<I, Ts...>;
};

• ThisIsNotCamelCase, camelCaseHasTheFirstLetterOfTheFirstWordLowerCase. – Chipster Jun 6 at 21:22
• SomeCamelsHaveTwoHumps. – Quuxplusone Jun 7 at 0:35
• Lol, true. My point is I think there's technically another name for ThisTypeOfCase. I think It's called CapitalCase. I'm being really nit picky though. – Chipster Jun 7 at 2:25
• @Chipster ThisTypeOfCaseIsCalledPascalCase. – L. F. Jun 7 at 4:15