How can I do short-circuiting conditionals in a template metaprogram?

Question

I am implementing a merge sort in template metaprogram. (Believe it or not, we have a real use case for this in production.)

My code is working and my tests are passing, however I realized that in the Merge function, when I do this:

using type = typename std::conditional::value,
                                       ...,
                                       ...>::type;

it is going to instantiate both sides of the branch, not just one side. That's going to make the time complexity quadratic (or worse? gulp) rather than n log n.

How can I imitate the short-circuiting behavior of ternary operator ? : in a template metaprogram, so that only the work of one side of the branch is done?

Tragically, I cannot use C++17 if constexpr here, which would be perfect. It has to work in C++14, or rather, the subset of C++14 implemented by gcc-5.4

My initial thought was to use SFINAE like so:

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

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

However, I'm not sure if this will actually work as intended -- when template parameter deduction fails at dummy above, will that prevent the compiler from instantiating the return type? Should I use an extra level of indirection (would that even help?)

It was suggested that I could use tag dispatch instead of SFINAE.

Do the template instantiations happen as a byproduct of overload resolution, or only after overload resolution is finished?

I fear the answer is, as a byproduct of overload resolution.

Do gcc and clang bail out early from instantiating templates when parameter dummy fails above, or would they always instantiate the return type?

Here's my MVCE:

#include 
#include 
#include 

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

// Metafunction First: Get first type from a typelist
template
struct First_s;

template
struct First_s > {
    using type = T;
};

template
using First = typename First_s::type;

// Metafunction Concat: Concatenate two typelists
template
struct Concat_s;

template
struct Concat_s , TypeList> {
   using type = TypeList;
};

template
using Concat = typename Concat_s::type;


// Metafunction Split: Split a typelist at a particular index
template
struct Split;

template
struct Split> {
private:
    using FirstSplit = Split>;
    using SecondSplit = Split;
public:
    using L = Concat;
    using R = typename SecondSplit::R;
};

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

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

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

// Metafunction Subdivide: Split a typelist into two roughly equal typelists
template
struct Subdivide : Split {};

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

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

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

template 
using Reverse = typename Reverse_s::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  class C>
struct Merge_s;

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

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

template

Barry · Accepted Answer

Add an extra layer of indirection. Boost.MPL had this metafunction called eval_if which is like conditional except instead of taking two types, it takes two nullary metafunctions and evaluates one or the other. It's extremely easy to implement:

template 
using eval_if = typename std::conditional::type::type;

So let's add a metafunction do your concatenation/merge:

template 
struct identity {
    using type = T;
};

template 
struct delay_concat {
    using type = Concat;
};

And then you can swap your:

typename std::conditional::value,
    Concat, typename Merge_s, TR>, C>::type>,
    Concat, typename Merge_s, TL>, TR, C>::type>

with:

eval_if::value,
    delay_concat>, Merge_s, TR>, C>>,
    delay_concat>, Merge_s, TL>, TR, C>>>

which does short circuit.

Which should probably generalize out to:

template

How can I do short-circuiting conditionals in a template metaprogram?

Answers (2)

Related Questions