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

Kunz

Can you really call non-constexpr functions (like sort) from something that is a constexpr (like your constructor)? It doesn't really make sense to be able to do that. – Hyetology

@Hyetology Well, obviously std::sort isn't constexpr; the puzzle is to write something that behaves like std::sort but is constexpr. – Kunz

I see, sorry. A compile-time sort meta-function would be pretty cool... – Hyetology

If you have Boost, you might want to look at its MPL library boost.org/doc/libs/1_51_0/libs/mpl/doc/refmanual/sort.html, if not, maybe the source code could give you some ideas. – Hyetology

Would a faster version which is called with SortMyElements<N>((list<1,2,3,4,...,50>())); be of interest? (55 elements in .7s on my machine) – Trouble

@DanielFrey Possibly, but the 1,2,3,... in my case originate outside the type system (they're the ASCII values of the chars constexpr-ly exploded out of a string literal), so I believe there's no way to get them into the type system, if you see what I mean. – Kunz

Related: https://mcmap.net/q/796782/-sorting-non-type-template-parameter-pack-in-c-11-or-c-1y/420683 – Pettifer

@Kunz I will probably play with some code tomorrow as I think that my version could be transformed into what you need. – Trouble

For C++20, std::sort is constexpr – Stumpy

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,

Pettifer

It compiles with clang++3.4 trunk 193040 Debug+Assert build reasonably fast even with about 50 elements. g++4.8.1 currently refuses it, I'll try to figure out why (imagine the diagnostic messages..) – Pettifer

g++4.8.1: error: (const int*)(& const int [1]{5}) is not a constant expression hmm it's not an address constant expression... I could pass around indices instead :( – Pettifer

Can you explain how the recursive inheritance template works? – Mountainside

@Mountainside You mean gen_seq? The first template parameter is a counter, and the remaining ones are the result. gen_seq<2, something> inherits from gen_seq<1, 1, something> which in turn inherits from gen_seq<0, 0, 1, something>. That is, each step of inheritance adds one number to the result. The base class in any case is some gen_seq<0, result>, which makes the result of the previous inheritance steps available by ... inheriting from seq<result>. You start with gen_seq<4> and it will finally inherit from seq<0, 1, 2, 3>. – Pettifer

@Mountainside If you supply a gen_seq<X> object as the last argument to a call of the append_impl function, the compiler will find the seq<result> that is some grand-grand-grand-....-parent class of gen_seq<X>. From that seq<result>, the compiler can deduce the sequence of integers. – Pettifer

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

Dwyer

I hit compilation error about reaching of maximum of recursion depth when tried to apply this implementation to sorted array of 400 elements. Actually seems that maximum count of elements as less than 80 on my compiler. I'll try comb_sort instead. – Inverson

Answer 3

A bit late to the party, but a much better and simpler implementation is the following comb_sort implementation.

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

Output: 0 1 2 5 6 7 8 9

Why better, it's [the algorithm] often as good as insertion sort, but is non-recursive, which means it will work on any size arrays (at least not limited by the recursive depth).

Cogswell

Any ideas why std::sort() from algorithm header is not a constexpr function and all you guys have to come up with a custom sort function? I consider to put this comment into a question, btw. – Pagano

@Pagano std::sort will be a constexpr function in C++20 – Sisal

Answer 4

Well, I got my inefficient version to compile, at least with Clang on OSX. Here's the code.

However, while it's tolerably fast for five elements, on my laptop it takes 0.5 seconds to sort six elements and 7 seconds to sort seven elements. (Catastrophically varying performance, too, depending on whether the items are almost-sorted or reverse-sorted.) I didn't even try timing eight. Clearly, this doesn't scale to the kind of things I want to do with it. (I'd say 50 elements is a reasonable upper bound for my contrived use-case, but 6 is unreasonably tiny.)

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

---

UPDATE: I haven't figured out how to do a fast mergesort (although DyP's answer looks potentially feasible to me). However, this morning I did solve my original puzzle-problem of shuffling zeroes to the end of an array! I used a recursive partition-and-merge algorithm; the code looks like this.

Kunz

Answer 5

Starting with C++20, all you need to change in your example is to add constexpr to the constructor. That is, in C++20, std::sort is in fact constexpr.

Galipot

example: wandbox.org/permlink/goTUOM6R4FFp4j7A – Vitiligo