constexpr初始化数组以排序内容 [英] constexpr initialization of array to sort contents
问题描述
这是一个谜题，而不是一个现实世界的问题，但我已经陷入一种情况，我想能够写一个行为完全一样的东西
This is a bit of a puzzle rather than a real-world problem, but I've gotten into a situation where I want to be able to write something that behaves exactly like
template<int N>
struct SortMyElements {
int data[N];
template<typename... TT>
SortMyElements(TT... tt) : data{ tt... }
{
std::sort(data, data+N);
}
};
int main() {
SortMyElements<5> se(1,4,2,5,3);
int se_reference[5] = {1,2,3,4,5};
assert(memcmp(se.data, se_reference, sizeof se.data) == 0);
}
，除了我想要 SortMyElements 构造函数 constexpr 。
except that I want the SortMyElements constructor to be constexpr.
显然， code> N ;例如，我可以专门化
Obviously this is possible for fixed N; for example, I can specialize
template<>
struct SortMyElements<1> {
int data[1];
constexpr SortMyElements(int x) : data{ x } {}
};
template<>
struct SortMyElements<2> {
int data[2];
constexpr SortMyElements(int x, int y) : data{ x>y?y:x, x>y?x:y } {}
};
但是如何将它概括为任何 code> N ？
But how do I generalize this into something that will work for any N?
请注意，数组元素必须来自参数的实际值，而不是模板非类型参数;我的元素来自 constexpr 表达式，尽管在编译时被评估，但是它牢牢地位于值系统之内，而不是类型系统。 （例如， Boost.MPL的 sort 严格在类型系统中工作。）
Please notice that the array elements have to come from the actual values of the arguments, not from template non-type arguments; my elements come from constexpr expressions that, despite being evaluated at compile-time, reside firmly inside the "value system", rather than the "type system". (For example, Boost.MPL's sort works strictly within the "type system".)
我发布了一个工作的答案它为 N>工作效率太低。 6 。我想用这个与 2< N < 50 或那里。
I've posted a working "answer", but it's too inefficient to work for N > 6. I'd like to use this with 2 < N < 50 or thereabouts.
（PS-其实我真正想做的是将数组中的所有零值数组并将非零值向前打包，这可能比全开排序更容易;但我认为排序更容易描述。可以自由处理shuffle zeroes问题，而不是排序。）
(P.S.— Actually what I'd really like to do is shuffle all the zeroes in an array to the end of the array and pack the nonzero values toward the front, which might be easier than full-on sorting; but I figure sorting is easier to describe. Feel free to tackle the "shuffle zeroes" problem instead of sorting.)
推荐答案
这是丑陋，可能不是最好的方式排序常量表达式（因为所需的实例化深度）..但voilà，合并sort：
It's ugly, and probably not the best way to sort in a constant expression (because of the required instantiation depth).. but voilà, a merge sort:
辅助类型，带有constexpr元素访问的可返回数组类型：
Helper type, returnable array type with constexpr element access:
#include <cstddef>
#include <iterator>
#include <type_traits>
template<class T, std::size_t N>
struct c_array
{
T arr[N];
constexpr T const& operator[](std::size_t p) const
{ return arr[p]; }
constexpr T const* begin() const
{ return arr+0; }
constexpr T const* end() const
{ return arr+N; }
};
template<class T>
struct c_array<T, 0> {};
append / p>
append function for that array type:
template<std::size_t... Is>
struct seq {};
template<std::size_t N, std::size_t... Is>
struct gen_seq : gen_seq<N-1, N-1, Is...> {};
template<std::size_t... Is>
struct gen_seq<0, Is...> : seq<Is...> {};
template<class T, std::size_t N, class U, std::size_t... Is>
constexpr c_array<T, N+1> append_impl(c_array<T, N> const& p, U const& e,
seq<Is...>)
{
return {{p[Is]..., e}};
}
template<class T, std::size_t N, class U>
constexpr c_array<T, N+1> append(c_array<T, N> const& p, U const& e)
{
return append_impl(p, e, gen_seq<N>{});
}
合并排序：
template<std::size_t Res, class T, class It, std::size_t Accum,
class = typename std::enable_if<Res!=Accum, void>::type >
constexpr c_array<T, Res> c_merge(It beg0, It end0, It beg1, It end1,
c_array<T, Accum> const& accum)
{
return
beg0 == end0 ? c_merge<Res>(beg0 , end0, beg1+1, end1, append(accum, *beg1)) :
beg1 == end1 ? c_merge<Res>(beg0+1, end0, beg1 , end1, append(accum, *beg0)) :
*beg0 < *beg1 ? c_merge<Res>(beg0+1, end0, beg1 , end1, append(accum, *beg0))
: c_merge<Res>(beg0 , end0, beg1+1, end1, append(accum, *beg1));
}
template<std::size_t Res, class T, class It, class... Dummies>
constexpr c_array<T, Res> c_merge(It beg0, It end0, It beg1, It end1,
c_array<T, Res> const& accum, Dummies...)
{
return accum;
}
template<class T, std::size_t L, std::size_t R>
constexpr c_array<T, L+R> c_merge(c_array<T, L> const& l,
c_array<T, R> const& r)
{
return c_merge<L+R>(l.begin(), l.end(), r.begin(), r.end(),
c_array<T, 0>{});
}
template<class T>
using rem_ref = typename std::remove_reference<T>::type;
template<std::size_t dist>
struct helper
{
template < class It >
static constexpr auto merge_sort(It beg, It end)
-> c_array<rem_ref<decltype(*beg)>, dist>
{
return c_merge(helper<dist/2>::merge_sort(beg, beg+dist/2),
helper<dist-dist/2>::merge_sort(beg+dist/2, end));
}
};
template<>
struct helper<0>
{
template < class It >
static constexpr auto merge_sort(It beg, It end)
-> c_array<rem_ref<decltype(*beg)>, 0>
{
return {};
}
};
template<>
struct helper<1>
{
template < class It >
static constexpr auto merge_sort(It beg, It end)
-> c_array<rem_ref<decltype(*beg)>, 1>
{
return {*beg};
}
};
template < std::size_t dist, class It >
constexpr auto merge_sort(It beg, It end)
-> c_array<rem_ref<decltype(*beg)>, dist>
{
return helper<dist>::merge_sort(beg, end);
}
Helpers的使用示例：
Helpers for usage example:
template<class T, std::size_t N>
constexpr std::size_t array_size(T (&arr)[N]) { return N; }
template<class T, std::size_t N>
constexpr T* c_begin(T (&arr)[N]) { return arr; }
template<class T, std::size_t N>
constexpr T* c_end(T (&arr)[N]) { return arr+N; }
使用示例：
constexpr int unsorted[] = {5,7,3,4,1,8,2,9,0,6,10}; // odd number of elements
constexpr auto sorted = merge_sort<array_size(unsorted)>(c_begin(unsorted),
c_end(unsorted));
#include <iostream>
int main()
{
std::cout << "unsorted: ";
for(auto const& e : unsorted) std::cout << e << ", ";
std::cout << '\n';
std::cout << "sorted: ";
for(auto const& e : sorted) std::cout << e << ", ";
std::cout << '\n';
}
输出：
unsorted: 5, 7, 3, 4, 1, 8, 2, 9, 0, 6, 10,
sorted: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,这篇关于constexpr初始化数组以排序内容的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
