如何使用 Boost.MP11 避免不必要的实例化

Question

我使用自己的 TMP 库已经有一段时间了。但是，我想开始使用Boost.MP11. 界面非常漂亮，为了给自己一些学习它的动力，我在编译时尽可能多地使用Boost.MP11.

然而，有些事情是我必须做的，但我不喜欢。我回去清理了一些东西，有一个地方我仍然有点困惑，那就是如何防止不必要的实例化。我确信使用 mp_valid 是可行的方法，但我可以使用一些指导。

例如，考虑以下push_heap, using的实现Boost.MP11（我将其作为实现 Dijkstra 算法以应对挑战之一的一部分来实现）。

为了使我想要实现的目标变得明显，即仅当模板为真时才实例化模板，它有点冗长。

我一定是误解了一些东西Boost.MP11，所以我想看到一个优雅的Boost.MP11实现push_heap。

template <typename IndexT>
using parent = mp_constant<(IndexT::value - 1) / 2>;

template <typename ListT, typename IndexT> struct BubbleUp;

template <
    typename ListT,
    typename IndexT,
    typename CondT = mp_less<
        mp_at<ListT, parent<IndexT>>,
        mp_at<ListT, IndexT>>>
struct BubbleUpImpl
: BubbleUp<
    mp_replace_at<
        mp_replace_at<ListT, IndexT, mp_at<ListT, parent<IndexT>>>,
        parent<IndexT>,
        mp_at<ListT, IndexT>>,
    parent<IndexT>>
{ };
template <typename ListT, typename IndexT>
struct BubbleUpImpl<ListT, IndexT, mp_false>
{
    using type = ListT;
};

template <typename ListT, typename IndexT>
struct BubbleUp
: BubbleUpImpl<ListT, IndexT>
{ };
template <typename ListT>
struct BubbleUp<ListT, mp_size_t<0>>
{
    using type = ListT;
};

// Not same as std::push_heap - it pushes and heapifies
template <typename ListT, typename T>
using push_heap = typename BubbleUp<
    mp_push_back<ListT, T>,
    mp_size<ListT>>::type;

---

编辑

这是我对 的尝试Boost.MP11，但我不太喜欢它，仍在寻找更好的替代方案，并且特别有兴趣学习如何最好地用 来做这些事情Boost.MP11。请注意，这里的语义与std::push_heap上面的区别是尝试和简化。

namespace heap_detail {

template <typename ListT, typename Index1T, typename Index2T>
using swap_at = mp_replace_at<
    mp_replace_at<ListT, Index1T, mp_at<ListT, Index2T>>,
    Index2T,
    mp_at<ListT, Index1T>>;

template <typename CmpQ>
class PushHeap
{
    template <typename T>
    using heap = mp_first<T>;

    template <typename T>
    using child = mp_second<T>;

    template <typename T>
    using parent = mp_if<
        mp_less<mp_size_t<0>, child<T>>,
        mp_constant<(child<T>::value - 1) / 2>>;

    template <typename T>
    using bubble_up = mp_list<
        mp_if<
            mp_invoke_q<
                CmpQ,
                mp_at<heap<T>, parent<T>>,
                mp_at<heap<T>, child<T>>>,
            swap_at<heap<T>, parent<T>, child<T>>>,
        parent<T>>;

public:
    template <typename ListT>
    using fn = mp_back<mp_iterate<
        mp_list<ListT, mp_minus<mp_size<ListT>, mp_int<1>>>,
        mp_first,
        bubble_up>>;
};
} // namespace heap_detail

template <typename ListT, typename CmpQ>
using push_heap_q = mp_invoke_q<heap_detail::PushHeap<CmpQ>, ListT>;

template <typename ListT, template <typename...> class Cmp = mp_less>
using push_heap = push_heap_q<ListT, mp_quote<Cmp>>;

另外，就其价值而言，这里是堆接口的其余部分。也许这些将展示更多学习如何更好地使用的机会Boost.MP11。

生成堆

template <typename ListT, typename CmpQ>
using make_heap_q = mp_fold_q<
    ListT,
    mp_list<>,
    mp_compose_q<mp_quote<mp_push_back>, mp_bind_back<push_heap_q, CmpQ>>>;

template <typename ListT, template <typename...> class Cmp = mp_less>
using make_heap = make_heap_q<ListT, mp_quote<Cmp>>;

以及将其他项目推入堆的东西

template <typename ListT, typename CmpQ, typename... Ts>
using heap_push_back_q = mp_fold_q<
    mp_list<Ts...>,
    ListT,
    mp_compose_q<mp_quote<mp_push_back>, mp_bind_back<push_heap_q, CmpQ>>>;

而且pop_heap，这似乎过于复杂 - 专业化似乎更容易阅读和编写，所以，我相信我错过了一些基本的东西Boost.MP11。

template <typename CmpQ>
class PopHeap
{
    template <typename T>
    using heap = mp_first<T>;

    template <typename T>
    using parent = mp_second<T>;

    template <typename T>
    using left_child = mp_constant<parent<T>::value * 2 + 1>;

    template <typename T>
    using right_child = mp_constant<parent<T>::value * 2 + 2>;

    template <typename T>
    using child_to_swap = mp_eval_or_q<
        left_child<T>,
        mp_quote<mp_if>,
        mp_invoke_q<
            CmpQ,
            mp_at<heap<T>, left_child<T>>,
            mp_at<heap<T>, right_child<T>>>,
        right_child<T>,
        left_child<T>>;

    template <typename T>
    using bubble_down = mp_list<
        mp_if<
            mp_invoke_q<
                CmpQ,
                mp_at<heap<T>, parent<T>>,
                mp_at<heap<T>, child_to_swap<T>>>,
            swap_at<heap<T>, parent<T>, child_to_swap<T>>>,
        child_to_swap<T>>;

public:
    template <typename ListT>
    using fn = mp_push_back<
        mp_back<
            mp_iterate<
                mp_list<
                    mp_rotate_right<mp_pop_front<ListT>, mp_int<1>>,
                    mp_size_t<0>>,
                mp_first,
                bubble_down>>,
        mp_first<ListT>>;
};

template <typename ListT, typename CmpQ>
using pop_heap_q = mp_invoke_q<heap_detail::PopHeap<CmpQ>, ListT>;

template <typename ListT, template <typename...> class Cmp = mp_less>
using pop_heap = pop_heap_q<ListT, mp_quote<Cmp>>;