Let’s have some fun with templates this time.

C++ has std::integer_sequence, which lets you define compile-time integer sequences. For example:

#include <utility>
using my_seq = std::integer_sequence<int, 1, 2, 3, 4, 5>;

Now let’s write a seq_sort_t trait that performs compile-time sorting, something like:

using my_seq = std::integer_sequence<int, 2, 5, 3, 1, 4>;
using sorted_my_seq = seq_sort_t<my_seq>; // std::integer_sequence<int, 1, 2, 3, 4, 5>

Let’s start with some groundwork.

Runtime Output

Use type extraction to convert std::integer_sequence into a runtime std::initializer_list for easy output.

template <typename S> struct seq_to_init_list;

template <typename T, T... Is>
struct seq_to_init_list<std::integer_sequence<T, Is...>> {
    static constexpr std::initializer_list<T> value = {Is...};
};

template <typename S>
constexpr auto seq_to_init_list_v = seq_to_init_list<S>::value;

Usage:

int main() {
    using seq = std::integer_sequence<int, 1, 2, 3, 4, 5>;
    for (auto i : seq_to_init_list_v<seq>) {
        // Do something...
    }
}

Type Extraction:

In C++ you can define a template:

template <typename T>
class Foo {};

If you need a specialized implementation for a specific type, say T = bool, use partial template specialization:

template <>
class Foo<bool> {};

You can also use other template types during partial specialization. Here the type U is extracted from the passed std::vector<U> type:

template <typename U>
class Foo<std::vector<U>> {};

You can define type aliases with typedef or using:

template <typename U>
class value_type<std::vector<U>> {
    using type = U;
};

A struct like value_type is called a trait.

Nothing to do with Rust.

Sequence Concatenation

Next we need seq_concat_t to concatenate two std::integer_sequences. For convenience, this trait should support concatenating multiple sequences.

template <typename S1, typename... Ss> struct seq_concat;

First, the base case of concatenating two sequences:

template <typename T, T... Ns1, T... Ns2>
struct seq_concat<std::integer_sequence<T, Ns1...>,
                  std::integer_sequence<T, Ns2...>> {
    using type = std::integer_sequence<T, Ns1..., Ns2...>;
};

Then the general case for multiple sequences, which reduces to the two-sequence case:

template <typename S1, typename S2, typename... Ss>
struct seq_concat<S1, S2, Ss...> {
    using type =
        typename seq_concat<S1, typename seq_concat<S2, Ss...>::type>::type;
};

Finally, a convenience wrapper:

template <typename S1, typename... Ss>
using seq_concat_t = typename seq_concat<S1, Ss...>::type;

Usage:

using seq1 = std::integer_sequence<int, 1, 2, 3>;
using seq2 = std::integer_sequence<int, 4>;
using seq3 = std::integer_sequence<int, 5, 6>;
using result = seq_concat_t<seq1, seq2, seq3>; // std::integer_sequence<int, 1, 2, 3, 4, 5, 6>

Variadic Template Parameters:

typename... Ts is a variadic template parameter, representing zero or more types (or integers).

To require at least one type:

template <typename T, typename... Ts>
class Foo {};

You can apply operations to each element of a parameter pack, similar to a map, e.g., (Is + 1)...:

template <int... Is>
struct Foo {
    static constexpr std::initializer_list<T> value = {(Is + 1)...};
};

Also, sizeof...() gives the length of a parameter pack, and fold expressions can be used for reductions.

Quicksort: The Partition Function

The key to quicksort is splitting elements into two groups around a pivot. So let’s define the seq_partition trait first.

seq_partition takes a pivot value V and a sequence S, and splits the elements into left and right based on whether they are less than V. Let’s declare it:

template <typename T, template <T, T> class Comparator, T V, typename S>
struct seq_partition;

We want to support both ascending and descending order, so we pass in a template template parameter Comparator, used as Comparator<1, 2>::value.

