Wie kann ich Konditionale in einem Template-Metaprogramm kurzschließen?

Question

Ich implementiere eine Merge-Sortierung in Vorlage Metaprogramm. (Ob Sie es glauben oder nicht, wir haben einen echten Anwendungsfall für diese in der Produktion.)

Mein Code funktioniert und meine Tests sind vorbei, aber ich erkannte, dass in der Merge Funktion, wenn ich dies tun:

using type = typename std::conditional<Compare<L1, R1>::value, 
             ..., 
             ...>::type; 

wird es beide Seiten des Zweiges instanziieren, nicht nur eine Seite. Das wird die Zeitkomplexität quadratischer (oder schlechter? Schluck) machen als n log n.

Wie kann ich das Kurzschlussverhalten des ternären Operators ? : in einem Template-Metaprogramm nachahmen, so dass nur die Arbeit auf einer Seite des Zweigs gemacht wird?

Tragischerweise kann ich C++ 17 if constexpr hier nicht verwenden, was perfekt wäre. Es hat arbeiten, in C++ 14, oder besser gesagt, die Teilmenge von 14 C durch gcc-5.4 ++ implementiert

---

Mein erster Gedanke war SFINAE zu verwenden wie so:

template <typename L1, typename R1, 
      typename <typename, typename> typename Compare, 
      typename TL, typename TR, 
      std::enable_if_t<Compare<L1, R1>::value> * dummy = nullptr> 
Concat<TypeList<L1>, Merge_s<TL, Concat<TypeList<R1>, TR>, C> merge_branch(); 

template <typename L1, typename R1, 
      typename <typename, typename> typename Compare, 
      typename TL, typename TR, 
      std::enable_if_t<!Compare<L1, R1>::value> * dummy = nullptr> 
Concat<TypeList<R1>, Merge_s<Concat<TypeList<L1>, TL>, TR, C> merge_branch(); 

Aber ich bin mir nicht sicher, ob dies tatsächlich wie vorgesehen funktioniert - wenn der Vorlagenparameterabzug bei dummy oben fehlschlägt, wird das verhindern, dass der Compiler den Rückgabetyp instanziiert? Sollte ich eine zusätzliche Ebene der Umleitung verwenden (würde das sogar helfen?)

Es wurde vorgeschlagen, dass ich Tag Versand anstelle von SFINAE verwenden könnte.

Erfolgen die Template-Instanziierungen als Nebenprodukt der Überladungsauflösung oder erst nach Abschluss der Überladungsauflösung?

Ich fürchte die Antwort ist, als Nebenprodukt der Überladung Auflösung.

Tun gcc und clang früh aus Vorlagen instanziieren, wenn der Parameter dummy oben fehlschlägt, oder würden sie immer den Rückgabetyp instanziieren?

---

Hier ist meine MVCE:

#include <cstddef> 
#include <type_traits> 
#include <utility> 

template <typename ... Ts> 
struct TypeList { 
    static constexpr size_t size = sizeof...(Ts); 
}; 

// Metafunction First: Get first type from a typelist 
template<typename T> 
struct First_s; 

template<typename T, typename... TL> 
struct First_s <TypeList<T, TL...>> { 
    using type = T; 
}; 

template<typename T> 
using First = typename First_s<T>::type; 

// Metafunction Concat: Concatenate two typelists 
template<typename L, typename R> 
struct Concat_s; 

template<typename... TL, typename... TR> 
struct Concat_s <TypeList<TL...>, TypeList<TR...>> { 
    using type = TypeList<TL..., TR...>; 
}; 

template<typename L, typename R> 
using Concat = typename Concat_s<L,R>::type; 


// Metafunction Split: Split a typelist at a particular index 
template<int i, typename TL> 
struct Split; 

template<int k, typename... TL> 
struct Split<k, TypeList<TL...>> { 
private: 
    using FirstSplit = Split<k/2, TypeList<TL...>>; 
    using SecondSplit = Split<k-k/2, typename FirstSplit::R>; 
public: 
    using L = Concat<typename FirstSplit::L, typename SecondSplit::L>; 
    using R = typename SecondSplit::R; 
}; 

