Sorting non-type template parameter pack in C++11 or C++1y?

Question

In C++11 and/or C++1y:

Suppose I am given a template with a non-type parameter pack:

template<int...>
void f();

And I'm writing another template that will instantiate it:

template<int... x>
void g()
{
    ???

    f<???>();
}

I want g to instantiate f with x in sorted order.

That is:

g<4,7,2,9,3,7>();

should call:

f<2,3,4,7,7,9>();

Can this be done? If so, what is the most efficient way (up to constant factors)?

Answer 1

Here is a solution that transform the list to skew heap then to sorted list.

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

template <class T, T... s>
using iseq = std::integer_sequence<T, s...>;

template <class T, T v>
using ic = std::integral_constant<T, v>;

template <bool b>
using bool_cond_t = std::conditional_t<b, std::true_type, std::false_type>;

// define compare function
template <class T, T v1, T v2>
constexpr auto ic_less_impl(ic<T, v1>, ic<T, v2>) -> bool_cond_t<(v1 < v2)>;
template <class ic1, class ic2>
using ic_less = decltype(ic_less_impl(ic1(), ic2()));

// data structure for null
struct nil {};

// get first element from sequence
template <class T, T v, T... s>
constexpr auto iseq_front_impl(iseq<T, v, s...>) -> ic<T, v>;

template <class T>
constexpr auto iseq_front_impl(iseq<T>) -> nil;

template <class seq>
using iseq_front = decltype(iseq_front_impl(seq()));

// remove first element from sequence
template <class T, T v, T... s>
constexpr auto iseq_pop_front_impl(iseq<T, v, s...>) -> iseq<T, s...>;

template <class seq>
using iseq_pop_front = decltype(iseq_pop_front_impl(seq()));

// append element into sequence
template <class T, T v, T... s>
constexpr auto iseq_append_impl(iseq<T, s...>, ic<T, v>) -> iseq<T, s..., v>;

template <class T, T v>
constexpr auto iseq_append_impl(nil, ic<T, v>) -> iseq<T, v>;

template <class seq, class c>
using iseq_append = decltype(iseq_append_impl(seq(), c()));

// check whether the sequence is empty
template <class seq>
using iseq_is_empty = bool_cond_t<std::is_same<iseq_front<seq>, nil>::value>;

// define structure of skew heap
template <class X, class L, class R>
struct skew_heap {};

// get the top of skew heap
template <class X, class L, class R>
constexpr auto skh_get_top_impl(skew_heap<X, L, R>) -> X;

template <class H>
using skh_get_top = decltype(skh_get_top_impl(H()));

// get left subtree of skew heap
template <class X, class L, class R>
constexpr auto skh_get_left_impl(skew_heap<X, L, R>) -> L;

template <class H>
using skh_get_left = decltype(skh_get_left_impl(H()));

// get right subtree of skew heap
template <class X, class L, class R>
constexpr auto skh_get_right_impl(skew_heap<X, L, R>) -> R;

template <class H>
using skh_get_right = decltype(skh_get_right_impl(H()));

// check whether skew heap is empty
template <class H>
using skh_is_empty = bool_cond_t<std::is_same<H, nil>::value>;

// skew heap merge function
template <class H1, class H2>
constexpr auto skh_merge_impl(H1, H2) -> decltype(auto) {
    if constexpr (skh_is_empty<H1>::value) {
        return H2{};
    } else if constexpr (skh_is_empty<H2>::value) {
        return H1{};
    } else {
        using x1 = skh_get_top<H1>;
        using l1 = skh_get_left<H1>;
        using r1 = skh_get_right<H1>;

        using x2 = skh_get_top<H2>;
        using l2 = skh_get_left<H2>;
        using r2 = skh_get_right<H2>;

        if constexpr (ic_less<x2, x1>::value) {
            using new_r2 = decltype(skh_merge_impl(H1(), r2()));
            return skew_heap<x2, new_r2, l2> {};
        } else {
            using new_r1 = decltype(skh_merge_impl(r1(), H2()));
            return skew_heap<x1, new_r1, l1>{};
        }
    }
}

template <class H1, class H2>
using skh_merge = decltype(skh_merge_impl(H1(), H2()));

