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

基本思路：

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

这是我的解决方案，它按后序分配 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, "");
}

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

@T.C。也在评论里贴出了解决方案，貌似比较简单

Answer 2

基本思路和@Brian的回答一样：

元函数必须跟踪已使用的值（或等效地，下一个可用值）和结果类型。
由于列表中每个类型的处理都依赖于前一个类型，简单的包扩展是行不通的，需要递归处理

细微差别是我没有使用单独的计数器类型，而且我进行的是前序遍历而不是后序遍历。我也以不同的方式处理连接。

// This is the base case, used only when T is not a mytype.
// N is the next index available to be used.
// The third argument is used to hold types that has been processed
// during the recursion.
template<class T, int N = 0, class = mytype<-1>> struct assign_IDs {
    using type = T; 
    static constexpr int next_index = N;
};

// When we are starting to process a mytype.
template<class T, class...Ts, int N, int M1, int M2>
struct assign_IDs<mytype<M1, T, Ts...>, N, mytype<M2>> {
    // Process the first type in the list.
    // The first available index is N+1 since we are using N.
    using T_assigned = assign_IDs<T, N + 1>;

    // recursively process the next type
    using next = assign_IDs<mytype<N, Ts...>, T_assigned::next_index, mytype<N, typename T_assigned::type>>;

    using type = typename next::type;
    static constexpr int next_index = next::next_index;
};

// When we are in the middle of processing a mytype. The difference
// is that we won't consume an index any more.
template<class T, class...Ts, class... Vs,  int N, int M1, int M2>
struct assign_IDs<mytype<M1, T, Ts...>, N, mytype<M2, Vs...>> {

    // now the handling of T can start at N.
    using T_assigned = assign_IDs<T, N>;

    using next = assign_IDs<mytype<M1, Ts...>, T_assigned::next_index, mytype<M2, Vs..., typename T_assigned::type>>;

    using type = typename next::type;
    static constexpr int next_index = next::next_index;
};

// end of recursion: all types have been processed.
// The resulting type is just the third template argument.
template<class... Vs, int N, int M1, int M2>
struct assign_IDs<mytype<M1>, N, mytype<M2, Vs...>> {
    using type = mytype<M2, Vs...>;
    static constexpr int next_index = N;
};

Demo.

A postorder traversal 实际上会更容易实现，因为它少了一个偏特化：

// same as before
template<class T, int N = 0, class = mytype<-1>> struct assign_IDs {
    using type = T; 
    static constexpr int next_index = N;
};

// can merge case #2 and #3 because now the handling is the same
// as the index isn't consumed until the end of the recursion
template<class T, class...Ts, class... Vs,  int N, int M1, int M2>
struct assign_IDs<mytype<M1, T, Ts...>, N, mytype<M2, Vs...>> {
    using T_assigned = assign_IDs<T, N>;
    using next = assign_IDs<mytype<M1, Ts...>, T_assigned::next_index, mytype<M2, Vs..., typename T_assigned::type>>;
    using type = typename next::type;
    static constexpr int next_index = next::next_index;
};

// end of recursion, consume an index for the current mytype that we are processing
template<class... Vs, int N, int M1, int M2>
struct assign_IDs<mytype<M1>, N, mytype<M2, Vs...>> {
    using type = mytype<N, Vs...>;
    static constexpr int next_index = N + 1;
};

OTOH，我喜欢在显示类型时按升序排列数字。

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

C++ metaprogramming assign unique ID to tree structures

c++

metaprogramming

uniqueidentifier

c++11