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

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. — masaers, Oct 24 '13 at 08:38
@masaers Well, obviously `std::sort` isn't constexpr; the puzzle is to write something that behaves like `std::sort` but *is* constexpr. — Quuxplusone, Oct 24 '13 at 08:40
I see, sorry. A compile-time sort meta-function would be pretty cool... — masaers, Oct 24 '13 at 09:06
If you have Boost, you might want to look at its MPL library http://www.boost.org/doc/libs/1_51_0/libs/mpl/doc/refmanual/sort.html, if not, maybe the source code could give you some ideas. — masaers, Oct 24 '13 at 09:16
Would a faster version which is called with SortMyElements((list<1,2,3,4,...,50>())); be of interest? (55 elements in .7s on my machine) — Daniel Frey, Oct 24 '13 at 09:21
@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. — Quuxplusone, Oct 24 '13 at 15:57
@Quuxplusone I will probably play with some code tomorrow as I think that my version could be transformed into what you need. — Daniel Frey, Oct 24 '13 at 17:08
For C++20, [`std::sort` is `constexpr`](https://stackoverflow.com/a/62725827/4123703) — Louis Go, Oct 18 '22 at 06:54

score 12 · Answer 1 · answered Oct 24 '13 at 17:35

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,

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..) — dyp, Oct 24 '13 at 17:46
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 :( — dyp, Oct 24 '13 at 18:00
Can you explain how the recursive inheritance template works? — user877329, Jun 12 '16 at 17:55
@user877329 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`. You start with `gen_seq<4>` and it will finally inherit from `seq<0, 1, 2, 3>`. — dyp, Jun 13 '16 at 20:10
@user877329 If you supply a `gen_seq` object as the last argument to a call of the `append_impl` function, the compiler will find the `seq` that is some grand-grand-grand-....-parent class of `gen_seq`. From that `seq`, the compiler can deduce the sequence of integers. — dyp, Jun 13 '16 at 20:13

score 8 · Answer 2 · answered Oct 13 '16 at 20:09

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

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. — Hsilgos, Jul 02 '22 at 13:42

score 5 · Answer 3 · answered Mar 17 '19 at 09:58

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

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. — BitTickler, Jun 28 '20 at 03:36
@BitTickler `std::sort` will be a `constexpr` function in C++20 — JensB, Jan 07 '22 at 22:56

score 3 · Answer 4 · edited May 23 '17 at 12:34

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.

score 3 · Answer 5 · answered Jul 04 '20 at 05:55

3

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.

answered Jul 04 '20 at 05:55

burnpanck

1,955
1
12
36

1

example: https://wandbox.org/permlink/goTUOM6R4FFp4j7A – Jerry Jeremiah May 17 '21 at 02:25

constexpr initialization of array to sort contents

5 Answers5

Linked