使用 C++17 可变参数模板在编译时遍历树

Question

我目前正在研究使用 C++ (C++17) 可变参数模板来生成高效、实时的电路仿真。

我的目标是利用可变参数模板定义一个可以在编译时遍历的树。为了定义这样一棵树，我使用了以下三个结构：

template <auto Tag> struct Leaf
{
    static constexpr auto tag = Tag;
};

template <typename ... Children> struct Branch
{
    static constexpr auto child_count = sizeof ... (Children);
    
    template <typename Lambda> constexpr void for_each_child(Lambda && lambda)
    {
        // TODO: Execute 'lambda' on each child.
    }
    
    std::tuple<Children ...> m_children {};
};

template <typename Root> struct Tree
{
    template <auto Tag> constexpr auto & get_leaf()
    {
        // TODO: Traverse the tree and find the leaf with tag 'Tag'.
        
        // If there's no leaf with tag 'Tag' the program shouldn't compile.
    }
    
    Root root {};
};

利用上面树的定义，我们可以定义一组电路元件如下：

template <auto Tag> struct Resistor : Leaf<Tag>
{
    float resistance() { return m_resistance; }
    
    float m_resistance {};
};

template <auto Tag> struct Capacitor : Leaf<Tag>
{
    float resistance() { return 0.0f; }
    
    float m_capacitance {};
};

template <typename ... Children> struct Series : Branch<Children ...>
{
    using Branch<Children ...>::for_each_child;
    
    float resistance()
    {
        float acc = 0.0f;
        
        for_each_child([&acc](auto child) { acc += child.resistance(); });
        
        return acc;
    }
};

template <typename ... Children> struct Parallel : Branch<Children ...>
{
    using Branch<Children ...>::for_each_child;
    
    float resistance()
    {
        float acc = 0.0f;
        
        for_each_child([&acc](auto child) { acc += 1.0f / child.resistance(); });
        
        return 1.0f / acc;
    }
};

接下来，利用上面的元件，我们可以这样表达一个具体的电路：

enum { R0, R1, C0, C1 };

using Circuit =
    Tree<
        Parallel<
            Series<
                Resistor<R0>,
                Capacitor<C0>
            >, // Series
            Series<
                Resistor<R0>,
                Capacitor<C1>
            > // Series
        > // Parallel
    >; // Tree

...其中 R0、R1、C0 和 C1 是我们在编译时用于访问组件的标签。例如。一个非常基本的用例可能如下：

int main()
{
    Circuit circuit {};
    
    circuit.get_leaf<R0>().m_resistance  =  5.0E+3f;
    circuit.get_leaf<C0>().m_capacitance = 10.0E-3f;
    circuit.get_leaf<R1>().m_resistance  =  5.0E+6f;
    circuit.get_leaf<C1>().m_capacitance = 10.0E-6f;
    
    std::cout << circuit.root.resistance() << std::endl;
}

我只是想不通的是如何实现函数 for_each_child 和 get_leaf.我尝试过使用 if-constexpr 语句和模板结构的不同方法，但没有找到好的解决方案。可变参数模板很有趣，但同时又令人望而生畏。任何帮助将不胜感激。

Answer 1

for_each_child 与 std::index_sequence.

相当简单

template <typename ... Children> struct Branch
{
    using indexes = std::index_sequence_for<Children...>;
    static constexpr auto child_count = sizeof... (Children);
    
    template <typename Lambda> constexpr void for_each_child(Lambda && lambda)
    {
        for_each_child_impl(std::forward<Lambda>(lambda), indexes{});
    }
    
    std::tuple<Children ...> m_children {};

private:
    template <typename Lambda, std::size_t... Is> constexpr void for_each_child_impl(Lambda && lambda, std::index_sequence<Is...>)
    {
        (lambda(std::get<Is>(m_children)), ...);
    }
};

get_leaf 稍微有点棘手。首先，我们计算出到达所需叶子的路径，然后我们遵循 root.

的路径

template <std::size_t I, typename>
struct index_sequence_cat;

template <std::size_t I, std::size_t... Is>
struct index_sequence_cat<I, std::index_sequence<Is...>> {
    using type = std::index_sequence<I, Is...>;
};

template <std::size_t I, typename Ix>
using index_sequence_cat_t = typename index_sequence_cat<I, Ix>::type;

template<typename, auto Tag, typename, std::size_t... Is> 
struct leaf_index {};

template<auto Tag, typename T, std::size_t... Is> 
using leaf_index_i = typename leaf_index<void, Tag, T, Is...>::index;

template<auto Tag, std::size_t I> 
struct leaf_index<void, Tag, Leaf<Tag>, I> {
    using index = std::index_sequence<I>;
};

template<typename, auto, std::size_t, typename...>
struct branch_index {};

template<auto Tag, std::size_t I, typename... Args>
using branch_index_i = typename branch_index<void, Tag, I, Args...>::index;

template<auto Tag, std::size_t I, typename First, typename... Args>
struct branch_index<std::void_t<leaf_index_i<Tag, First, I>>, Tag, I, First, Args...> {
    using index = leaf_index_i<Tag, First, I>;
};

template<auto Tag, std::size_t I, typename First, typename... Args>
struct branch_index<std::void_t<branch_index_i<Tag, I + 1, Args...>>, Tag, I, First, Args...> {
    using index = branch_index_i<Tag, I + 1, Args...>;
};