template<typename T, typename... TL> 
struct Split<0, TypeList<T, TL...>> { 
    using L = TypeList<>; 
    using R = TypeList<T, TL...>; 
}; 

template<typename T, typename... TL> 
struct Split<1, TypeList<T, TL...>> { 
    using L = TypeList<T>; 
    using R = TypeList<TL...>; 
}; 

template<int k> 
struct Split<k, TypeList<>> { 
    using L = TypeList<>; 
    using R = TypeList<>; 
}; 

// Metafunction Subdivide: Split a typelist into two roughly equal typelists 
template<typename TL> 
struct Subdivide : Split<TL::size/2, TL> {}; 

// Metafunction Reverse: Reverse a typelist 
template <typename TL> 
struct Reverse_s { 
    using S = Subdivide<TL>; 
    using type = Concat<typename Reverse_s<typename S::R>::type, 
         typename Reverse_s<typename S::L>::type>; 
}; 

template <typename T> 
struct Reverse_s<TypeList<T>> { 
    using type = TypeList<T>; 
}; 

template <> 
struct Reverse_s<TypeList<>> { 
    using type = TypeList<>; 
}; 

template <typename TL> 
using Reverse = typename Reverse_s<TL>::type; 

// Metafunction MergeSort: Mergesort a typelist, using a comparator C 

// Merge takes two type lists, and a comparator metafunction. 
// The comparator should take two type parameters and declare `static constexpr bool value = ...` 
template <typename TL, typename TR, template <typename, typename> class C> 
struct Merge_s; 

// TODO: Use SFINAE for the branch here because std::conditional does not short circuit :(
/* 
template <typename L1, typename R1, typename <typename, typename> typename C, typename TL, typename TR, std::enable_if_t<C<L1, R1>::value> * dummy = nullptr> 
Concat<TypeList<L1>, Merge_s<TL, Concat<TypeList<R1>, TR>, C> merge_branch(); 

template <typename L1, typename R1, typename <typename, typename> typename C, typename TL, typename TR, std::enable_if_t<!C<L1, R1>::value> * dummy = nullptr> 
Concat<TypeList<R1>, Merge_s<Concat<TypeList<L1>, TL>, TR, C> merge_branch(); 
*/ 

template <template <typename, typename> class C> 
struct Merge_s<TypeList<>, TypeList<>, C> { 
    using type = TypeList<>; 
}; 

template <typename L1, typename ... Ls, template <typename, typename> class C> 
struct Merge_s<TypeList<L1, Ls...>, TypeList<>, C> { 
    using type = TypeList<L1, Ls...>; 
}; 

template <typename R1, typename ... Rs, template <typename, typename> class C> 
struct Merge_s<TypeList<>, TypeList<R1, Rs...>, C> { 
    using type = TypeList<R1, Rs...>; 
}; 

template <typename L1, typename R1, template <typename, typename> class C, typename TL, typename TR> 
using merge_branch = typename std::conditional<C<L1, R1>::value, 
       Concat<TypeList<L1>, typename Merge_s<TL, Concat<TypeList<R1>, TR>, C>::type>, 
       Concat<TypeList<R1>, typename Merge_s<Concat<TypeList<L1>, TL>, TR, C>::type>>::type; 

template <typename L1, typename... Ls, typename R1, typename ... Rs, template <typename, typename> class C> 
struct Merge_s<TypeList<L1, Ls...>, TypeList<R1, Rs...>, C> { 
    using type = merge_branch<L1, R1, C, TypeList<Ls...>, TypeList<Rs...>>; 
}; 

template <typename TL, typename TR, template <typename, typename> class C> 
using Merge = typename Merge_s<TL, TR, C>::type; 

// Here is merge sort 
template <typename T, template <typename, typename> class C> 
struct MergeSort_s; 

template <template <typename, typename> class C> 
struct MergeSort_s<TypeList<>, C> { 
    using type = TypeList<>; 
}; 

