constexpr Initialisierung von Array zu sortieren Inhalt

Question

Dies ist ein bisschen wie ein Puzzle, statt einer realen Problem, aber ich habe in eine Situation geraten, wo ich in der Lage sein, etwas zu schreiben, das genau verhält sich wie

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

außer dass ich möchte, dass der SortMyElements Konstruktor constexpr ist.

Offensichtlich ist dies für feste N möglich; zum Beispiel kann ich

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

spezialisiert Aber wie verallgemeinern ich dies in etwas, das für jedeN funktionieren wird?

---

Bitte beachten Sie, dass die Array-Elemente von den tatsächlichen Werten der Argumente kommen, nicht aus Vorlage nicht-Typargument; Meine Elemente stammen aus constexpr Ausdrücken, die, obwohl sie zur Kompilierungszeit ausgewertet werden, fest im "Wertesystem" und nicht im "Typensystem" verankert sind. (Zum Beispiel Boost.MPL's sort arbeitet streng innerhalb des „Typ-Systems“).

Ich habe eine funktionierende „Antwort“ geschrieben, aber es ist zu ineffizient für N > 6 zu arbeiten. Ich möchte das mit 2 < N < 50 oder in der Nähe verwenden.

(PS- Eigentlich möchte ich wirklich alle Nullen in einem Array an das Ende des Arrays mischen und die Werte ungleich Null nach vorne packen, was einfacher sein kann als vollständige Sortierung; aber Ich denke, Sortierung ist einfacher zu beschreiben.Fühlen Sie sich frei, die "Shuffle Nullen" Problem statt Sortieren.

Answer 1

Nun, ich habe meine ineffiziente Version zu kompilieren, zumindest mit Clang auf OSX. Hier ist der Code.

Während es für fünf Elemente ziemlich schnell ist, dauert es auf meinem Laptop 0,5 Sekunden, um sechs Elemente zu sortieren und sieben Sekunden, um sieben Elemente zu sortieren. (Auch katastrophale Leistung, je nachdem, ob die Artikel fast sortiert oder umgekehrt sortiert sind.) Ich habe nicht einmal acht Mal versucht. Natürlich skaliert das nicht zu den Dingen, die ich damit machen möchte. (Ich würde sagen, 50 Elemente ist eine vernünftige Obergrenze für meinen erfundenen Anwendungsfall, aber 6 ist unangemessen klein.)

#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: Ich habe nicht, wie herausgefunden ein tun schneller mergesort (obwohl DyP's answer für mich potentiell machbar scheint). Doch heute morgen habe ich mein ursprüngliches Puzzle-Problem gelöst: Nullen mischen bis zum Ende eines Arrays! Ich habe einen rekursiven Partition-and-Merge-Algorithmus verwendet; der Code sieht aus wie this.

Answer 2

Es ist hässlich, und wahrscheinlich nicht die beste Möglichkeit, in einem konstanten Ausdruck zu sortieren (wegen der erforderlichen Instanziierungstiefe) ..aber voilà, ein Merge Sort:

Helper-Typ, Mehrweg-Array-Typ mit constexpr Element Zugang:

#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 Funktion für diesen Array-Typ:

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

Helfer für Anwendungsbeispiel:

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

Anwendungsbeispiel:

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

Ausgang:

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 3

Ich weiß, dass dies eine alte Frage ist aber, wie wir haben C++ 14 (und 17 C++ in Kürze), und da C++ 14 constexpr Regeln nicht so eingeschränkt sind, und sicher einige Leute Ihre Frage in Google finden werden, hier ist, wie Quicksort (und natürlich andere Algorithmen) seit C++ 14 getan werden kann. (große Firmen für constexpr Array @dyp)

#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