使用constexpr对数组进行初始化以对其内容进行排序

Question

使用constexpr对数组进行初始化以对其内容进行排序

c++c++11template-meta-programmingconstexpr

8

这是一个谜题而不是现实中的问题，但我遇到了这样一种情况：我想写些东西，让它的行为与

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 外，其他都可以保持不变。

显然，对于固定的 N，这是可能的；例如，我可以进行特化。

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

但是我该如何将这个泛化为适用于任何N的东西呢？

请注意，数组元素必须来自实际参数值，而不是来自模板非类型参数；我的元素来自于constexpr表达式，尽管在编译时计算，但仍然属于“值系统”，而不是“类型系统”。（例如， Boost.MPL的sort 严格工作在“类型系统”内。）

我已经发布了一个可行的“答案”，但对于N > 6来说效率太低了。我想在2 < N < 50左右使用它。

（附言-实际上，我真正想做的是将数组中所有的零洗牌到数组的末尾，并将非零值向前打包，这可能比完全排序更容易；但我认为排序更容易描述。随意解决“洗牌零”问题而不是排序。）

- Quuxplusone

你真的可以从一个constexpr（比如你的构造函数）中调用非constexpr函数（比如sort）吗？这样做似乎没有什么意义。 - masaers

@masaers 嗯，显然 std::sort 不是 constexpr；这个谜题是要编写一个像 std::sort 一样的东西，但是 constexpr 的。 - Quuxplusone

我明白了，抱歉。编译时排序元函数会非常酷... - masaers

如果你有Boost，你可能想看看它的MPL库http://www.boost.org/doc/libs/1_51_0/libs/mpl/doc/refmanual/sort.html，如果没有，也许源代码可以给你一些想法。 - masaers

@Quuxplusone 我明天可能会动手写一些代码，因为我觉得我的版本可以转换成你所需要的形式。 - Daniel Frey

显示剩余4条评论

5个回答

8

我知道这是一个老问题，但随着我们拥有C++14（以及很快的C++17），自从C++14 constexpr规则不再那么受限制，肯定有一些人会在谷歌上找到你的问题。下面是自C++14以来如何使用快速排序（当然还有其他算法）。（感谢@dyp提供constexpr数组）

#include <utility>
#include <cstdlib>

template<class T>
constexpr void swap(T& l, T& r)
{
    T tmp = std::move(l);
    l = std::move(r);
    r = std::move(tmp);
}

template <typename T, size_t N>
struct array
{
    constexpr T& operator[](size_t i)
    {
        return arr[i];
    }

    constexpr const T& operator[](size_t i) const
    {
        return arr[i];
    }

    constexpr const T* begin() const
    {
        return arr;
    }
    constexpr const T* end() const
    {
        return arr + N;
    }

    T arr[N];
};

template <typename T, size_t N>
constexpr void sort_impl(array<T, N> &array, size_t left, size_t right)
{
    if (left < right)
    {
        size_t m = left;

        for (size_t i = left + 1; i<right; i++)
            if (array[i]<array[left])
                swap(array[++m], array[i]);

        swap(array[left], array[m]);

        sort_impl(array, left, m);
        sort_impl(array, m + 1, right);
    }
}

template <typename T, size_t N>
constexpr array<T, N> sort(array<T, N> array)
{
    auto sorted = array;
    sort_impl(sorted, 0, N);
    return sorted;
}

constexpr array<int, 11> unsorted{5,7,3,4,1,8,2,9,0,6,10}; // odd number of elements
constexpr auto sorted = sort(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';
}

LIVE DEMO

- stryku

尝试将该实现应用于包含400个元素的排序数组时，我遇到了递归深度最大的编译错误。实际上，似乎我的编译器中的最大元素计数少于80个。我会尝试使用梳排序代替。 - Hsilgos

5

虽然有些晚了，但以下是一种更好、更简单的实现方式：梳排序实现。

template<typename Array>
constexpr void comb_sort_impl ( Array & array_ ) noexcept {
    using size_type = typename Array::size_type;
    size_type gap = array_.size ( );
    bool swapped = false;
    while ( ( gap > size_type { 1 } ) or swapped ) {
        if ( gap > size_type { 1 } ) {
            gap = static_cast<size_type> ( gap / 1.247330950103979 );
        }
        swapped = false;
        for ( size_type i = size_type { 0 }; gap + i < static_cast<size_type> ( array_.size ( ) ); ++i ) {
            if ( array_ [ i ] > array_ [ i + gap ] ) {
                auto swap = array_ [ i ];
                array_ [ i ] = array_ [ i + gap ];
                array_ [ i + gap ] = swap;
                swapped = true;
            }
        }
    }
}