seq_partition is recursive. Let’s start with the general case, where the sequence has one or more elements:

template <typename T, template <T, T> class Comparator, T V, T Head, T... Tail>
struct seq_partition<T, Comparator, V,
                     std::integer_sequence<T, Head, Tail...>> {
    using next_ =
        seq_partition<T, Comparator, V, std::integer_sequence<T, Tail...>>;
    using left = std::conditional_t<
        Comparator<Head, V>::value,
        seq_concat_t<std::integer_sequence<T, Head>, typename next_::left>,
        typename next_::left>;
    using right = std::conditional_t<
        Comparator<Head, V>::value, typename next_::right,
        seq_concat_t<std::integer_sequence<T, Head>, typename next_::right>>;
};

Conditional Selection via Specialization:

std::conditional_t is an example of partial specialization. We can implement our own my_conditional_t:

template<bool cond, typename IfTrue, typename IfFalse>
struct my_conditional;

template<typename IfTrue, typename IfFalse>
struct my_conditional<true, IfTrue, IfFalse> {
    using type = IfTrue;
};

template<typename IfTrue, typename IfFalse>
struct my_conditional<false, IfTrue, IfFalse> {
    using type = IfFalse;
};

template<bool cond, typename IfTrue, typename IfFalse>
using my_conditional_t = typename my_conditional<cond, IfTrue, IfFalse>::type;

Now the base case — an empty sequence:

template <typename T, template <T, T> class Comparator, T V>
struct seq_partition<T, Comparator, V, std::integer_sequence<T>> {
    using left = std::integer_sequence<T>;
    using right = std::integer_sequence<T>;
};

Next, we define the comparator traits. We need to handle different integer types T, so the trait should accept a type T and produce a corresponding comparator:

template <typename T> struct less_than {
    template <T V1, T V2>
    using type = std::integral_constant<bool, (V1 < V2)>;
};

template <typename T> struct greater_than {
    template <T V1, T V2>
    using type = std::integral_constant<bool, (V1 > V2)>;
};

Combining seq_partition and the comparator trait, here’s an example:

using seq = std::integer_sequence<int, 1, 2, 3, 4, 5, 6>;
using result = seq_partition<int, less_than<int>, 3, seq>;
using left = typename result::left; // std::integer_sequence<int, 1, 2>
using right = typename result::right; // std::integer_sequence<int, 3, 4, 5, 6>

Quicksort: Main Body

The main quicksort logic is relatively straightforward. seq_sort takes a sequence and a comparator, and returns the sorted sequence:

template <typename T, template <T, T> class Comparator, typename S>
struct seq_sort;

The core: partition the sequence, sort each part, then concatenate:

template <typename T, template <T, T> class Comparator, T Head, T... Tail>
struct seq_sort<T, Comparator, std::integer_sequence<T, Head, Tail...>> {
    using partition_ =
        seq_partition<T, Comparator, Head, std::integer_sequence<T, Tail...>>;
    using left_ = typename partition_::left;
    using right_ = typename partition_::right;
    using type = seq_concat_t<typename seq_sort<T, Comparator, left_>::type,
                              std::integer_sequence<T, Head>,
                              typename seq_sort<T, Comparator, right_>::type>;
};

The base case: an empty sequence returns an empty sequence:

template <typename T, template <T, T> class Comparator>
struct seq_sort<T, Comparator, std::integer_sequence<T>> {
    using type = std::integer_sequence<T>;
};

Finally, a convenience wrapper:

template <typename T, template <T, T> class Comparator, typename S>
using seq_sort_t = typename seq_sort<T, Comparator, S>::type;

And we’re done:

int main() {
    using seq = std::integer_sequence<int, 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5>;
    using sorted1 = seq_sort_t<int, greater_than<int>::type, seq>;
    using sorted2 = seq_sort_t<int, less_than<int>::type, seq>;
    for (auto i : to_initializer_list_v<sorted1>) {
        std::cout << i << ' ';
    }
    std::cout << std::endl;
    for (auto i : to_initializer_list_v<sorted2>) {
        std::cout << i << ' ';
    }
    std::cout << std::endl;
    return 0;
}