template<auto Tag, typename... Children, std::size_t I> 
struct leaf_index<void, Tag, Branch<Children...>, I> {
    using index = index_sequence_cat_t<I, branch_index_i<Tag, 0, Children...>>;
};

template<auto Tag, typename... Children> 
struct leaf_index<std::void_t<branch_index_i<Tag, 0, Children...>>, Tag, Branch<Children...>> {
    using index = branch_index_i<Tag, 0, Children...>;
};

template <typename Root> struct Tree
{
    template <auto Tag> constexpr auto & get_leaf()
    {
        return get_leaf(leaf_index<Tag, root>{});
    }
    
    Root root {};
private:
    template <std::size_t... Is>
    auto & get_leaf(std::index_sequence<Is...>)
    {
        return get_leaf<Is...>(root);
    }

    template<std::size_t I, typename T>
    auto& get_leaf(T & branch)
    {
        return std::get<I>(branch.m_children);
    }
    
    template<std::size_t I, std::size_t J, std::size_t... Is, typename T>
    auto& get_leaf(T & branch)
    {
        return get_leaf<J, Is...>(std::get<I>(branch.m_children));
    }
};

Answer 2

在研究了有关 C++ 可变参数模板的各种文章之后，我设法修补了该问题的解决方案。

首先，为了实现 for_each_child，我们使用以下辅助函数作为 for-loop，即 un-rolled 在 compile-time:

template <auto from, auto to, typename Lambda>
    static inline constexpr void for_constexpr(Lambda && lambda)
{
    if constexpr (from < to)
    {
        constexpr auto i = std::integral_constant<decltype(from), from>();
        
        lambda(i);
        
        for_constexpr<from + 1, to>(lambda);
    }
}

通过使用这个辅助函数，我们可以实现 for_each_child 如下：

template <typename ... Children> struct Branch
{
    static constexpr auto children_count = sizeof ... (Children);

    template <typename Lambda> constexpr void for_each_child(Lambda && lambda)
    {
        for_constexpr<0, children_count>([lambda, this](auto i)
        {
            lambda(std::get<i>(m_children));
        });
    }
    
    std::tuple<Children ...> m_children {};
};

下一步，为了实现get_leaf，我们使用了一堆不同的辅助函数。由于Caleth ，我们可以将问题分为两步。首先，我们计算从根到所需叶子的路径；之后，我们可以按照该路径从树中提取叶子。

路径可以表示为索引序列，如下所示：

template <auto ...indices> using Path = std::index_sequence<indices...>;

我们需要的第一个辅助函数检查 node 是否有一个带有给定 tag:

的叶子

template <auto tag, class Node> struct has_path
{
    static constexpr
        std::true_type
            match(const Leaf<tag>);
    
    template <class ...Children> static constexpr
        typename std::enable_if<
            (has_path<tag, Children>::type::value || ...),
            std::true_type
        >::type
            match(const Branch<Children...>);
    
    static constexpr
        std::false_type
            match(...);
    
    using type = decltype(match(std::declval<Node>()));
};

我们只是在节点上进行模式匹配。如果它是一片叶子，我们必须确保它有正确的标签。并且，如果它是一个分支，我们需要确保其中一个 children 有一个带有标签的叶子。

下一个辅助函数有点复杂：

template <auto tag, class Node, auto ...indices> struct find_path
{
    template <auto index, class Child, class ...Children> struct search_children
    {
        static constexpr auto fold()
        {
            if constexpr(has_path<tag, Child>::type::value)
            {
                return typename find_path<tag, Child, indices..., index>::type();
            }
            else
            {
                return typename search_children<index + 1, Children...>::type();
            }
        }
        
        using type = decltype(fold());
    };
    
    static constexpr
        Path<indices...>
            match(const Leaf<tag>);
    
    template <class ...Children> static constexpr
        typename search_children<0, Children...>::type
            match(const Branch<Children...>);
    
    using type = decltype(match(std::declval<Node>()));
};

我们在indices模板参数中累积路径。如果我们正在调查的节点（通过模板参数 Node）是一片叶子，我们检查它是否有正确的标签，如果是，return 累积路径。相反，如果节点是一个分支，我们必须使用辅助函数 search_children 来遍历分支中的所有 children。对于每个 child，我们首先检查 child 是否有一个带有给定标签的叶子。如果是这样，我们将当前索引（由模板参数 index 给出）附加到累积路径并在 child 上递归调用 find_path。如果 child 没有带有给定标签的叶子，我们尝试下一个 child，依此类推。

最后，我们定义了一个可以提取给定路径的叶子的辅助函数：

template <class Node>
    static inline constexpr auto &
        get(Node & leaf, Path<> path)
{
    return leaf;
}

template <auto index, auto ...indices, class Node>
    static inline constexpr auto &
        get(Node & branch, Path<index, indices...> path)
{
    auto & child = std::get<index>(branch.m_children);
    
    return get(child, Path<indices...>());
}

使用find_path和get我们可以实现get_leaf如下：

template <typename Root> struct Tree
{
    template <auto tag> constexpr auto & get_leaf()
    {
        constexpr auto path = typename implementation::find_path<tag, Root>::type {};
        
        return implementation::get(root, path);
    }
    
    Root root;
};

这里有一个 link 到 godbolt.org，它证明了代码可以按预期使用 Clang 进行编译和工作：

godbolt.org/...

使用 C++17 可变参数模板在编译时遍历树

Traversing trees at compile time with C++17 Variadic Templates

c++

templates

c++17

metaprogramming

variadic-templates