在C++ 11或C++ 1y中排序非类型模板参数包？

Question

在C++ 11和/或C++中:

假设我给出了一个带有非类型参数包的模板:

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

我正在编写另一个将实例化它的模板:

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

    f<???>();
}

我希望g以排序顺序用x实例化f.

那是:

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

应致电:

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

可以这样做吗？如果是这样,最有效的方法是什么(由常数因素决定)？

Answer 1

所有这些答案都是令人沮丧的C++ 11 ......很多很多模板元编程都会出现.
这是使用普通排序constexpr函数的C++ 14解决方案.

(使用std = c ++ 1y编译并运行clang + libc ++ trunk)

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

我们被迫定义自定义ConstantArray而不是使用std :: array有点奇怪.
如果只有它的"T&operator []"成员将是constexpr,那么std :: array可能没问题.我检查了最新的草案,但事实并非如此,但我不明白为什么.

Answer 2

这是一个有效的解决方案(我的第一次尝试).您的代码如下所示:

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

按照我的意图,生成的错误消息包含:

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

这表明整数模板参数已排序.

上面的解决方案使用sort<>和list<>类模板,实现如下:

#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> {}; 

在线演示.

希望有所帮助.:-)

Answer 3

我想你可以使用Boost MPL的排序"功能": http //www.boost.org/doc/libs/1_51_0/libs/mpl/doc/refmanual/sort.html

给定值列表作为模板参数,加上谓词(默认less为惯例),它将按排序顺序生成"副本".要求保护的复杂性是"平均"O(n log(n)),O(n ^ 2)最坏情况; 使它类似于Quicksort(事实上,它似乎实际上使用Quicksort).

你问过这个功能的"内部架构".关于这一点,我当然不知道,但鉴于Boost MPL的成熟度以及我以前使用它的经验,我会说尝试一下,如果它能满足您的需求,您可能会觉得它和您一样令人满意找到任何其他C++模板元编程.