Try guessing the output :)

Complete Code

#include <initializer_list>
#include <iostream>
#include <type_traits>
#include <utility>

template <typename S> struct to_initializer_list;

template <typename T, T... Ns>
struct to_initializer_list<std::integer_sequence<T, Ns...>> {
    static constexpr std::initializer_list<T> value = {Ns...};
};

template <typename S>
constexpr std::initializer_list<typename S::value_type> to_initializer_list_v =
    to_initializer_list<S>::value;

template <typename S1, typename... Ss> struct seq_concat;

template <typename T, T... Ns1, T... Ns2>
struct seq_concat<std::integer_sequence<T, Ns1...>,
                  std::integer_sequence<T, Ns2...>> {
    using type = std::integer_sequence<T, Ns1..., Ns2...>;
};

template <typename S1, typename S2, typename... Ss>
struct seq_concat<S1, S2, Ss...> {
    using type =
        typename seq_concat<S1, typename seq_concat<S2, Ss...>::type>::type;
};

template <typename S1, typename... Ss>
using seq_concat_t = typename seq_concat<S1, Ss...>::type;

template <typename T, template <T, T> class Comparator, T V, typename S>
struct seq_partition;

template <typename T, template <T, T> class Comparator, T V, T Head, T... Tail>
struct seq_partition<T, Comparator, V,
                     std::integer_sequence<T, Head, Tail...>> {
    using next_ =
        seq_partition<T, Comparator, V, std::integer_sequence<T, Tail...>>;
    using left = std::conditional_t<
        Comparator<Head, V>::value,
        seq_concat_t<std::integer_sequence<T, Head>, typename next_::left>,
        typename next_::left>;
    using right = std::conditional_t<
        Comparator<Head, V>::value, typename next_::right,
        seq_concat_t<std::integer_sequence<T, Head>, typename next_::right>>;
};

template <typename T, template <T, T> class Comparator, T V>
struct seq_partition<T, Comparator, V, std::integer_sequence<T>> {
    using left = std::integer_sequence<T>;
    using right = std::integer_sequence<T>;
};

template <typename T> struct less_than {
    template <T V1, T V2> using type = std::integral_constant<bool, (V1 < V2)>;
};

template <typename T> struct greater_than {
    template <T V1, T V2> using type = std::integral_constant<bool, (V1 > V2)>;
};

template <typename T, template <T, T> class Comparator, typename S>
struct seq_sort;

template <typename T, template <T, T> class Comparator, T Head, T... Tail>
struct seq_sort<T, Comparator, std::integer_sequence<T, Head, Tail...>> {
    using partition_ =
        seq_partition<T, Comparator, Head, std::integer_sequence<T, Tail...>>;
    using left_ = typename partition_::left;
    using right_ = typename partition_::right;
    using type = seq_concat_t<typename seq_sort<T, Comparator, left_>::type,
                              std::integer_sequence<T, Head>,
                              typename seq_sort<T, Comparator, right_>::type>;
};

template <typename T, template <T, T> class Comparator>
struct seq_sort<T, Comparator, std::integer_sequence<T>> {
    using type = std::integer_sequence<T>;
};

template <typename T, template <T, T> class Comparator, typename S>
using seq_sort_t = typename seq_sort<T, Comparator, S>::type;

int main() {
    using seq = std::integer_sequence<int, 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5>;
    using sorted1 = seq_sort_t<int, greater_than<int>::type, seq>;
    using sorted2 = seq_sort_t<int, less_than<int>::type, seq>;
    for (auto i : to_initializer_list_v<sorted1>) {
        std::cout << i << ' ';
    }
    std::cout << std::endl;
    for (auto i : to_initializer_list_v<sorted2>) {
        std::cout << i << ' ';
    }
    std::cout << std::endl;