template <typename T, template <typename, typename> class C> 
struct MergeSort_s<TypeList<T>, C> { 
    using type = TypeList<T>; 
}; 

template <typename T, typename... Ts, template <typename, typename> class C> 
struct MergeSort_s <TypeList<T, Ts...>, C>{ 
    using S = Subdivide<TypeList<T, Ts...>>; 
    using L = typename MergeSort_s<typename S::L, C>::type; 
    using R = typename MergeSort_s<typename S::R, C>::type; 
    using type = Merge<L, R, C>; 
}; 

template <typename T, template <typename, typename> class C> 
using MergeSort = typename MergeSort_s<T, C>::type; 


// Tests 

struct A{}; 
struct B{}; 
struct C{}; 


// Concat tests 
static_assert(std::is_same<TypeList<A, B, C>, // 
          Concat<TypeList<>, TypeList<A, B, C>>>::value, ""); // 
static_assert(std::is_same<TypeList<A, B, C>, // 
          Concat<TypeList<A>, TypeList<B, C>>>::value, ""); // 
static_assert(std::is_same<TypeList<A, B, C>, // 
          Concat<TypeList<A, B>, TypeList<C>>>::value, ""); // 
static_assert(std::is_same<TypeList<A, B, C>, // 
          Concat<TypeList<A, B, C>, TypeList<>>>::value, ""); // 

// Split tests 
static_assert(std::is_same<TypeList<A>, // 
          typename Split<1, TypeList<A, B, C>>::L>::value, ""); // 
static_assert(std::is_same<TypeList<B, C>, // 
          typename Split<1, TypeList<A, B, C>>::R>::value, ""); // 

static_assert(std::is_same<TypeList<A, B>, // 
          typename Split<2, TypeList<A, B, C>>::L>::value, ""); // 
static_assert(std::is_same<TypeList<C>, // 
          typename Split<2, TypeList<A, B, C>>::R>::value, ""); // 

// Reverse tests 

static_assert(std::is_same<TypeList<B, A>, // 
          Reverse<TypeList<A, B>>>::value, ""); // 
static_assert(std::is_same<TypeList<C, B, A>,// 
          Reverse<TypeList<A, B, C>>>::value, ""); // 

// Sorting tests 

template <typename T1, typename T2> 
struct IntCmp; 

template <int a, int b> 
struct IntCmp<std::integral_constant<int, a>, std::integral_constant<int, b>> { 
    static constexpr bool value = (a < b); 
}; 

template <int x> 
using IntC = std::integral_constant<int, x>; 

static_assert(std::is_same<TypeList<IntC<1>, IntC<2>>, // 
          MergeSort<TypeList<IntC<1>, IntC<2>>, IntCmp>>::value, ""); // 

static_assert(std::is_same<TypeList<IntC<1>, IntC<2>>,// 
          MergeSort<TypeList<IntC<2>, IntC<1>>, IntCmp>>::value, "");// 

static_assert(std::is_same<TypeList<IntC<1>, IntC<2>, IntC<3>>,// 
          MergeSort<TypeList<IntC<3>, IntC<1>, IntC<2>>, IntCmp>>::value, "");// 

static_assert(std::is_same<TypeList<IntC<1>, IntC<2>, IntC<3>>,// 
          MergeSort<TypeList<IntC<1>, IntC<3>, IntC<2>>, IntCmp>>::value, "");// 

static_assert(std::is_same<TypeList<IntC<1>, IntC<2>, IntC<3>>,// 
          MergeSort<TypeList<IntC<2>, IntC<3>, IntC<1>>, IntCmp>>::value, "");// 

static_assert(std::is_same<TypeList<IntC<1>, IntC<2>, IntC<3>>,// 
          MergeSort<TypeList<IntC<1>, IntC<2>, IntC<3>>, IntCmp>>::value, "");// 

static_assert(std::is_same<TypeList<IntC<1>, IntC<2>, IntC<3>>,// 
          MergeSort<TypeList<IntC<2>, IntC<1>, IntC<3>>, IntCmp>>::value, "");// 

