constexpr initialization of array to sort contents

Question

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

except that I want the SortMyElements constructor to be constexpr.

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

But how do I generalize this into something that will work for any N?

---

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

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.

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

Answer 1

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:

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

Merge sort:

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

Usage example:

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

Output:

unsorted: 5, 7, 3, 4, 1, 8, 2, 9, 0, 6, 10, 
sorted: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,

Answer 2

I know that this is an old question but as we have C++14 (and C++17 soon), and since C++14 constexpr rules aren't so restricted, and, for sure, couple of people will find your question in google, here is how quicksort (and of course other algorithms) can be done since C++14. (big credits to @dyp for constexpr array)

#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