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

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 2

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. :-)