static_assert(std::is_same<TypeList<IntC<1>, IntC<2>, IntC<3>>,// 
          MergeSort<TypeList<IntC<1>, IntC<2>, IntC<3>>, IntCmp>>::value, "");// 

static_assert(std::is_same<TypeList<IntC<1>, IntC<2>, IntC<3>, IntC<4>>,// 
          MergeSort<TypeList<IntC<1>, IntC<2>, IntC<3>, IntC<4>>, IntCmp>>::value, "");// 

static_assert(std::is_same<TypeList<IntC<1>, IntC<2>, IntC<3>, IntC<4>>,// 
          MergeSort<TypeList<IntC<3>, IntC<4>, IntC<2>, IntC<1>>, IntCmp>>::value, "");// 

---

Namensnennung: Einige der Details in der oben Yakk's comments in eine andere Antwort

Answer 1

Ich schlage vor, informiert ein Helfer struct Korbdurchschub- mit Teilspezialisierung

template <typename L1, typename R1, template <typename, typename> class C, 
      typename TL, typename TR, bool = C<L1, R1>::value> 
struct merge_branch_h 
{ using type = Concat<TypeList<L1>, 
     typename Merge_s<TL, Concat<TypeList<R1>, TR>, C>::type>; }; 

template <typename L1, typename R1, template <typename, typename> class C, 
      typename TL, typename TR> 
struct merge_branch_h<L1, R1, C, TL, TR, false> 
{ using type = Concat<TypeList<R1>, 
     typename Merge_s<Concat<TypeList<L1>, TL>, TR, C>::type>; }; 

template <typename L1, typename R1, template <typename, typename> class C, 
      typename TL, typename TR> 
using merge_branch = typename merge_branch_h<L1, R1, C, TL, TR>::type; 

Answer 2

Fügen Sie eine zusätzliche Indirektion hinzu. Boost.MPL hatte diese Metafunktion namens eval_if, die wie conditional ist, außer, anstatt zwei Typen zu nehmen, benötigt es zwei Metafunktionen und wertet das eine oder andere aus.Es ist extrem einfach zu implementieren:

template <bool B, typename T1, typename T2> 
using eval_if = typename std::conditional<B, T1, T2>::type::type; 

Werfen wir also einen metafunction Fügen Sie Ihre Verkettung/Merge:

template <typename T> 
struct identity { 
    using type = T; 
}; 

template <typename L, typename R> 
struct delay_concat { 
    using type = Concat<typename L::type, typename R::type>; 
}; 

Und dann können Sie tauschen Ihre:

typename std::conditional<C<L1, R1>::value, 
    Concat<TypeList<L1>, typename Merge_s<TL, Concat<TypeList<R1>, TR>, C>::type>, 
    Concat<TypeList<R1>, typename Merge_s<Concat<TypeList<L1>, TL>, TR, C>::type> 

mit:

eval_if<C<L1, R1>::value, 
    delay_concat<identity<TypeList<L1>>, Merge_s<TL, Concat<TypeList<R1>, TR>, C>>, 
    delay_concat<identity<TypeList<R1>>, Merge_s<Concat<TypeList<L1>, TL>, TR, C>>> 

was kurz ist Schaltung.

---

die wahrscheinlich verallgemeinern sollten:

template <template <typename...> class Z, typename... Ts> 
struct delay_eval { 
    using type = Z<typename Ts::type...>; 
}; 

Und dann machen TypeList ein metafunction, der sich ergibt, so haben wir nicht sie in identity wickeln. Dies ermöglicht:

eval_if<C<L1, R1>::value, 
    delay_eval<Concat, TypeList<L1>, delay_eval<Merge_s, TL, delay_eval<Concat, TypeList<R1>, TR>, C>>, 
    delay_eval<Concat, TypeList<R1>, delay_eval<Merge_s, delay_eval<Concat, TypeList<L1>, TL>, TR, C>>>