C++ 元编程为树结构分配唯一 ID

Question

我有一个奇怪的问题。我有一个像这样定义的元编程类型:

template <int N, typename... Args>
struct mytype {
    ...
};

默认情况下，我这样创建它们:

using type = mytype<-1, mytype<-1, mytype<-1, ...>>>;

或者:

using type = mytype<-1, mytype<-1, ...>, mytype<-1, mytype<-1, ...>>>;

稍后，我需要递归该类型并将每个数字递归设置为唯一的 ID。出于长期的技术原因，ID 需要是连续的并且从 0 开始。例如，如果我有这个:

mytype<-1
    mytype<-1, a, b>
>

我希望它变成这样:

mytype<0,
    mytype<1, a, b>
>

数字分配的顺序并不重要。

我不太知道如何解决这个问题，并且尝试了一些没有任何进展的方法。任何帮助将不胜感激。

Answer 1

基本思想:

1. 对 mytype 中的可变参数包进行模板递归，也就是说，元函数应该在处理列表中的第一个类型之前或之后使用更少的参数调用自身。
2. 使用的类型不仅可以跟踪结果类型，还可以跟踪计数器的下一个值。在完全递归遍历子树后，您需要记住计数器的新值，因为这是下一个子树(或当前节点)的起始值。所以你的元函数也需要返回它。

这是我的解决方案，它在后序中分配 ID(并且可能比需要的更复杂):

#include <type_traits>

template <int placeholder, typename... Args>
struct mytype {};

using type = mytype<-1, mytype<-1, int, float>, mytype<-1, char, double>>;
using result = mytype<2, mytype<0, int, float>, mytype<1, char, double>>;

// This helper type is used to keep track of the next counter value
template <int c, typename T>
struct type_with_counter {
  static constexpr int counter = c;
  typedef T type;
};

template <typename T> struct assign_ids_helper;

// Base case: we have no mytype and no placeholders to assign, so just give
// back the original type and leave the counter alone.
template <int c, typename T>
struct assign_ids_helper<type_with_counter<c, T>> {
  typedef type_with_counter<c, T> result;
};

// Base case: we have a mytype with no children; assign the placeholder and
// increment the counter.
template <int c, int placeholder>
struct assign_ids_helper<type_with_counter<c, mytype<placeholder>>> {
  typedef type_with_counter<c+1, mytype<c>> result;
};

// Recursive case: one or more children.
template <int c, int placeholder, typename head, typename... tail>
struct assign_ids_helper<type_with_counter<c, mytype<placeholder, head, tail...>>> {
  // Recurse into the first type.
  typedef typename assign_ids_helper<type_with_counter<c, head>>::result head_result;
  // Now use the updated counter to recurse on the tail.
  typedef typename assign_ids_helper<type_with_counter<head_result::counter, mytype<placeholder, tail...>>>::result tail_result;
  // The new type will be given by inserting the head into the tail
  template <typename, typename> struct cons;
  template <int id, typename head_, typename... tail_>
  struct cons<head_, mytype<id, tail_...>> {
    typedef mytype<id, head_, tail_...> result;
  };
  typedef typename cons<typename head_result::type, typename tail_result::type>::result type;
  typedef type_with_counter<tail_result::counter, type> result;
};

template <typename T>
using assign_ids = typename assign_ids_helper<type_with_counter<0, T>>::result::type;

int main() {
  static_assert(std::is_same<assign_ids<type>, result>::value, "");
}

(链接:http://coliru.stacked-crooked.com/a/1d9507359e9ebc07)

@T.C.评论里也贴出了解决方案，看起来比较简单。