適配非constexpr積分值與非類型模板參數，和代碼膨脹

Question

考慮一個功能對象F服用constexpr size_t參數I

struct F 
{ 
    template <size_t I> 
    constexpr size_t operator()(size <I>) const { return I; } 
}; 

纏繞的類型size <I>內，其中（爲了簡潔）

template <size_t N> 
using size = std::integral_constant <size_t, N>; 

當然，我們可以直接通過I，但我想強調它是通過使用它作爲模板參數的constexpr。函數F在這裏是虛構的，但實際上它可以執行各種有用的東西，比如從元組的元素I中檢索信息。假定F具有相同的返回類型，而不管I。 I可以是任何整數類型，但假定爲非負值。

問題

給定一個constexpr size_t值I，我們可以通過

F()(size <I>()); 

打電話F現在，如果我們要調用F與非constepr size_t值i什麼？考慮以下幾點：？

constexpr size_t L = 10; 
idx <F, L> f; 
for (size_t i = 0; i < L; ++i) 
    cout << f(i) << " "; 

（爲什麼需要這個要給予一定的背景下，我其實想建立一個複合迭代器的容器觀點，即表示「加入」序列（串聯）異構容器中，這樣可以說join(a, b) = c;這樣的數組，其中數組join(a, b)和c長度相等，但是i是迭代器狀態，因此不能是constexpr，但子迭代器存儲在元組中，需要被constexpr訪問指數個人value_type的大致一致，以便加入的視圖可以採取他們的common_type類型，但子容器和因此子迭代器是不同類型的。）

解

在這裏，我已經想出結構idx <F, L>，其適應功能F用於此目的，假設輸入參數小於L。這實際上編譯罰款輸出

0 1 2 3 4 5 6 7 8 9 

這裏是一個live example。

idx作品通過遞歸分解輸入i成二進制表示和重建constexpr對方N：

template <typename F, size_t L, size_t N = 0, bool = (N < L)> 
struct idx 
{ 
    template <size_t R = 1> 
    inline constexpr decltype(F()(size <0>())) 
    operator()(size_t I, size <R> = size <R>()) const 
    { 
     return I%2 ? idx <F, L, N+R>()(--I/2, size <2*R>()) : 
       I ? idx <F, L, N >()( I/2, size <2*R>()) : 
       F()(size <N>()); 
    } 
}; 

其中R表示2在當前迭代的功率。爲了避免無限模板實例化，專業化，給出了N >= L，返回F()(size <0>())爲虛值：

template <typename F, size_t L, size_t N> 
struct idx <F, L, N, false> 
{ 
    template <size_t R> 
    inline constexpr decltype(F()(size <0>())) 
    operator()(size_t I, size <R>) const { return F()(size <0>()); } 
}; 

事實上，這種方法是比較常見的成語有一個布爾參數的概括：

bool b = true; 
b ? f <true>() : f <false>(); 

其中f是以bool作爲模板參數的函數。在這種情況下，顯然所有兩個可能的版本f都被實例化了。

問題

雖然這個作品和它的運行時間複雜度爲i想必對數，我關心的是編譯時的影響，如：

• 的idx多少組合並且它的template operator()被實例化爲在運行時爲編譯時未知的任何輸入i工作？ （我明白「所有可能」，但又有多少？）

• 是否真的可以內聯operator()？

• 是否有任何替代策略或變體「更容易」編譯？

• 作爲純code bloat的實例，我應該忘記這個想法嗎？

注

下面是編譯時間（秒）和可執行的大小（單位爲KB）我已經測量了不同的值的L：

L  Clang(s) GCC(s) Clang(KB) GCC(KB) 
10  1.3  1.7   33   36 
20  2.1  3.0   48   65 
40  3.7  5.8   87  120 
80  7.0  11.2   160  222 
160  13.9  23.4   306  430 
320  28.1  47.8   578  850 
640  56.5  103.0  1126  1753 

所以，雖然它在L出現大致線性，這是相當長和令人沮喪的大。

試圖強制operator()內聯失敗：可能被Clang忽略（可執行的更大），而GCC報告recursive inlining。

在可執行文件上運行nm -C對於L = 160，顯示511/1253不同版本的operator()（與Clang/GCC）。這些全部用於N < L，所以看起來終止專用N >= L確實被內聯。

PS。我會添加標籤code-bloat但系統不會讓我。

Answer 1

我稱這種技術爲魔法開關。

我知道這樣做的最有效的方法是建立你自己的跳轉表。

