文章/答案/技术大牛

发布

社区首页 >问答首页 >如何在模板元程序中执行短路条件？

问如何在模板元程序中执行短路条件？
EN

Stack Overflow用户

提问于 2017-11-28 18:52:51

回答 2查看 270关注 0票数 1

我正在模板元程序中实现合并排序。(信不信由你，我们在生产中有一个真正的用例。)

我的代码正在工作，我的测试正在通过，但是当我这样做时，我意识到在Merge函数中：

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

它将实例化分支的两侧，而不仅仅是一侧。这会使时间复杂度二次(或者更糟？)而不是n log n。

如何在模板元程序中模拟三元算子? :的短路行为，从而只完成分支一侧的工作？

不幸的是，我不能在这里使用C++17 if constexpr，这将是完美的。它必须在C++14中工作，或者更确切地说，是gcc-5.4实现的C++14的子集。

我最初的想法是这样使用SFINAE：

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

但是，我不确定这是否真的会按预期工作--当模板参数在上面的dummy中失败时，这会阻止编译器实例化返回类型吗？我应该使用额外的间接(这甚至有帮助吗？)

有人建议我可以用标签发送代替SFINAE。

模板实例化是作为过载解析的副产品发生的，还是只在过载解析完成之后发生？

我担心答案是，作为过载解决方案的副产品。

当参数dummy 在参数上失败时，gcc和clang是否会提前从实例化模板中退出，或者它们是否总是实例化返回类型？

这是我的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, "");//

归因:以上部分细节由Yakk's comments在另一个答案中提供。

templates

c++14

template-meta-programming

short-circuiting

c++

回答 2

Stack Overflow用户

回答已采纳

发布于 2017-11-28 19:14:07

我建议通过一个具有部分专门化的助手结构。

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;

票数 1

Stack Overflow用户

发布于 2017-11-28 19:17:21

增加一个额外的间接层。Boost.MPL有一个称为eval_if的元功能，它类似于conditional，除了采用两种类型以外，它需要两种髓元功能，并对其中一种或另一种进行评估。它非常容易实现：

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

因此，让我们添加一个元功能，进行连接/合并：

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

然后你可以交换你的：

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>

通过以下方式：

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

它会短路。

这可能会概括为：

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

然后使TypeList成为一个产生自身功能的元函数，因此我们不必将它们封装在identity中。这样可以：

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

票数 2

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/47538917

复制

相似问题

问如何在模板元程序中执行短路条件？
EN

回答 2

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问如何在模板元程序中执行短路条件？EN

回答 2

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问如何在模板元程序中执行短路条件？
EN