c++ - Traversing trees at compile time with C++17 Variadic Templates
问题描述
I'm currently looking into using C++ (C++17) variadic templates for generating efficient, real-time simulations of circuits.
My goal is to leverage variadic templates to define a tree that can be traversed at compile-time. To define such a tree, I use the following three structs:
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 {};
};
Using the above definition of a tree, we can define a set of circuit components as follows:
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;
}
};
Next, using the above components, we can express a specific circuit like this:
enum { R0, R1, C0, C1 };
using Circuit =
Tree<
Parallel<
Series<
Resistor<R0>,
Capacitor<C0>
>, // Series
Series<
Resistor<R0>,
Capacitor<C1>
> // Series
> // Parallel
>; // Tree
...where R0, R1, C0, and C1 are tags that we use for accessing components at compile time. E.g. a very basic use case could be the following:
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;
}
What I just can't wrap my head around is how to implement the functions for_each_child and get_leaf. I've tried different approaches using if-constexpr statements and template-structs without finding a good solution. Variadic templates are interesting but daunting at the same time. Any help would be greatly appreciated.
解决方案
for_each_child
is fairly simple with 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
is slightly trickier. First we work out what the path is to the desired leaf, then we follow the path from 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));
}
};
推荐阅读
- installation - Gentoo 软件包掩码不适用于确切的版本号
- java - 为什么 Apache Spark 中的 Accuracy 和 Weighted Recall 值始终相同?
- c# - 如何将 ASCII 值转换回字符
- ios - UIStackView - 用动画隐藏和折叠子视图
- wordpress - Wordpress 支付插件站点范围的 Cookie 通过 Pantheon 防止清漆边缘缓存
- azure - 将应用服务从一个应用服务计划移动到另一个(相同的资源组和区域)
- c# - 如何在 ASP.NET MVC Web 应用程序中的两个表之间创建查询?
- inno-setup - Inno Setup 在自定义表单标题栏上使用不同的图标
- azure - .Net 客户端应用程序访问 Azure Data Lake 时出现 AccessControlException
- wordpress - 仅在同一 div 中包装两个帖子 - WP While 循环