// first, index list boilerplate. Does log-depth creation as well 
// needed for >1000 magic switches: 
template<unsigned...Is> struct indexes {typedef indexes<Is...> type;}; 
template<class lhs, class rhs> struct concat_indexes; 
template<unsigned...Is, unsigned...Ys> struct concat_indexes<indexes<Is...>, indexes<Ys...>>{ 
    typedef indexes<Is...,Ys...> type; 
}; 
template<class lhs, class rhs> 
using ConcatIndexes = typename concat_indexes<lhs, rhs>::type; 

template<unsigned min, unsigned count> struct make_indexes: 
    ConcatIndexes< 
     typename make_indexes<min, count/2>::type, 
     typename make_indexes<min+count/2, (count+1)/2>::type 
    > 
{}; 
template<unsigned min> struct make_indexes<min, 0>: 
    indexes<> 
{}; 
template<unsigned min> struct make_indexes<min, 1>: 
    indexes<min> 
{}; 
template<unsigned max, unsigned min=0> 
using MakeIndexes = typename make_indexes<min, max-min>::type; 

// This class exists simply because [](blah){code}... `...` expansion 
// support is lacking in many compilers: 
template< typename L, typename R, unsigned I > 
struct helper_helper { 
    static R func(L&& l) { return std::forward<L>(l)(size<I>()); } 
}; 
// the workhorse. Creates an "manual" jump table, then invokes it: 
template<typename L, unsigned... Is> 
auto 
dispatch_helper(indexes<Is...>, L&& l, unsigned i) 
-> decltype(std::declval<L>()(size<0>())) 
{ 
    // R is return type: 
    typedef decltype(std::declval<L>()(size<0>())) R; 
    // F is the function pointer type for our jump table: 
    typedef R(*F)(L&&); 
    // the jump table: 
    static const F table[] = { 
    helper_helper<L, R, Is>::func... 
    }; 
    // invoke at the jump spot: 
    return table[i](std::forward<L>(l)); 
}; 
// create an index pack for each index, and invoke the helper to 
// create the jump table: 
template<unsigned Max, typename L> 
auto 
dispatch(L&& l, unsigned i) 
-> decltype(std::declval<L>()(size<0>())) 
{ 
    return dispatch_helper(MakeIndexes<Max>(), std::forward<L>(l), i); 
}; 

這需要一些靜態設置，但運行時速度非常快。

斷言i處於界限內也可能有用。

live example

Answer 2

我會在這裏採取明顯的位置，並問：「我想強調，這是constexpr使用它作爲一個模板參數」是值得這筆費用，如果：

struct F 
{ 
    constexpr size_t operator()(size_t i) const { return i; } 
    template <size_t I> 
    constexpr size_t operator()(size <I>) const { return (*this)(I); } 
}; 

不會是一個更簡單的解決方案。

Answer 3

這是不完全的答案，我的問題仍然有效，但我已經找到了解決辦法，讓在編譯一個令人印象深刻的推動作用。它是在的問題，其中，參數R從operator()外移動到結構idx給出的溶液的細微調整，和終端條件現在包括兩個R和N：

template < 
    typename F, size_t L, 
    size_t R = 1, size_t N = 0, bool = (R < 2 * L && N < L) 
> 
struct idx //... 

整個代碼是在該給定新的live example。

這種方法顯然減少了大量不必要的專門化組合R。編譯時間和可執行文件大小急劇下降。例如，我已經能夠在10.7/18.7秒內用Clang/GCC編譯L = 1<<12（4096），產生220/239 KB的可執行文件。在這種情況下，nm -C顯示operator()的546/250版本。

Answer 4

如果您的解決方案有最大可能值上限（256說），你可以使用宏魔術和switch語句簡化它：

#define POS(i) case (i): return F<(i)>(); break; 
#define POS_4(i) POS(i + 0) POS(i + 1) POS(i + 2) POS(i + 3) 
#define POS_16(i) POS_4(i + 0) POS_4(i + 4) POS_4(i + 8) POS_4(i + 12) 

int func(int i) 
{ 
    switch(i) 
    { 
     POS_16(0) 
    } 
} 

另一種可能的解決方案是（用C++ 11）使用可變參數模板：

template<int I> 
struct FF 
{ 
    static int f() { return I; } 
}; 


template<typename... I> 
int func(int i) 
{ 
    constexpr int (*Func[])() = { I::f... }; 
    return Func[i](); 
} 

int main(int argc, char** argv) 
{ 
    func<FF<0>,FF<1>>(1); 
}