// push an element into skew heap
template <class H1, class IC1>
using skh_push = skh_merge<H1, skew_heap<IC1, nil, nil>>;

// pop an element from skew heap
template <class H>
using skh_pop = skh_merge<skh_get_left<H>, skh_get_right<H>>;

// convert sequence to skew heap
template <class H, class seq>
constexpr auto skh_heapify_impl(H, seq) -> decltype(auto) {
    if constexpr (iseq_is_empty<seq>::value) {
        return H{};
    } else {
        using val = iseq_front<seq>;
        return skh_heapify_impl(skh_push<H, val>{}, iseq_pop_front<seq>{});
    }
}

template <class seq>
using skh_heapify = decltype(skh_heapify_impl(nil(), seq()));

// convert skew heap to sorted sequence
template <class H, class seq>
constexpr auto skh_to_sortlist_impl(H, seq) -> decltype(auto) {
    if constexpr (skh_is_empty<H>::value) {
        return seq{};
    } else {
        using val = skh_get_top<H>;
        return skh_to_sortlist_impl(skh_pop<H>{}, iseq_append<seq, val>{});
    }
}

template <class H>
using skh_to_sortlist = decltype(skh_to_sortlist_impl(H(), nil()));

// sort sequence
template <class seq>
using sort_iseq = skh_to_sortlist<skh_heapify<seq>>;

template <int... s>
void f() {
    for (auto x : {s...})
        std::cout << x << " ";
    std::cout << "\n";
}

template <int... s>
void g_helper(iseq<int, s...>) {
    f<s...>();
}

template <int... s>
void g() {
    g_helper(sort_iseq<iseq<int, s...>>{});
}

int main(void) {
    g<2, 3, 5, 8, 9, 6, 7, 1>();
    return 0;
}

It's also able to be implemented in c++11.

c++11 solution and online demo

Answer 2

All those answers are so depressingly C++11... lots and lots of template meta-programming spew.
Here is C++14 solution using plain sort constexpr function.

(compile and run with clang + libc++ trunk with std=c++1y)

#include <utility>
#include <iostream>


template<int... x>
void f()
{
   constexpr int x_array[] = {x...};

   for(int i = 0; i < sizeof...(x); i++)
      std::cout << x_array[i] << " ";

   std::cout << std::endl;
}

template <typename T, int N>
struct ConstArray
{
   T data[N];
   constexpr T& operator[](int i){return data[i];}
   constexpr const T& operator[](int i) const {return data[i];}
};


template<int... x>
constexpr auto bubble_sort_best_sort()
{
   constexpr int N = sizeof...(x);
   ConstArray<int, N> a = {x...};

  for (int i = 0;  i < N - 1;  i++)
  {
    for (int j = 0;  j < N - i - 1;  j++)
    {
      if (a.data[j] > a.data[j+1])
      {
        int temp  = a[j];
        a[j] = a[j+1];
        a[j+1]= temp;
      }
    }
  }
  return a;
}



template<int... x, int...i>
void g_imp(std::integer_sequence<int, x...>, 
           std::integer_sequence<int, i...> )
{
    constexpr auto array_sorted = bubble_sort_best_sort<x...>();
    f<array_sorted[i]...>();
}


template<int... x>
void g()
{
    auto seq = std::integer_sequence<int, x...>();
    auto idx = std::make_integer_sequence<int, sizeof...(x)>();

    g_imp(seq, idx);
}

int main()
{
  g<4, 7, 2, 9, 3, 7>();
  return 0;
}

It's a bit strange that we are forced to define a custom ConstantArray instead of using std::array.
std::array could be fine here if only its "T& operator[]" member would have been constexpr. I checked in the latest draft and it's still not the case, but I don't understand why.

Answer 3

Here is a working solution (my first attempt). Your code would look like this:

template<int...N>
void f() 
{
    //this line is just to generate compilation error so that
    //you can see the sorted ints in the error message
    list<N...> generate_error = 0;
}

template<int...N>
void invoke_f_with(list<N...>) 
{
    f<N...>();
}
 
template<int...N>
void g()
{
  invoke_f_with(typename sort<list<N...>>::type{});
}

As I intended, the generated error message contains this:

main.cpp: In instantiation of ‘void f() [with int ...N = {2, 3, 4, 7, 7, 9}]’:

That shows the integer template arguments are sorted.

The above solution makes use of sort<> and list<> class templates which are implemented as:

#include <type_traits>

template<int ...N> 
struct list { using type = list<N...>; };

template<int N, typename IntList> 
struct prepend;

template<int N, int ... ints> 
struct prepend<N, list<ints...>>  : list<N, ints...> {};

namespace detail
{
    template<int A, int B> 
    struct min : std::integral_constant<int, (A < B ? A : B)> {};
    
    template<int A, int B> 
    struct max : std::integral_constant<int, (A > B ? A : B)> {};
    
    template<int i, int ...ints> 
    struct insert_impl : list<i> {};
    
    template<int i, int A, int ...ints> 
    struct insert_impl<i, A, ints...> : prepend<min<i,A>{}, typename insert_impl<max<i,A>{}, ints...>::type> {};
    
    template<int i, typename IntList> 
    struct insert;
    
    template<int i, int ...ints> 
    struct insert<i, list<ints...>> : insert_impl<i, ints...> {};
}

template<typename IntList> 
struct sort : list<> {};

template<int A, int ...N> 
struct sort<list<A,N...>> : detail::insert<A, typename sort<list<N...>>::type> {}; 

Online Demo.

Hope that helps. :-)

Answer 4

It took a bit to put it together but here is another complete implementation:

#include <iostream>
#include <type_traits>

// ------------------------------------------------------------------------
template <int X>
void print_values() { std::cout << X; }
template <int X, int Y, int... Z>
void print_values() { std::cout << X << ", "; print_values<Y, Z...>(); }
template <int... X>
void print() { print_values<X...>(); std::cout << '\n'; }
// ------------------------------------------------------------------------

template <int...> struct value_list {};

// ------------------------------------------------------------------------

template <int X, typename> struct combine;
template <int X, int...Y>
struct combine<X, value_list<Y...>>
{
    typedef value_list<X, Y...> type;
};

// ------------------------------------------------------------------------

template <typename, typename> struct merge;

template <int... X>
struct merge<value_list<X...>, value_list<>> {
    typedef value_list<X...> type;
};
template <int... Y>
struct merge<value_list<>, value_list<Y...>> {
    typedef value_list<Y...> type;
};

template <int X0, int... X, int Y0, int... Y>
struct merge<value_list<X0, X...>, value_list<Y0, Y...>> {
    typedef typename std::conditional<(X0 < Y0),
        typename combine<X0,
            typename merge<value_list<X...>,
                           value_list<Y0, Y...>
            >::type
        >::type,
        typename combine<Y0,
            typename merge<value_list<X0, X...>,
                           value_list<Y...>
            >::type
        >::type
    >::type type;
};

// -----------------------------------------------------------------------------

template <int... X> struct sort;

template <int X>
struct sort<X> { typedef value_list<X> type; };
template <int X, int Y>
struct sort<X, Y> { typedef value_list<(X < Y? X: Y), (X < Y? Y: X)> type; };
template <int X, int Y, int... Z>
struct sort<X, Y, Z...> {
    typedef typename merge<typename sort<X, Y>::type,
                           typename sort<Z...>::type>::type type;
};

// -----------------------------------------------------------------------------

template <int... X>
void f()
{
    print<X...>();
}

template <typename> struct g_helper;
template <int... X>
struct g_helper<value_list<X...>>
{
    static void call() { f<X...>(); }
};

template <int... X>
void g()
{
    print<X...>();
    g_helper<typename sort<X...>::type>::call();
}

int main()
{
    g<4,7,2,9,3,7>();
}

Answer 5

I suppose you can use Boost MPL's sort "function": http://www.boost.org/doc/libs/1_51_0/libs/mpl/doc/refmanual/sort.html

Given a list of values as template parameters, plus a predicate (which defaults to less as is customary), it will produce a "copy" in sorted order. The claimed complexity is O(n log(n)) "on average", O(n^2) worst-case; making it similar to Quicksort (and in fact, it appears to actually use Quicksort).

You asked about this function's "internal architecture." About that, I surely have no idea, but given the maturity of Boost MPL and my prior experience using it, I'd say give it a try and if it does what you need, you'll probably find it about as satisfying as you find any other C++ template meta-programming.