template<typename Array>
constexpr Array sort ( Array array_ ) noexcept {
    auto sorted = array_;
    comb_sort_impl ( sorted );
    return sorted;
}

int main ( ) {

    constexpr auto sorted = sort ( std::array<int, 8> { 6, 8, 0, 1, 5, 9, 2, 7 } );

    for ( auto i : sorted )
        std::cout << i << ' ';
    std::cout << std::endl;

    return EXIT_SUCCESS;
}

输出: 0 1 2 5 6 7 8 9

为什么这个算法更好，因为它通常和插入排序一样优秀，但是它是非递归的，这意味着它适用于任何大小的数组（至少不受递归深度的限制）。

- degski

你们有什么想法为什么来自“algorithm”头文件的“std::sort()”不是constexpr函数，而你们所有人都必须想出一个自定义排序函数？顺便说一句，我考虑把这个评论放到一个问题里。 - BitTickler

1

@BitTickler std::sort 在 C++20 中将成为一个 constexpr 函数。 - JensB

3

好的，我已经将我的低效版本编译成功了，至少在OSX上使用Clang编译成功。以下是代码。

然而，尽管对于五个元素来说速度还算可以接受，在我的笔记本电脑上，排序六个元素需要0.5秒，排序七个元素需要7秒。（性能也会出现灾难性的变化，具体取决于项目是否接近排序或者反向排序。）我甚至没有尝试计时八个元素。显然，这不能扩展到我想要处理的那种事情。（我认为50个元素是我设计的合理上限，但6个元素太小了。）

#include <cstring>
#include <cassert>

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

// Now let's make a consecutive range of ints from [A to B).
template<int A, int B, int... Accum>
struct IntRange_ : IntRange_<A+1, B, Accum..., A> {};

template<int A, int... Accum>
struct IntRange_<A, A, Accum...> {
    using type = IntHolder<Accum...>;
};

template<int A, int B>
using IntRange = typename IntRange_<A,B>::type;

// And a helper function to do what std::min should be doing for us.
template<typename... TT> constexpr int min(TT...);
constexpr int min(int i) { return i; }
template<typename... TT> constexpr int min(int i, TT... tt) { return i < min(tt...) ? i : min(tt...); }

template<int N>
struct SortMyElements {
    int data[N];

    template<int... II, typename... TT>
    constexpr SortMyElements(IntHolder<II...> ii, int minval, int a, TT... tt) : data{
        ( a==minval ? a : SortMyElements<N>(ii, minval, tt..., a).data[0] ),
        ( a==minval ? SortMyElements<N-1>(tt...).data[II] : SortMyElements<N>(ii, minval, tt..., a).data[II+1] )...
    } {}

    template<typename... TT>
    constexpr SortMyElements(TT... tt) : SortMyElements(IntRange<0,sizeof...(tt)-1>(), min(tt...), tt...) {}
};

template<>
struct SortMyElements<1> {
    int data[1];
    constexpr SortMyElements(int x) : data{ x } {}
    constexpr SortMyElements(IntHolder<>, int minval, int x) : SortMyElements(x) {}
};

static_assert(SortMyElements<5>(5,2,1,3,1).data[0] == 1, "");
static_assert(SortMyElements<5>(5,2,1,3,1).data[1] == 1, "");
static_assert(SortMyElements<5>(5,2,1,3,1).data[2] == 2, "");
static_assert(SortMyElements<5>(5,2,1,3,1).data[3] == 3, "");
static_assert(SortMyElements<5>(5,2,1,3,1).data[4] == 5, "");

char global_array[ SortMyElements<5>(1,4,2,5,3).data[2] ];
static_assert(sizeof global_array == 3, "");

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

更新：我还没有找到如何快速进行归并排序的方法（尽管DyP的答案看起来对我来说是可行的）。然而，今天早上我解决了我的原始难题 - 将零洗牌到数组的末尾！我使用了递归的分区和合并算法；代码看起来像这样。

- Quuxplusone

3

从C++20开始，您需要更改示例中的唯一内容是将constexpr添加到构造函数中。也就是说，在C++20中，std::sort实际上是constexpr。

- burnpanck

2

示例：https://wandbox.org/permlink/goTUOM6R4FFp4j7A - Jerry Jeremiah

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- dyp · Accepted Answer

这是一个很丑陋的做法，可能不是在常量表达式中排序的最佳方式（由于需要实例化深度），但是有了归并排序：

帮助类型，具有可返回的数组类型和constexpr元素访问：

#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函数用于该数组类型：

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

使用示例的辅助工具：

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

输出:

未排序: 5, 7, 3, 4, 1, 8, 2, 9, 0, 6, 10, 
已排序: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,