所有这些答案都是令人沮丧的 C++11 ......大量的模板元编程喷涌而出。
这是使用普通排序 constexpr 函数的 C++14 解决方案。
（使用 clang + libc++ trunk 编译和运行，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;
}
有点奇怪，我们被迫定义一个自定义的 ConstantArray 而不是使用 std::array。
如果只有它的“T& operator[]”成员是 constexpr，那么 std::array 在这里可能没问题。我检查了最新的草稿，但仍然不是这样，但我不明白为什么。
这是一个可行的解决方案（我的第一次尝试）。您的代码如下所示：
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> {};
在线演示。
希望有帮助。:-)
我想你可以使用 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) 最坏情况；使其类似于快速排序（事实上，它似乎实际上使用了快速排序）。
您询问了此功能的“内部架构”。关于这一点，我当然不知道，但鉴于 Boost MPL 的成熟度和我之前使用它的经验，我会说尝试一下，如果它满足你的需要，你可能会发现它和你一样令人满意查找任何其他 C++ 模板元编程。
把它放在一起花了一些时间，但这是另一个完整的实现：
#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>();
}
这是一个将列表转换为倾斜堆然后转换为排序列表的解决方案。
#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;
}
它也可以在 c++11 中实现。