Selection sorting a type list (compile-time)

Question

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 , "!" );
}

Answer 1

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.

---

EDITED TO ADD:

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.

Taking your current code, you'd make two substitutions. Instead of

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

And then instead of

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