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. 元函數必須保持已使用（或相當於下一個可用值）的值，並將所得類型的軌道。
2. 由於列表中每種類型的處理都依賴於以前的類型，所以簡單的包擴展是不可行的，您需要使用遞歸來處理它。

最小的區別是我沒有使用單獨的計數器類型，而且我做了前序遍歷而不是後序遍歷。我也以不同的方式處理了連接。

// 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，我喜歡有遞增的順序號碼顯示類型時。

Answer 2

基本思路：

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。也在評論中發佈了一個解決方案，看起來更簡單。